连连看是广受欢迎的配对消除类游戏，核心挑战在于两点之间是否存在合法路径。传统的实现往往对每个候选对单独做路径搜索，效率较低。本文引入并查集（Union-Find）维护棋盘空区域的连通状态，快速筛选潜在可消除对；再结合启发式评估函数决定消除顺序，实现一个高效且具备一定智能的连连看引擎。
游戏规则与算法建模
在标准连连看中，两个相同图案的格子可以消除，当且仅当它们之间能用一条折线连接，且折线最多包含两个拐点（即最多三条线段）。路径只能穿过空格或起点/终点本身。
将问题抽象为以下三个子问题：
- 路径检测：给定两个坐标，判断是否存在合法折线路径。
- 连通块分析：哪些图案对在当前局面下理论可达？
- 消除策略：当存在多组可消除对时，优先消除哪一组？
并查集与空区域连通块
随着消除进行，棋盘上的空格会逐渐增多并形成大片连通区域。我们用并查集维护所有空格的连通状态：相邻（上下左右）的空格属于同一集合。这样可以在近似 $O(1)$ 时间内判断两个空格是否处于同一片”自由区域”。
更重要的是，我们可以为每种图案的每个实例标记它”属于”哪个空区域（通过向四个方向扩展找到最近的空格所属集合）。如果某种图案的所有实例分布在两个以上不同的空区域集合中，且这些区域之间被其他图案完全阻隔，则当前局面可能已进入”死局”边缘，需要优先打破阻隔。
路径检测：枚举拐点法
两个格子 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的连通路径分为三种情况：
- 0个拐点：同行或同列，中间全为空格。
- 1个拐点：拐点 $(i,j)$ 必须同时满足到两个端点的直线路径畅通。
- 2个拐点：路径呈”Z”字形或”U”字形，枚举两个中间点并验证各段畅通。
由于棋盘尺寸通常不大（如 $8 \times 12$），直接枚举拐点位置配合 $O(1)$ 的并查集查询，整体效率极高。
启发式消除策略
并非所有可消除对的价值都相同。我们设计一个评估函数，从以下维度打分：
- 边缘优先：位于棋盘边缘的图案更容易造成后续堵死，优先消除。
- 区域连通价值：消除后能使两个原本分离的空区域合并为一个大区域的配对，获得更高分。
- 图案稀缺度：剩余数量少的图案优先配对，防止最后落单。
综合得分为三项的加权和，每次选择得分最高的配对进行消除。
完整Java实现
以下代码实现了完整的连连看核心引擎，包含并查集、路径检测、启发式策略与自动求解演示。
import java.util.*;
/**
* 并查集（Union-Find）：维护空格连通区域
* 支持路径压缩与按秩合并，近似O(1)查询
*/
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
public void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
// 按秩合并
if (rank[rx] < rank[ry]) {
parent[rx] = ry;
} else if (rank[rx] > rank[ry]) {
parent[ry] = rx;
} else {
parent[ry] = rx;
rank[rx]++;
}
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public void reset(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
}
/**
* 连连看游戏引擎
* 核心能力：并查集空区域分析 + 折线路径检测 + 启发式消除
*/
public class LinkGame {
private final int rows;
private final int cols;
private int[][] board; // 0表示空，>0表示图案类型
private final UnionFind uf; // 并查集维护空格连通性
// 方向向量：上、下、左、右
private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
public LinkGame(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.board = new int[rows][cols];
this.uf = new UnionFind(rows * cols);
}
/**
* 将二维坐标转为一维索引
*/
private int id(int r, int c) {
return r * cols + c;
}
/**
* 初始化棋盘：生成成对的随机图案
* @param types 图案种类数
*/
public void initBoard(int types) {
List<Integer> tiles = new ArrayList<>();
int total = rows * cols;
// 确保总数为偶数，每种图案出现偶数次
for (int i = 0; i < total / 2; i++) {
int type = (i % types) + 1;
tiles.add(type);
tiles.add(type);
}
Collections.shuffle(tiles);
int idx = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
board[r][c] = tiles.get(idx++);
}
}
rebuildUF();
}
/**
* 重建并查集：将所有相邻空格连接
*/
public void rebuildUF() {
uf.reset(rows * cols);
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == 0) {
int cur = id(r, c);
// 只检查右和下，避免重复
if (c + 1 < cols && board[r][c + 1] == 0) {
uf.union(cur, id(r, c + 1));
}
if (r + 1 < rows && board[r + 1][c] == 0) {
uf.union(cur, id(r + 1, c));
}
}
}
}
}
/**
* 检查坐标是否在棋盘内
*/
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
/**
* 核心路径检测：判断(r1,c1)与(r2,c2)之间是否存在合法路径
* 合法路径：最多2个拐点，只能经过空格或端点本身
*/
public boolean canConnect(int r1, int c1, int r2, int c2) {
if (board[r1][c1] == 0 || board[r2][c2] == 0) return false;
if (board[r1][c1] != board[r2][c2]) return false;
if (r1 == r2 && c1 == c2) return false;
// 情况1：0个拐点（直线连通）
if (straightLine(r1, c1, r2, c2)) return true;
// 情况2：1个拐点
// 枚举拐点：两个端点的横纵坐标交叉点
if (isEmptyPath(r1, c1, r1, c2) && isEmptyPath(r1, c2, r2, c2)) return true;
if (isEmptyPath(r1, c1, r2, c1) && isEmptyPath(r2, c1, r2, c2)) return true;
// 情况3：2个拐点
// 枚举第一拐点在同一行，第二拐点在同一列
for (int i = 0; i < rows; i++) {
if (i == r1 || i == r2) continue;
if ((board[i][c1] == 0 || (i == r2 && c1 == c2)) &&
(board[i][c2] == 0 || (i == r1 && c2 == c1)) &&
isEmptyPath(r1, c1, i, c1) &&
isEmptyPath(i, c1, i, c2) &&
isEmptyPath(i, c2, r2, c2)) {
return true;
}
}
// 枚举第一拐点在同一列，第二拐点在同一行
for (int j = 0; j < cols; j++) {
if (j == c1 || j == c2) continue;
if ((board[r1][j] == 0 || (r1 == r2 && j == c2)) &&
(board[r2][j] == 0 || (r2 == r1 && j == c1)) &&
isEmptyPath(r1, c1, r1, j) &&
isEmptyPath(r1, j, r2, j) &&
isEmptyPath(r2, j, r2, c2)) {
return true;
}
}
return false;
}
/**
* 判断两点是否同行或同列且中间全为空格（端点除外）
*/
private boolean straightLine(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] != 0) 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] != 0) return false;
}
return true;
}
return false;
}
/**
* 判断从(r1,c1)到(r2,c2)的直线路径是否畅通
* 起点和终点可以是图案，中间必须为空
*/
private boolean isEmptyPath(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; c <= max; c++) {
if (c != c1 && c != c2 && board[r1][c] != 0) return false;
}
return true;
}
if (c1 == c2) {
int min = Math.min(r1, r2), max = Math.max(r1, r2);
for (int r = min; r <= max; r++) {
if (r != r1 && r != r2 && board[r][c1] != 0) return false;
}
return true;
}
return false;
}
/**
* 启发式评估函数：给一组可消除对打分
* 分数越高越应该优先消除
*/
private double evaluateMove(int r1, int c1, int r2, int c2) {
double score = 0;
// 维度1：边缘优先（边缘格子后续更难匹配）
if (r1 == 0 || r1 == rows - 1 || c1 == 0 || c1 == cols - 1) score += 10;
if (r2 == 0 || r2 == rows - 1 || c2 == 0 || c2 == cols - 1) score += 10;
// 维度2：连通区域合并价值
// 消除后这两个位置变为空格，如果它们原本属于不同的空区域集合，合并价值高
Set<Integer> emptySets = new HashSet<>();
for (int[] d : DIRS) {
int nr1 = r1 + d[0], nc1 = c1 + d[1];
if (inBounds(nr1, nc1) && board[nr1][nc1] == 0) {
emptySets.add(uf.find(id(nr1, nc1)));
}
int nr2 = r2 + d[0], nc2 = c2 + d[1];
if (inBounds(nr2, nc2) && board[nr2][nc2] == 0) {
emptySets.add(uf.find(id(nr2, nc2)));
}
}
score += emptySets.size() * 15; // 连接越多的独立区域，价值越高
// 维度3：图案稀缺度（剩余数量少的优先）
int type = board[r1][c1];
int remaining = countRemaining(type);
score += (20 - remaining) * 2; // 剩余越少，分数越高
return score;
}
/**
* 统计某类图案剩余数量
*/
private int countRemaining(int type) {
int cnt = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == type) cnt++;
}
}
return cnt;
}
/**
* 查找当前局面下的最佳消除对
* @return int[]{r1,c1,r2,c2}，若无解返回null
*/
public int[] findBestMatch() {
List<int[]> candidates = new ArrayList<>();
for (int r1 = 0; r1 < rows; r1++) {
for (int c1 = 0; c1 < cols; c1++) {
if (board[r1][c1] == 0) continue;
for (int r2 = r1; r2 < rows; r2++) {
int cStart = (r2 == r1) ? c1 + 1 : 0;
for (int c2 = cStart; c2 < cols; c2++) {
if (board[r2][c2] == 0) continue;
if (canConnect(r1, c1, r2, c2)) {
candidates.add(new int[]{r1, c1, r2, c2});
}
}
}
}
}
if (candidates.isEmpty()) return null;
// 按启发式分数排序，返回最高分
candidates.sort((a, b) -> {
double scoreA = evaluateMove(a[0], a[1], a[2], a[3]);
double scoreB = evaluateMove(b[0], b[1], b[2], b[3]);
return Double.compare(scoreB, scoreA); // 降序
});
return candidates.get(0);
}
/**
* 执行消除
*/
public boolean eliminate(int r1, int c1, int r2, int c2) {
if (!canConnect(r1, c1, r2, c2)) return false;
board[r1][c1] = 0;
board[r2][c2] = 0;
rebuildUF(); // 更新空格连通状态
return true;
}
/**
* 自动求解：使用启发式策略一步步消除
*/
public void autoSolve() {
int steps = 0;
while (true) {
int[] match = findBestMatch();
if (match == null) break;
eliminate(match[0], match[1], match[2], match[3]);
steps++;
System.out.printf("第%2d步: 消除 (%d,%d) <-> (%d,%d)\n",
steps, match[0], match[1], match[2], match[3]);
}
int remaining = 0;
for (int[] row : board) {
for (int v : row) if (v != 0) remaining++;
}
if (remaining == 0) {
System.out.println("恭喜！自动求解成功，全部消除！");
} else {
System.out.println("未完全消除，剩余 " + remaining + " 个图案。");
}
}
/**
* 打印棋盘
*/
public void printBoard() {
System.out.println("当前棋盘：");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.printf("%3d", board[r][c]);
}
System.out.println();
}
}
public static void main(String[] args) {
// 创建一个 6x8 的棋盘，使用 6 种图案
LinkGame game = new LinkGame(6, 8);
game.initBoard(6);
System.out.println("=== 连连看初始化 ===");
game.printBoard();
System.out.println("\n=== 并查集空区域分析 ===");
// 初始没有空格，每个空格独立（实际上没有空格）
System.out.println("初始无空格，并查集待用。");
System.out.println("\n=== 启发式自动求解 ===");
game.autoSolve();
System.out.println("\n=== 最终棋盘 ===");
game.printBoard();
}
}
并查集的关键作用解析
代码中 rebuildUF() 方法在每次消除后被调用，重新构建所有空格的并查集。这一设计看似简单，实则解决了两个核心问题：
第一，死局预判。 在 evaluateMove 中，我们检查待消除位置四周的空格分别属于哪些并查集集合。如果某图案的所有实例周围只出现唯一一个空区域集合，说明该图案被”围困”在单一区域中，消除其他对子无法帮它创造路径；反之，若周围空区域集合越多，消除该对后越可能打通全局。
第二，连通块合并评估。 emptySets.size() 直接量化了消除操作带来的”结构收益”——连接越多的独立空区域，后续的路径选择就越丰富。这使得算法不再盲目消除，而是主动创造更有利的局面。
路径检测的性能优化
路径检测 canConnect 采用直接枚举拐点策略，时间复杂度为 $O(R + C)$，其中 $R$ 和 $C$ 为棋盘行列数。对于常见的 $8 \times 12$ 棋盘，单次检测仅需数十次操作。配合启发式策略对候选对的剪枝，整体求解速度完全满足实时交互需求。
如果棋盘尺寸更大，可将 canConnect 中的拐点枚举替换为 BFS（限制深度为 3），但代码复杂度会显著增加。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 路径检测 | $O(R + C)$ | 枚举0/1/2个拐点 |
| 并查集查询 | $O(\alpha(N))$ | 反阿克曼函数，近似常数 |
| 单次消除重建UF | $O(R \times C)$ | 遍历整个棋盘 |
| 启发式选点 | $O(K \cdot (R + C))$ | $K$ 为候选对数量 |
| 整体求解 | $O(N^2 \cdot (R + C))$ | $N$ 为图案总数 |
总结
本文将并查集这一经典数据结构创新性地应用于连连看的空区域分析，配合启发式评估函数实现了具备策略性的自动求解引擎。读者可以从中学习到：并查集在非图论场景中的灵活运用、折线路径的枚举思路，以及如何用简单的启发式规则赋予算法”优先级意识”。这些技巧在 puzzle 类游戏 AI 开发中具有广泛的迁移价值。
