引言
连连看是一款经典的消除类益智游戏：玩家在由各种图案组成的棋盘中，寻找两个相同且能用不超过3条直线连接的图案进行消除。看似简单的规则背后，涉及图论中的路径搜索、连通性判断与匹配算法。本文用Java实现一个带AI求解器的连连看游戏，核心在于如何高效判断两点之间是否存在合法连接路径。
算法原理
1. 合法路径定义
连连看中的合法路径需满足：
– 路径由水平或垂直线段组成
– 转折点（拐点）不超过2个
– 路径经过的格子必须为空（已消除的格子视为空）
2. BFS路径搜索
将问题建模为图搜索：每个空格子或目标图案位置为节点，水平/垂直相邻的空格子之间有边。从起点出发进行BFS，限制拐点数≤2，找到到达终点的最短路径。
3. 零拐点直连检测
若两点在同一行或同一列，且中间所有格子为空，则可直接连接。这是最快的情况，时间复杂度O(n)。
4. 一拐点与二拐点检测
- 一拐点：存在某空格子C，使A→C和C→B均为直连
- 二拐点：存在两条垂直线段的组合连接A和B
Java实现
import java.util.*;
/**
* 连连看AI求解器实现
* 包含BFS路径搜索、连通性检测与自动消除策略
*/
public class LinkUp {
static final int EMPTY = 0;
int rows, cols;
int[][] board; // 0表示空，其他数字表示图案类型
public LinkUp(int rows, int cols) {
this.rows = rows + 2; // 外扩一圈便于边界处理
this.cols = cols + 2;
this.board = new int[this.rows][this.cols];
// 外圈默认为EMPTY(0)，内圈随机生成图案
generateBoard(rows, cols);
}
void generateBoard(int r, int c) {
Random rand = new Random();
List<Integer> tiles = new ArrayList<>();
int total = r * c;
// 确保总数为偶数
for (int i = 0; i < total / 2; i++) {
int type = 1 + rand.nextInt(20); // 20种图案
tiles.add(type);
tiles.add(type);
}
Collections.shuffle(tiles);
int idx = 0;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
board[i][j] = tiles.get(idx++);
}
}
}
/**
* 检查两点之间是否存在合法路径（拐点≤2）
*/
boolean canConnect(int r1, int c1, int r2, int c2) {
if (board[r1][c1] == EMPTY || board[r2][c2] == EMPTY) return false;
if (board[r1][c1] != board[r2][c2]) return false;
if (r1 == r2 && c1 == c2) return false;
// 0个拐点：直连
if (directConnect(r1, c1, r2, c2)) return true;
// 1个拐点
if (oneCornerConnect(r1, c1, r2, c2)) return true;
// 2个拐点
if (twoCornerConnect(r1, c1, r2, c2)) return true;
return false;
}
/**
* 直连检测：同一行或同一列，中间无障碍
*/
boolean directConnect(int r1, int c1, int r2, int c2) {
if (r1 == r2) {
int min = Math.min(c1, c2), max = Math.max(c1, c2);
for (int c = min + 1; c < max; c++) {
if (board[r1][c] != EMPTY) return false;
}
return true;
}
if (c1 == c2) {
int min = Math.min(r1, r2), max = Math.max(r1, r2);
for (int r = min + 1; r < max; r++) {
if (board[r][c1] != EMPTY) return false;
}
return true;
}
return false;
}
/**
* 一拐点检测：存在一个中间点使两段均为直连
*/
boolean oneCornerConnect(int r1, int c1, int r2, int c2) {
// 候选拐点：(r1, c2) 和 (r2, c1)
if (board[r1][c2] == EMPTY && directConnect(r1, c1, r1, c2) && directConnect(r1, c2, r2, c2)) {
return true;
}
if (board[r2][c1] == EMPTY && directConnect(r1, c1, r2, c1) && directConnect(r2, c1, r2, c2)) {
return true;
}
return false;
}
/**
* 二拐点检测：BFS搜索最多2个拐点的路径
*/
boolean twoCornerConnect(int r1, int c1, int r2, int c2) {
// 从(r1,c1)出发，沿四个方向走，每遇到一个拐点计数+1
// 优化：枚举所有可能的中间空行和空列
for (int r = 0; r < rows; r++) {
if (board[r][c1] == EMPTY || r == r1) {
if (directConnect(r1, c1, r, c1) && oneCornerConnect(r, c1, r2, c2)) {
return true;
}
}
}
for (int c = 0; c < cols; c++) {
if (board[r1][c] == EMPTY || c == c1) {
if (directConnect(r1, c1, r1, c) && oneCornerConnect(r1, c, r2, c2)) {
return true;
}
}
}
return false;
}
/**
* 获取指定图案类型的所有位置
*/
List<int[]> getPositions(int type) {
List<int[]> pos = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == type) pos.add(new int[]{r, c});
}
}
return pos;
}
/**
* AI自动寻找可消除的一对图案
* 策略：遍历所有图案类型，找到第一个可连接的配对
*/
int[] findMatch() {
Set<Integer> types = new HashSet<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] != EMPTY) types.add(board[r][c]);
}
}
for (int type : types) {
List<int[]> pos = getPositions(type);
for (int i = 0; i < pos.size(); i++) {
for (int j = i + 1; j < pos.size(); j++) {
int[] a = pos.get(i), b = pos.get(j);
if (canConnect(a[0], a[1], b[0], b[1])) {
return new int[]{a[0], a[1], b[0], b[1]};
}
}
}
}
return null;
}
/**
* 执行消除
*/
void eliminate(int r1, int c1, int r2, int c2) {
board[r1][c1] = EMPTY;
board[r2][c2] = EMPTY;
}
/**
* 检查棋盘是否已清空
*/
boolean isClear() {
for (int[] row : board) {
for (int cell : row) {
if (cell != EMPTY) return false;
}
}
return true;
}
/**
* AI自动求解整局游戏
*/
void autoSolve() {
int steps = 0;
while (!isClear()) {
int[] match = findMatch();
if (match == null) {
System.out.println("无法继续消除，游戏失败！");
return;
}
eliminate(match[0], match[1], match[2], match[3]);
steps++;
}
System.out.println("===== 连连看AI自动求解 =====");
System.out.println("棋盘大小: " + (rows - 2) + "x" + (cols - 2));
System.out.println("消除步数: " + steps);
System.out.println("求解成功！");
}
void printBoard() {
for (int r = 1; r < rows - 1; r++) {
for (int c = 1; c < cols - 1; c++) {
System.out.printf("%2d ", board[r][c]);
}
System.out.println();
}
}
public static void main(String[] args) {
LinkUp game = new LinkUp(6, 8); // 6x8棋盘
System.out.println("初始棋盘:");
game.printBoard();
game.autoSolve();
}
}
复杂度分析
- 直连检测：O(max(rows, cols))
- 一拐点检测：O(1)，仅2个候选点
- 二拐点检测：O(rows + cols)，枚举所有空行和空列
- 单次连通判断：O(rows + cols)
- AI自动求解：最坏O(k² × n² × (rows + cols))，k为图案种类数，n为每种图案数量
扩展方向
- 全局最优策略：每一步选择使后续可选消除对数最大化的匹配，可用贪心或回溯
- 死锁检测与重排：若当前无解，检测死锁并触发图案重排
- 多线程并行：多线程同时搜索不同图案类型的配对
总结
本文实现了连连看的核心连通性检测算法，将”最多2个拐点”的路径条件转化为三层直连检测（0拐点、1拐点、2拐点），时间复杂度从朴素BFS的O((rc)²)优化至O(r+c)。AI自动求解器可快速完成整局消除。
