连连看是一款经典的益智消除游戏，规则简单却蕴含丰富的算法思想。本文将用 Java 实现一个带 AI 自动消除的连连看程序，核心讲解BFS 路径连通检测（判断两点间能否通过不超过两次拐弯连接）以及贪心消除策略（自动寻找最优消除顺序）。通过游戏场景，你将深入理解图搜索与启发式决策的实际应用。
游戏规则与问题建模
标准连连看在一个 $M \times N$ 的棋盘上随机摆放成对的图案。玩家需要找出两个相同的图案，如果它们之间的连线转折不超过两次（即最多经过三条直线段），则可以消除。消除后图案清空，当所有图案被消除时游戏胜利。
从算法角度看，连连看包含两个核心问题：
- 连通性判定：给定两个相同图案的坐标，判断是否存在合法路径（拐弯数 $\le 2$）。
- 消除顺序决策：当棋盘上存在多组可消除的图案时，如何选择消除顺序以避免死局。
核心算法一：BFS 路径连通检测
算法思路
判断两点间是否存在合法路径，最直接的方法是 BFS。不同于普通迷宫寻路，连连看的路径约束是拐弯次数而非步数。我们需要在状态中加入当前移动方向和已拐弯次数。
状态定义为 (row, col, direction, turns)，其中：
– direction 表示进入当前格子的方向（上/下/左/右/无）
– turns 表示从起点到当前格子已经拐弯的次数
从起点出发，向四个方向扩展：
– 如果新方向与当前方向相同，拐弯次数不变，直线前进。
– 如果新方向与当前方向不同（且当前方向不是”无”），拐弯次数 $+1$。
– 一旦拐弯次数超过 $2$，该分支直接剪枝。
BFS 保证了我们找到的是拐弯数最少的路径，只要存在合法路径就一定能找到。
Java 实现
import java.util.*;
/**
* 连连看路径连通检测 —— BFS 版本
* 判断两点之间是否存在拐弯数 <= 2 的合法路径
*/
public class LinkUpPathFinder {
// 四个方向：上、下、左、右
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 方向编号与 DIRS 对应：0=上, 1=下, 2=左, 3=右
private static final int DIR_NONE = -1;
private static final int MAX_TURNS = 2;
/**
* 检查从 (r1,c1) 到 (r2,c2) 是否存在合法路径
* @param board 棋盘，0 表示空，非 0 表示图案编号
* @param r1 起点行
* @param c1 起点列
* @param r2 终点行
* @param c2 终点列
* @return 是否存在合法路径
*/
public boolean canConnect(int[][] board, int r1, int c1, int r2, int c2) {
int rows = board.length;
int cols = board[0].length;
// visited[r][c][d] 表示从某个方向 d 到达 (r,c) 时的最小拐弯数
// d=4 表示无方向（起点状态）
int[][][] visited = new int[rows][cols][5];
for (int[][] layer : visited) {
for (int[] row : layer) {
Arrays.fill(row, Integer.MAX_VALUE);
}
}
Deque<State> queue = new ArrayDeque<>();
queue.offer(new State(r1, c1, 4, 0)); // 起点，无方向，0拐弯
visited[r1][c1][4] = 0;
while (!queue.isEmpty()) {
State cur = queue.poll();
// 到达终点（且不是起点本身）
if (cur.r == r2 && cur.c == c2 && !(cur.r == r1 && cur.c == c1)) {
return true;
}
for (int d = 0; d < 4; d++) {
int nr = cur.r + DIRS[d][0];
int nc = cur.c + DIRS[d][1];
// 越界检查
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
// 计算新拐弯数
int newTurns = cur.turns;
if (cur.dir != 4 && cur.dir != d) {
newTurns++;
}
// 剪枝：拐弯数超过限制
if (newTurns > MAX_TURNS) continue;
// 下一步要么是空格（0），要么是终点（不能踩其他图案）
boolean isTarget = (nr == r2 && nc == c2);
if (board[nr][nc] != 0 && !isTarget) continue;
// 如果通过方向 d 到达 (nr,nc) 的拐弯数更优，则加入队列
if (newTurns < visited[nr][nc][d]) {
visited[nr][nc][d] = newTurns;
queue.offer(new State(nr, nc, d, newTurns));
}
}
}
return false;
}
/**
* BFS 状态节点
*/
private static class State {
int r, c; // 坐标
int dir; // 进入当前格子的方向
int turns; // 已拐弯次数
State(int r, int c, int dir, int turns) {
this.r = r;
this.c = c;
this.dir = dir;
this.turns = turns;
}
}
}
复杂度分析
- 时间复杂度：$O(rows \times cols \times 5)$。棋盘每个格子的每个方向最多入队一次，常数 $5$ 为方向数（含无方向状态）。
- 空间复杂度：$O(rows \times cols \times 5)$，用于
visited数组和队列。
核心算法二：贪心消除策略
为什么需要策略？
连连看并非总能通关。如果玩家随意消除，可能过早地堵住某些图案的唯一出口，导致死局。一个良好的 AI 消除策略应当：优先消除那些”选择最少”的图案对，或者说优先消除位于边缘、角落的图案，避免把通路堵死。
贪心启发规则
本文采用以下贪心策略：
- 枚举所有可消除对：遍历棋盘上所有相同图案的配对，用上述 BFS 检测是否连通。
- 计算每对图案的”自由度”：统计每个图案四周（上下左右）空格的数量，空格越多说明该图案越不紧迫。
- 优先消除四周空格最少的图案对：这类似于”排雷”思想——先处理受限最严重的图案，防止后续被堵死。
Java 实现
import java.util.*;
/**
* 连连看 AI 消除引擎 —— 贪心策略版
*/
public class LinkUpSolver {
private final LinkUpPathFinder pathFinder = new LinkUpPathFinder();
/**
* 寻找下一步最优消除
* @param board 当前棋盘
* @return 最优消除对的坐标，无法消除则返回 null
*/
public int[] findBestMove(int[][] board) {
int rows = board.length;
int cols = board[0].length;
// 收集所有相同图案的位置
Map<Integer, List<int[]>> groups = new HashMap<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] != 0) {
groups.computeIfAbsent(board[r][c], k -> new ArrayList<>()).add(new int[]{r, c});
}
}
}
int bestScore = Integer.MAX_VALUE;
int[] bestPair = null;
for (List<int[]> positions : groups.values()) {
// 两两配对检查连通性
for (int i = 0; i < positions.size(); i++) {
for (int j = i + 1; j < positions.size(); j++) {
int[] p1 = positions.get(i);
int[] p2 = positions.get(j);
if (pathFinder.canConnect(board, p1[0], p1[1], p2[0], p2[1])) {
// 计算这对图案的"紧迫度" = 四周空格数之和（越少越紧迫）
int freedom = countEmptyNeighbors(board, p1[0], p1[1])
+ countEmptyNeighbors(board, p2[0], p2[1]);
if (freedom < bestScore) {
bestScore = freedom;
bestPair = new int[]{p1[0], p1[1], p2[0], p2[1]};
}
}
}
}
}
return bestPair;
}
/**
* 统计某格子四周空格数量
*/
private int countEmptyNeighbors(int[][] board, int r, int c) {
int count = 0;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) {
if (board[nr][nc] == 0) count++;
} else {
// 边界外也算"空"，因为连连看可以绕到棋盘外面（有外框）
count++;
}
}
return count;
}
/**
* 自动通关：不断寻找最优消除直到棋盘清空或无法继续
*/
public boolean autoSolve(int[][] board) {
while (true) {
int[] move = findBestMove(board);
if (move == null) {
// 检查是否已全部消除
for (int[] row : board) {
for (int val : row) {
if (val != 0) return false; // 死局
}
}
return true; // 通关
}
// 执行消除
board[move[0]][move[1]] = 0;
board[move[2]][move[3]] = 0;
}
}
}
完整可运行项目
下面是一个最小化但可直接运行的完整程序，包含棋盘生成、BFS 连通检测、贪心 AI 消除和结果展示：
import java.util.*;
public class LinkUpGame {
private static final int ROWS = 8;
private static final int COLS = 10;
private static final int ICON_TYPES = 18; // 图案种类数
public static void main(String[] args) {
LinkUpGame game = new LinkUpGame();
int[][] board = game.generateBoard();
System.out.println("=== 初始棋盘 ===");
game.printBoard(board);
LinkUpSolver solver = new LinkUpSolver();
boolean success = solver.autoSolve(board);
System.out.println("\n=== 最终棋盘 ===");
game.printBoard(board);
System.out.println(success ? "\nAI 自动通关成功！" : "\n陷入死局，AI 无法通关。");
}
/**
* 生成随机可解棋盘：随机配对放置
*/
public int[][] generateBoard() {
int[][] board = new int[ROWS][COLS];
List<Integer> icons = new ArrayList<>();
int total = ROWS * COLS;
for (int i = 0; i < total / 2; i++) {
int type = (i % ICON_TYPES) + 1;
icons.add(type);
icons.add(type);
}
Collections.shuffle(icons);
int idx = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
board[r][c] = icons.get(idx++);
}
}
return board;
}
public void printBoard(int[][] board) {
for (int[] row : board) {
for (int val : row) {
System.out.printf("%3d", val);
}
System.out.println();
}
}
}
// ================== 以下为辅助类，实际项目中建议拆分为独立文件 ==================
class LinkUpPathFinder {
private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
private static final int DIR_NONE = 4;
private static final int MAX_TURNS = 2;
public boolean canConnect(int[][] board, int r1, int c1, int r2, int c2) {
int rows = board.length, cols = board[0].length;
int[][][] visited = new int[rows][cols][5];
for (int[][] layer : visited) for (int[] row : layer) Arrays.fill(row, Integer.MAX_VALUE);
Deque<State> q = new ArrayDeque<>();
q.offer(new State(r1, c1, DIR_NONE, 0));
visited[r1][c1][DIR_NONE] = 0;
while (!q.isEmpty()) {
State cur = q.poll();
if (cur.r == r2 && cur.c == c2 && !(cur.r == r1 && cur.c == c1)) return true;
for (int d = 0; d < 4; d++) {
int nr = cur.r + DIRS[d][0], nc = cur.c + DIRS[d][1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int nt = cur.turns + (cur.dir != DIR_NONE && cur.dir != d ? 1 : 0);
if (nt > MAX_TURNS) continue;
boolean target = (nr == r2 && nc == c2);
if (board[nr][nc] != 0 && !target) continue;
if (nt < visited[nr][nc][d]) {
visited[nr][nc][d] = nt;
q.offer(new State(nr, nc, d, nt));
}
}
}
return false;
}
private static class State {
int r, c, dir, turns;
State(int r, int c, int dir, int turns) { this.r=r; this.c=c; this.dir=dir; this.turns=turns; }
}
}
class LinkUpSolver {
private final LinkUpPathFinder finder = new LinkUpPathFinder();
public int[] findBestMove(int[][] board) {
int rows = board.length, cols = board[0].length;
Map<Integer, List<int[]>> groups = new HashMap<>();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (board[r][c] != 0)
groups.computeIfAbsent(board[r][c], k->new ArrayList<>()).add(new int[]{r,c});
int best = Integer.MAX_VALUE;
int[] pick = null;
for (List<int[]> list : groups.values()) {
for (int i = 0; i < list.size(); i++) {
for (int j = i+1; j < list.size(); j++) {
int[] a = list.get(i), b = list.get(j);
if (finder.canConnect(board, a[0], a[1], b[0], b[1])) {
int score = freedom(board, a[0], a[1]) + freedom(board, b[0], b[1]);
if (score < best) { best = score; pick = new int[]{a[0],a[1],b[0],b[1]}; }
}
}
}
}
return pick;
}
private int freedom(int[][] b, int r, int c) {
int cnt = 0;
int[][] d = {{-1,0},{1,0},{0,-1},{0,1}};
for (int[] v : d) {
int nr = r+v[0], nc = c+v[1];
if (nr<0||nr>=b.length||nc<0||nc>=b[0].length||b[nr][nc]==0) cnt++;
}
return cnt;
}
public boolean autoSolve(int[][] board) {
while (true) {
int[] m = findBestMove(board);
if (m == null) {
for (int[] row : board) for (int v : row) if (v != 0) return false;
return true;
}
board[m[0]][m[1]] = 0;
board[m[2]][m[3]] = 0;
}
}
}
算法延伸与思考
1. 为何用 BFS 而非 DFS？
BFS 按层扩展，天然保证找到的是拐弯数最少的路径。虽然连连看只关心是否存在（$\le 2$ 拐弯），但 BFS 的状态管理更直观，且不会出现 DFS 深层递归导致的栈溢出问题。
2. 贪心策略能保证 100% 通关吗？
不能。贪心策略只关注局部最优（先消除最紧迫的图案），但连连看的全局最优消除顺序可能需要在早期牺牲局部利益。对于更高阶的 AI，可以引入回溯搜索或蒙特卡洛模拟评估不同消除顺序的胜率。
3. 如何优化性能？
- 预计算连通性：每次消除只影响周围局部区域，可用增量更新代替全盘 BFS。
- 空间换时间：维护一个图案位置索引表，避免每次全表扫描。
- 死局提前检测：若某种图案只剩一个，直接判负。
总结
连连看将图搜索与启发式决策融合在简单的消除规则中。本文通过 BFS 状态扩展 解决了路径连通判定问题，通过贪心自由度评估实现了 AI 自动消除。读者可以在此基础上继续探索：将贪心升级为带搜索深度的 Minimax，或引入机器学习训练估值网络，让 AI 的通关率更进一步。
