连连看（Link-Up / Onet）是一款经典的消除类益智游戏，玩家需要在限定时间内找出并消除所有成对的相同图案，两个图案之间能用不超过两个拐点的折线连接即可消除。本文用Java实现一个带自动求解AI的连连看系统，核心讲解BFS最短路径搜索、连通性判断，以及状态空间搜索在残局求解中的应用。
路径连通性判定
连连看的核心规则是：两个相同图案之间的连线最多允许两个拐点（即最多3段直线）。路径搜索需要在包含空格（已消除位置）的棋盘上进行，且连线只能经过空格。
判定算法采用BFS，将问题建模为图搜索：
– 节点：棋盘上的每个格子
– 边：同行或同列且中间无障碍的格子对
– 状态：当前位置和已使用的拐点数
– 目标：到达目标图案位置，且拐点数≤2
状态空间搜索与消除策略
当存在多对可消除的图案时，消除顺序会影响后续局面。某些消除可能阻断其他配对的路径，因此AI需要评估每对消除的”战略价值”：
- 路径长度惩罚：路径越短的配对优先消除，保留长路径作为后续缓冲。
- 阻塞度评估：消除后是否会阻断其他配对的唯一路径。
- 角落优先：位于边缘和角落的图案可连接方向少，优先消除避免被困。
Java 实现
import java.util.*;
public class LinkUpSolver {
static final int EMPTY = 0; // 已消除
int rows, cols;
int[][] board;
// 方向：上、下、左、右
static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
public LinkUpSolver(int[][] board) {
this.board = board;
this.rows = board.length;
this.cols = board[0].length;
}
// BFS搜索从(startR,startC)到(targetR,targetC)的最短折线路径
// 返回路径拐点数，-1表示不可达（拐点>2）
public int findPathBFS(int sr, int sc, int tr, int tc) {
if (board[sr][sc] != board[tr][tc] || board[sr][sc] == EMPTY) return -1;
// 状态: [r, c, dir, turns] dir=-1表示起点，turns为已用拐点数
// 优先队列按turns排序
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[4]));
// visited[r][c][dir] = 到达该位置该方向的最小turns
int[][][] best = new int[rows][cols][4];
for (int[][] arr2 : best) for (int[] arr : arr2) Arrays.fill(arr, Integer.MAX_VALUE);
for (int d = 0; d < 4; d++) {
pq.offer(new int[]{sr, sc, d, 0, 0}); // r,c,dir,turns,pathLen
best[sr][sc][d] = 0;
}
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int r = cur[0], c = cur[1], dir = cur[2], turns = cur[3];
if (r == tr && c == tc && !(r == sr && c == sc)) return turns;
if (turns > best[r][c][dir]) continue;
for (int nd = 0; nd < 4; nd++) {
int nr = r + DIRS[nd][0], nc = c + DIRS[nd][1];
int nturns = turns + (nd == dir ? 0 : 1);
if (nturns > 2) continue; // 超过2个拐点
// 沿nd方向直线走到尽头
while (nr >= -1 && nr <= rows && nc >= -1 && nc <= cols) {
// 允许越界一格（连连看常见规则：可以从外部绕）
boolean inBounds = nr >= 0 && nr < rows && nc >= 0 && nc < cols;
if (inBounds && board[nr][nc] != EMPTY && !(nr == tr && nc == tc)) break;
if (nturns < best[nr < 0 || nr >= rows || nc < 0 || nc >= cols ? 0 : nr]
[nr < 0 || nr >= rows || nc < 0 || nc >= cols ? 0 : nc][nd]) {
// 简化处理：只记录棋盘内格子的最优值
if (inBounds && nturns < best[nr][nc][nd]) {
best[nr][nc][nd] = nturns;
pq.offer(new int[]{nr, nc, nd, nturns, 0});
}
}
if (nr == tr && nc == tc) return nturns; // 找到目标
nr += DIRS[nd][0]; nc += DIRS[nd][1];
}
}
}
return -1;
}
// 改进版BFS：支持从外部边界绕行（连连看标准规则）
public boolean canConnect(int sr, int sc, int tr, int tc) {
if (board[sr][sc] != board[tr][tc] || board[sr][sc] == EMPTY) return false;
// 扩展棋盘：外围增加一圈虚拟空格
int ER = rows + 2, EC = cols + 2;
boolean[][] extended = new boolean[ER][EC];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
extended[i+1][j+1] = board[i][j] != EMPTY;
// BFS: [r, c, dir, turns]
Queue<int[]> q = new LinkedList<>();
boolean[][][] visited = new boolean[ER][EC][4];
for (int d = 0; d < 4; d++) {
q.offer(new int[]{sr+1, sc+1, d, 0});
visited[sr+1][sc+1][d] = true;
}
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], dir = cur[2], turns = cur[3];
if (r == tr+1 && c == tc+1 && !(r == sr+1 && c == sc+1)) return true;
for (int nd = 0; nd < 4; nd++) {
int nturns = turns + (nd == dir ? 0 : 1);
if (nturns > 2) continue;
int nr = r + DIRS[nd][0], nc = c + DIRS[nd][1];
while (nr >= 0 && nr < ER && nc >= 0 && nc < EC) {
if (visited[nr][nc][nd]) { nr += DIRS[nd][0]; nc += DIRS[nd][1]; continue; }
boolean isTarget = (nr == tr+1 && nc == tc+1);
boolean isBlocked = extended[nr][nc];
if (isBlocked && !isTarget) break;
visited[nr][nc][nd] = true;
q.offer(new int[]{nr, nc, nd, nturns});
if (isTarget) return true;
nr += DIRS[nd][0]; nc += DIRS[nd][1];
}
}
}
return false;
}
// 查找所有可消除的配对
public List<int[]> findAllPairs() {
List<int[]> pairs = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == EMPTY) continue;
for (int pi = i; pi < rows; pi++) {
for (int pj = (pi == i ? j+1 : 0); pj < cols; pj++) {
if (board[pi][pj] == board[i][j] && canConnect(i, j, pi, pj)) {
pairs.add(new int[]{i, j, pi, pj});
}
}
}
}
}
return pairs;
}
// 评估消除的战略价值：路径短的、角落的优先
public double evaluatePair(int[] pair) {
int r1 = pair[0], c1 = pair[1], r2 = pair[2], c2 = pair[3];
double score = 100;
// 角落和边缘加分（位置受限，容易后续无法消除）
if (isCorner(r1, c1) || isCorner(r2, c2)) score += 50;
else if (isEdge(r1, c1) || isEdge(r2, c2)) score += 20;
// 路径惩罚：路径越复杂（需要多拐点）越优先消除
// 简化为：周围空格少的优先
score -= (countEmptyAround(r1, c1) + countEmptyAround(r2, c2)) * 2;
return score;
}
private boolean isCorner(int r, int c) {
return (r == 0 || r == rows-1) && (c == 0 || c == cols-1);
}
private boolean isEdge(int r, int c) {
return r == 0 || r == rows-1 || c == 0 || c == cols-1;
}
private int countEmptyAround(int r, int c) {
int cnt = 0;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == EMPTY) cnt++;
}
return cnt;
}
// 贪心求解：每次消除评分最高的配对
public List<int[]> greedySolve() {
List<int[]> solution = new ArrayList<>();
while (true) {
List<int[]> pairs = findAllPairs();
if (pairs.isEmpty()) break;
// 选择评分最高的配对
pairs.sort((a, b) -> Double.compare(evaluatePair(b), evaluatePair(a)));
int[] best = pairs.get(0);
solution.add(best);
board[best[0]][best[1]] = EMPTY;
board[best[2]][best[3]] = EMPTY;
}
return solution;
}
// 打印棋盘
public void printBoard() {
for (int[] row : board) {
for (int v : row) System.out.print((v == EMPTY ? " ." : String.format("%3d", v)));
System.out.println();
}
}
public static void main(String[] args) {
// 8x8简化测试棋盘，数字表示图案类型
int[][] board = {
{1, 2, 3, 4, 1, 2, 3, 4},
{5, 6, 7, 8, 5, 6, 7, 8},
{9,10, 1, 2, 9,10, 1, 2},
{3, 4, 5, 6, 3, 4, 5, 6},
{7, 8, 9,10, 7, 8, 9,10},
{1, 2, 3, 4, 1, 2, 3, 4},
{5, 6, 7, 8, 5, 6, 7, 8},
{9,10, 0, 0, 9,10, 0, 0} // 底部预留空格
};
LinkUpSolver solver = new LinkUpSolver(board);
System.out.println("Initial board:");
solver.printBoard();
List<int[]> solution = solver.greedySolve();
System.out.println("\nElimination order (" + solution.size() + " pairs):");
for (int i = 0; i < solution.size(); i++) {
int[] p = solution.get(i);
System.out.println((i+1) + ": (" + p[0] + "," + p[1] + ") -> (" + p[2] + "," + p[3] + ")");
}
System.out.println("\nRemaining board:");
solver.printBoard();
}
}
复杂度分析
- 时间复杂度：单次BFS连通性判断为O(rows×cols)，因为每个格子在每个方向上最多访问一次。查找所有配对为O(P² × rows × cols)，P为图案对数。
- 空间复杂度：O(rows×cols×4)用于BFS访问标记数组。
状态空间搜索优化
贪心策略在大多数局面下有效，但存在”死锁”风险——某些消除顺序会导致后续无可行配对。对于高难度关卡，可采用：
- 有限深度回溯：向前模拟k步消除，选择不导致死锁的路径。
- 并查集连通性预检：提前判断剩余图案是否仍全局可解。
- 洗牌重排：当检测到死锁时，重新随机排列剩余图案位置（游戏常见机制）。
连连看的路径搜索框架可推广至：电路板布线（VLSI设计）、管线连通检测、以及各类网格路径规划问题。
