连连看看起来像”眼力游戏”，但从算法视角看它是一个带几何约束的匹配问题：棋盘上每种图案恰好出现偶数次，玩家每次要挑出一对图案，且它们之间能用最多两次拐弯的折线连通。把”同图案的任意两个格子”看作一条潜在边，整张棋盘就变成了一张二分图，而”能否全部消完”本质上就是这张图上存不存在完美匹配。本文用 Hopcroft-Karp 算法把匹配过程从”逐个尝试、失败就退”的 O(VE) 匈牙利算法，加速到 O(E√V) 的分层增广，并配合几何连通性判定，做出一个真正会算最优解的连连看 AI。
一、为什么”贪心消一对”必然失败
新手写连连看求解器，第一反应是”从左上角开始，能消就消”。这个策略在 8×8 棋盘上就已经不稳：某些消法会切断后续图案之间的连通通道，导致剩下两个同图案格子被”墙”隔开，永远无法相连。
举个具体反例：棋盘上四个 A 组成一个”L”形，中间被一块 B 挡住。先消掉 A 的左右两个，剩下的 A 就被 B 与自身余下的对手堵死；可是若先消 A 的上下两个，B 消掉后另一对 A 反而能连通。局部贪心没有全局视野——它只看眼前这一对能否连通，不看消完之后剩下什么。
正确解法是把问题交给匹配算法：先枚举所有”几何上可连通”的同图案配对，生成二分图，再求最大匹配。只要匹配数是格子总数的一半，就存在全消顺序。
二、几何判定：最多两次拐弯的折线
连连看的连通规则是”折线转弯次数 ≤ 2″。等价表述有三种，实现时可以用同一套技巧——把路径分解成”直线”与”一次拐弯”的组合：
- 0 次拐弯：同行或同列之间全空；
- 1 次拐弯：两点之间存在一个公共拐点 (r1,c2) 或 (r2,c1)，且该点为空、两段直线均无阻挡；
- 2 次拐弯：两点各自向四个方向”射出”一条射线，射线经过的空格叫候选拐点；若存在一对候选拐点在同一行或同一列且其间无阻挡，则 2 次拐弯可达。
也可以用 BFS 做判定，但代价会抬到 O(棋盘面积)；而上述”射线枚举”在 12×12 棋盘上最坏只有 4×4 对候选点，比全图 BFS 廉价得多。
/** 检查 (r1,c1)-(r2,c2) 能否"最多两次拐弯"连通 */
static boolean connectable(Board b, int r1, int c1, int r2, int c2) {
if (r1 == r2 && c1 == c2) return false;
if (b.at(r1, c1) == 0 || b.at(r2, c2) == 0) return false;
// 情形 1: 同一行/同一列, 中间全空
if (b.hasLine(r1, c1, r2, c2)) return true;
// 情形 2: 一次拐弯, 拐点 (r1,c2) 或 (r2,c1)
if (b.free(r1, c2) && b.hasLine(r1, c1, r1, c2) && b.hasLine(r1, c2, r2, c2)) return true;
if (b.free(r2, c1) && b.hasLine(r1, c1, r2, c1) && b.hasLine(r2, c1, r2, c2)) return true;
// 情形 3: 两次拐弯 —— 两点的射线成对比较
for (int[] p : b.rays(r1, c1))
for (int[] q : b.rays(r2, c2))
if ((p[0] == q[0] || p[1] == q[1]) && b.hasLine(p[0], p[1], q[0], q[1]))
return true;
return false;
}
其中 rays(r,c) 沿四个方向连续走空格，返回路径上所有空格坐标；hasLine 只检查两端之间（不含端点）是否全空。
有一个细节决定正确性：必须允许线走到棋盘外一圈。连连看允许折线绕出边界，如果棋盘不做外圈填充，大量标准的两拐弯走法会被误判为不可达。工程上的做法是把棋盘外围扩一圈虚拟空格（值 0），所有判定都在扩边后的数组上做。
三、二分图建模：把”配对”当作点
关键转换：不要把格子当作图上的点，而要把”一对潜在配对”当作待满足的需求。因为每个格子只能被消一次，真正的约束是”哪些配对之间互相冲突”。
按图案分组再二分的构造流程：
- 对每种图案，把它的 m 个格子按出现顺序编成 0..m-1；
- 偶数号归入左部 A，奇数号归入右部 B；
- 若 A 中格子 x 与 B 中格子 y 几何可连通，则连边；
- 求该子图的最大匹配，匹配数即该图案能消掉的配对数量。
之所以能”按图案拆成独立子问题”，是因为不同图案的格子值不同，配对绝不跨图案——全局解等于各图案最大匹配之和。这个洞察把图的规模从 O(N²) 压到 O(N²/图案数)，在图案种类多时收益极大。
四、Hopcroft-Karp：分层寻找最短增广路
匈牙利算法（DFS 单路增广）每次只找一条增广路，单次代价 O(E)，总代价 O(VE)。在 72 对的规模上够用，但连连看求解器往往要反复求解（可解性检测、难度评估、重排后验证），这时 O(VE) 就成了瓶颈。
Hopcroft-Karp 的改进只有一句话：每一轮同时找出极大的一组互不相交的最短增广路。实现分两步，BFS 分层 + DFS 沿层递增：
final class HopcroftKarp {
private final Bipartite bp;
private final int[] matchU, matchV, dist;
HopcroftKarp(Bipartite bp) {
this.bp = bp;
matchU = new int[bp.nU]; matchV = new int[bp.nV]; dist = new int[bp.nU];
Arrays.fill(matchU, -1); Arrays.fill(matchV, -1);
}
int maxMatching() {
int total = 0;
while (bfsLayers())
for (int u = 0; u < bp.nU; u++)
if (matchU[u] == -1 && dfsAugment(u)) total++;
return total;
}
/** 所有未匹配左点同时入队, 求最短增广路长度并标记层号 */
private boolean bfsLayers() {
Deque<Integer> q = new ArrayDeque<>();
for (int u = 0; u < bp.nU; u++) {
if (matchU[u] == -1) { dist[u] = 0; q.add(u); }
else dist[u] = -1;
}
boolean found = false;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : bp.adj[u]) {
int w = matchV[v];
if (w == -1) found = true; // 触到自由点: 存在增广路
else if (dist[w] == -1) { dist[w] = dist[u] + 1; q.add(w); }
}
}
return found;
}
/** 只沿"层号严格递增"的路径递归, 保证每轮走的都是同长度最短路 */
private boolean dfsAugment(int u) {
for (int v : bp.adj[u]) {
int w = matchV[v];
if (w == -1 || (dist[w] == dist[u] + 1 && dfsAugment(w))) {
matchU[u] = v; matchV[v] = u;
return true;
}
}
dist[u] = -1; // 本轮此点已废, 后续 DFS 不再访问
return false;
}
}
两个细节值得强调：
bfsLayers里所有未匹配左点都从距离 0 出发，才叫”并行”；如果只从第一个自由点出发，就退化成单路增广。dist[u] = -1这行是剪枝：本轮失败的左点在后续 DFS 里不可能成功，置为不可达能显著减少重复探索。
由于每轮增广路长度单调不减、且同长度的一批路互不相交，总轮数是 O(√V)，总和给出 O(E√V)。
五、从静态匹配到可执行消除序列
最大匹配只回答”存在可行配对集合”，而玩家需要的是逐个执行的顺序：某些配对在被其他格子阻挡之前无法连通。解决办法是”迭代 + 动态校验”：
- 用当前棋盘构造二分图，求最大匹配；
- 按匹配对逐个尝试消除，每次消除前用
connectable实时校验（棋盘已变）； - 若某对因阻挡消不掉，跳过并记为”待重试”；
- 若一轮下来一对都没消掉，用新棋盘重跑匹配（图已经变了），直到清空或彻底停滞。
这个循环最多重跑 O(k) 轮（k 为图案数），把”静态可行性”与”动态可达性”解耦，比贪心稳健得多。
六、完整工程实现
目录结构：
linkgame/
└── src/main/java/link/
├── Board.java # 扩边棋盘与连通性判定
├── Bipartite.java # 单图案子二分图
├── HopcroftKarp.java # 分层增广匹配
└── Solver.java # 主流程(含 main)
package link;
import java.util.*;
/** 棋盘: 0 为空, 正数为图案编号; 四周留一圈虚拟空格以支持绕边连线 */
final class Board {
final int rows, cols;
final int[][] g;
Board(int[][] grid) {
this.rows = grid.length;
this.cols = grid[0].length;
this.g = new int[rows + 2][cols + 2];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
g[r + 1][c + 1] = grid[r][c];
}
int at(int r, int c) { return g[r][c]; }
void clear(int r, int c) { g[r][c] = 0; }
boolean free(int r, int c){ return g[r][c] == 0; }
/** 两端之间(不含端点)是否全空; 不同行不同列时返回 false */
boolean hasLine(int r1, int c1, int r2, int c2) {
if (r1 == r2) {
for (int c = Math.min(c1, c2) + 1; c < Math.max(c1, c2); c++)
if (!free(r1, c)) return false;
return true;
}
if (c1 == c2) {
for (int r = Math.min(r1, r2) + 1; r < Math.max(r1, r2); r++)
if (!free(r, c1)) return false;
return true;
}
return false;
}
/** 从 (r,c) 沿四个方向走出的连续空格坐标(含扩边后的一圈虚拟空格) */
List<int[]> rays(int r, int c) {
List<int[]> out = new ArrayList<>();
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : dirs) {
int rr = r + d[0], cc = c + d[1];
while (rr >= 0 && rr <= rows + 1 && cc >= 0 && cc <= cols + 1
&& g[rr][cc] == 0) {
out.add(new int[]{rr, cc});
rr += d[0]; cc += d[1];
}
}
return out;
}
/** 最多两次拐弯的可连通判定 */
boolean connectable(int r1, int c1, int r2, int c2) {
if (r1 == r2 && c1 == c2) return false;
if (at(r1, c1) == 0 || at(r2, c2) == 0) return false;
if (hasLine(r1, c1, r2, c2)) return true; // 0 拐弯
if (free(r1, c2) && hasLine(r1, c1, r1, c2) && hasLine(r1, c2, r2, c2)) return true;
if (free(r2, c1) && hasLine(r1, c1, r2, c1) && hasLine(r2, c1, r2, c2)) return true;
for (int[] p : rays(r1, c1)) // 2 拐弯
for (int[] q : rays(r2, c2))
if ((p[0] == q[0] || p[1] == q[1]) && hasLine(p[0], p[1], q[0], q[1]))
return true;
return false;
}
}
/** 单个图案的子二分图 */
final class Bipartite {
final int nU, nV;
final List<Integer>[] adj;
@SuppressWarnings("unchecked")
Bipartite(int nU, int nV) {
this.nU = nU; this.nV = nV;
adj = new List[nU];
for (int i = 0; i < nU; i++) adj[i] = new ArrayList<>();
}
void addEdge(int u, int v) { adj[u].add(v); }
}
/** Hopcroft-Karp 分层增广 */
final class HopcroftKarp {
private final Bipartite bp;
private final int[] matchU, matchV, dist;
HopcroftKarp(Bipartite bp) {
this.bp = bp;
matchU = new int[bp.nU]; matchV = new int[bp.nV]; dist = new int[bp.nU];
Arrays.fill(matchU, -1); Arrays.fill(matchV, -1);
}
int maxMatching() {
int total = 0;
while (bfsLayers())
for (int u = 0; u < bp.nU; u++)
if (matchU[u] == -1 && dfsAugment(u)) total++;
return total;
}
private boolean bfsLayers() {
Deque<Integer> q = new ArrayDeque<>();
for (int u = 0; u < bp.nU; u++) {
if (matchU[u] == -1) { dist[u] = 0; q.add(u); } else dist[u] = -1;
}
boolean found = false;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : bp.adj[u]) {
int w = matchV[v];
if (w == -1) found = true;
else if (dist[w] == -1) { dist[w] = dist[u] + 1; q.add(w); }
}
}
return found;
}
private boolean dfsAugment(int u) {
for (int v : bp.adj[u]) {
int w = matchV[v];
if (w == -1 || (dist[w] == dist[u] + 1 && dfsAugment(w))) {
matchU[u] = v; matchV[v] = u;
return true;
}
}
dist[u] = -1;
return false;
}
int[] leftMatch() { return matchU; }
}
/** 主流程: 匹配 -> 动态校验消除 -> 停滞则重匹配 */
public final class Solver {
public static void main(String[] args) {
int[][] grid = {
{1, 2, 1, 3},
{2, 3, 0, 0},
{1, 0, 2, 1},
{3, 0, 3, 2},
};
Board b = new Board(grid);
int removed = 0, steps = 0;
while (true) {
boolean progress = false;
List<int[]> pairs = buildMatching(b); // 每轮重新匹配
for (int[] p : pairs) {
if (!b.connectable(p[0], p[1], p[2], p[3])) continue; // 动态校验
System.out.printf("第%d步: 消 (%d,%d)-(%d,%d) 值=%d%n",
++steps, p[0] - 1, p[1] - 1, p[2] - 1, p[3] - 1,
b.at(p[0], p[1]));
b.clear(p[0], p[1]);
b.clear(p[2], p[3]);
removed += 2;
progress = true;
}
if (!progress) break; // 停滞: 当前匹配下无可行消除
}
System.out.println("共消除 " + removed + " 格, 剩余 " + count(b) + " 格");
}
/** 按图案分组 -> 建二分图 -> Hopcroft-Karp -> 还原成坐标对 */
private static List<int[]> buildMatching(Board b) {
Map<Integer, List<int[]>> byValue = new HashMap<>();
for (int r = 0; r <= b.rows + 1; r++)
for (int c = 0; c <= b.cols + 1; c++)
if (b.at(r, c) != 0)
byValue.computeIfAbsent(b.at(r, c), k -> new ArrayList<>())
.add(new int[]{r, c});
List<int[]> result = new ArrayList<>();
for (List<int[]> cells : byValue.values()) {
int m = cells.size();
if (m < 2) continue;
int half = m / 2;
Bipartite bp = new Bipartite(half, half);
for (int i = 0; i < half; i++) // 偶数号 -> 左部
for (int j = 0; j < half; j++) { // 奇数号 -> 右部
int[] x = cells.get(2 * i), y = cells.get(2 * j + 1);
if (b.connectable(x[0], x[1], y[0], y[1]))
bp.addEdge(i, j);
}
int[] mu = new HopcroftKarp(bp).leftMatch();
for (int i = 0; i < half; i++)
if (mu[i] != -1) {
int[] x = cells.get(2 * i), y = cells.get(2 * mu[i] + 1);
result.add(new int[]{x[0], x[1], y[0], y[1]});
}
}
return result;
}
private static int count(Board b) {
int n = 0;
for (int[] row : b.g) for (int v : row) if (v != 0) n++;
return n;
}
}
buildMatching 里的分组是”按出现顺序 0..m-1 交替分两侧”，只要 m 为偶数就两侧数量相等；若某图案出现奇数个（非法棋盘），half 取整后自然丢弃多余的一个，不会数组越界。
七、复杂度与调优
设 N 为非空格子数、k 为图案数、单图案平均 m = N/k 个格子：
| 环节 | 复杂度 | 说明 |
|---|---|---|
| 连通判定 | O((rows+cols)²) | 2 拐弯最多 16 对射线 |
| 建边 | O(N·m) | 每图案内两两检测，是主要开销 |
| 匹配 | O(E√V)，E ≤ N·m/2，V ≈ N/2 | 优于匈牙利 O(VE) |
| 整体消除 | O(k · E√V) | k 轮重匹配上限 |
三个可落地的优化点：
- 缓存连通判定结果：
(r1,c1,r2,c2)排序后做 key 缓存，棋盘变化时才失效； - 按稀有图案优先建边：稀有图案（格子少）先消，棋盘更容易打开，迭代轮数显著下降；
- 连通性预筛：先用”是否被完全包围”的连通块分析把明显孤立的格子提前剔除，减少无效建边。
八、小结
连连看的三层结构值得记住：几何层把”最多两次拐弯”降解成射线枚举，匹配层用二分图把”能否消完”变成最大匹配，调度层用”匹配 → 动态校验 → 重试”把静态可行性转成可执行序列。而 Hopcroft-Karp 提供匹配层的最优复杂度——分层 BFS 找出同长度的最短增广路，DFS 只沿层号递增的路径递归，两轮交替得到 O(E√V)。把三层各自独立看待，换掉任何一层（用 A* 找连通路径、用 KM 求带权最优配对）都不影响其他两层，这也正是这套实现的扩展价值所在。
