引言
连连看是一款广受欢迎的消除类益智游戏：玩家需要在一个布满图案的棋盘上，找出两个相同图案且能用不超过两个转弯的折线连接的方块，将它们消除。当棋盘上的图案成对且精心排布时，如何判断当前局面是否存在合法消除序列？如何在多步消除中避免陷入”死局”？这本质上是一个图匹配问题。本文用Java实现连连看的求解与判定算法，核心采用网络流最大匹配（Max-Flow）与最小割（Min-Cut）理论，将消除问题转化为二分图上的匹配问题，并通过残量网络分析判定死局。
问题建模
连连看规则的图论抽象
将棋盘上的每个图案视为图中的一个节点。对于当前局面上每一对相同图案，若它们之间存在合法路径（连线转角 ≤ 2），则在图中添加一条边。连连看的消除过程等价于：
– 选择一条边，移除其两个端点（消除一对图案）
– 重复上述过程，直到图中无边可选或所有节点被移除
转化为二分图匹配
将棋盘格子按坐标奇偶性分为两组（类似国际象棋棋盘的黑格与白格）：
– 左部（L）：(row + col) % 2 == 0 的格子
– 右部（R）：(row + col) % 2 == 1 的格子
任何合法消除连接的两个格子必然分属不同部（因为每步移动改变行列和的奇偶性），因此消除边构成一个二分图。问题转化为：在该二分图中寻找一个最大匹配，使得消除的图案对数最多。
最小割与死局判定
根据Konig定理，二分图最大匹配的边数等于最小点覆盖的大小。而最小点覆盖与最大独立集互补。若最大匹配的边数 × 2 < 剩余图案总数，则存在无法被匹配的孤立图案，当前局面必然为死局。
更进一步，通过最小割（Minimum Cut）分析残量网络，可以精确定位哪些图案是导致死局的”瓶颈”节点。
核心算法：Dinic最大流求解二分图匹配
算法思路
- 建图：
- 源点
S连接所有左部节点，容量为1 - 所有右部节点连接汇点
T，容量为1 - 每对可消除的相同图案之间建立有向边（左→右），容量为1
- Dinic算法：
- BFS分层：构建从源点到汇点的层次图
- DFS增广：在层次图上寻找阻塞流
- 重复直到无法增广
- 输出匹配：残量网络中容量为0的边即为匹配边
- 最小割恢复：从源点出发在残量网络中DFS/BFS，能到达的节点构成
S侧，其余为T侧，跨割边即为最小割
复杂度分析
- Dinic在二分图匹配上的时间复杂度为
O(E × √V)，其中V为节点数，E为边数 - 对于
m × n的棋盘，V = O(mn)，E = O(mn)，整体效率为O((mn)^1.5) - 空间复杂度：
O(V + E)
Java完整实现
import java.util.*;
/**
* 连连看：网络流最大匹配与最小割消除策略
*
* 核心思路：
* 1. 将棋盘按坐标奇偶性分为二分图左右两部
* 2. 对每对相同且可连通的图案建立二分图边
* 3. 使用Dinic最大流算法求解最大匹配
* 4. 通过残量网络的最小割定位死局瓶颈节点
* 5. 提供路径搜索（BFS）验证两图案间是否可连通消除
*/
public class LinkGameMaxFlow {
static final int[] DX = {-1, 1, 0, 0};
static final int[] DY = {0, 0, -1, 1};
static final int EMPTY = 0; // 空白格标记
// ============ Dinic算法数据结构 ============
static class Edge {
int to, rev, cap;
public Edge(int to, int rev, int cap) {
this.to = to;
this.rev = rev;
this.cap = cap;
}
}
static class Dinic {
int N;
List<List<Edge>> G;
int[] level, iter;
public Dinic(int N) {
this.N = N;
this.G = new ArrayList<>();
for (int i = 0; i < N; i++) G.add(new ArrayList<>());
this.level = new int[N];
this.iter = new int[N];
}
/** 添加有向边 */
public void addEdge(int from, int to, int cap) {
G.get(from).add(new Edge(to, G.get(to).size(), cap));
G.get(to).add(new Edge(from, G.get(from).size() - 1, 0)); // 反向边
}
/** BFS构建层次图 */
public boolean bfs(int s, int t) {
Arrays.fill(level, -1);
Queue<Integer> q = new LinkedList<>();
level[s] = 0;
q.offer(s);
while (!q.isEmpty()) {
int v = q.poll();
for (Edge e : G.get(v)) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.offer(e.to);
}
}
}
return level[t] >= 0;
}
/** DFS在层次图上寻找增广路 */
public int dfs(int v, int t, int f) {
if (v == t) return f;
for (int i = iter[v]; i < G.get(v).size(); i++) {
Edge e = G.get(v).get(i);
if (e.cap > 0 && level[v] < level[e.to]) {
int d = dfs(e.to, t, Math.min(f, e.cap));
if (d > 0) {
e.cap -= d;
G.get(e.to).get(e.rev).cap += d;
return d;
}
}
iter[v]++;
}
return 0;
}
/** 求解最大流 */
public int maxFlow(int s, int t) {
int flow = 0;
final int INF = Integer.MAX_VALUE;
while (bfs(s, t)) {
Arrays.fill(iter, 0);
int f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
/** 获取最小割的S侧节点（从源点在残量网络上BFS） */
public boolean[] minCutS(int s) {
boolean[] vis = new boolean[N];
Queue<Integer> q = new LinkedList<>();
vis[s] = true;
q.offer(s);
while (!q.isEmpty()) {
int v = q.poll();
for (Edge e : G.get(v)) {
if (e.cap > 0 && !vis[e.to]) {
vis[e.to] = true;
q.offer(e.to);
}
}
}
return vis;
}
}
// ============ 连连看游戏类 ============
private int rows, cols;
private int[][] board; // 棋盘图案编号，0表示空白
private int patternTypes; // 图案种类数
public LinkGameMaxFlow(int rows, int cols, int patternTypes) {
this.rows = rows;
this.cols = cols;
this.patternTypes = patternTypes;
this.board = new int[rows][cols];
}
public void setBoard(int[][] b) {
for (int i = 0; i < rows; i++) {
System.arraycopy(b[i], 0, board[i], 0, cols);
}
}
public int[][] getBoard() { return board; }
/** 将二维坐标映射为一维ID */
private int nodeId(int r, int c) {
return r * cols + c;
}
/**
* BFS判断两个格子是否可通过不超过2个转弯的路径连接
* 连连看规则：路径只能经过空白格（0），且转角次数≤2
*/
public boolean canConnect(int r1, int c1, int r2, int c2) {
if (board[r1][c1] != board[r2][c2] || board[r1][c1] == EMPTY) {
return false;
}
if (r1 == r2 && c1 == c2) return false;
// BFS状态: (r, c, direction, turns)
// direction: 0=上,1=下,2=左,3=右,4=起始
boolean[][][][] vis = new boolean[rows][cols][5][3]; // turns最多2
ArrayDeque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{r1, c1, 4, 0}); // 起点方向为4（无方向），转角0
vis[r1][c1][4][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], dir = cur[2], turns = cur[3];
for (int d = 0; d < 4; d++) {
int nr = r + DX[d], nc = c + DY[d];
int nTurns = turns;
if (dir != 4 && dir != d) nTurns++; // 转弯
if (nTurns > 2) continue;
while (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (nr == r2 && nc == c2) {
return true; // 到达目标
}
if (board[nr][nc] != EMPTY) break; // 遇到非空白格阻挡
if (!vis[nr][nc][d][nTurns]) {
vis[nr][nc][d][nTurns] = true;
q.offer(new int[]{nr, nc, d, nTurns});
}
nr += DX[d];
nc += DY[d];
}
}
}
return false;
}
/**
* 构建二分图并求解最大匹配
* @return 包含最大匹配数、匹配对列表、是否可完全消除、死局节点的结果
*/
public MatchResult solveMaxMatching() {
// 统计非空节点并分配左右部编号
int totalNodes = rows * cols;
int[] leftId = new int[totalNodes]; // 原始节点ID -> 左部局部ID（-1表示不在左部）
int[] rightId = new int[totalNodes]; // 原始节点ID -> 右部局部ID（-1表示不在右部）
Arrays.fill(leftId, -1);
Arrays.fill(rightId, -1);
List<int[]> leftNodes = new ArrayList<>(); // (r, c)
List<int[]> rightNodes = new ArrayList<>(); // (r, c)
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == EMPTY) continue;
int id = nodeId(r, c);
if ((r + c) % 2 == 0) {
leftId[id] = leftNodes.size();
leftNodes.add(new int[]{r, c});
} else {
rightId[id] = rightNodes.size();
rightNodes.add(new int[]{r, c});
}
}
}
int L = leftNodes.size();
int R = rightNodes.size();
int S = L + R;
int T = S + 1;
Dinic dinic = new Dinic(T + 1);
// 源点->左部
for (int i = 0; i < L; i++) {
dinic.addEdge(S, i, 1);
}
// 右部->汇点
for (int i = 0; i < R; i++) {
dinic.addEdge(L + i, T, 1);
}
// 左部->右部的可消除边
for (int i = 0; i < L; i++) {
int[] a = leftNodes.get(i);
for (int j = 0; j < R; j++) {
int[] b = rightNodes.get(j);
if (board[a[0]][a[1]] == board[b[0]][b[1]] && canConnect(a[0], a[1], b[0], b[1])) {
dinic.addEdge(i, L + j, 1);
}
}
}
int maxMatch = dinic.maxFlow(S, T);
// 恢复匹配对：检查左部到右部的边，cap为0表示被使用
List<int[]> matches = new ArrayList<>();
for (int i = 0; i < L; i++) {
for (Dinic.Edge e : dinic.G.get(i)) {
if (e.to >= L && e.to < L + R && e.cap == 0) {
int[] a = leftNodes.get(i);
int[] b = rightNodes.get(e.to - L);
matches.add(new int[]{nodeId(a[0], a[1]), nodeId(b[0], b[1])});
}
}
}
// 最小割定位死局节点
boolean[] sSide = dinic.minCutS(S);
List<int[]> bottleneck = new ArrayList<>();
int totalPatterns = L + R;
boolean solvable = (maxMatch * 2 == totalPatterns);
if (!solvable) {
// S侧中未匹配的左部节点 + T侧中未匹配的右部节点 = 瓶颈
for (int i = 0; i < L; i++) {
if (sSide[i]) { // 在S侧
boolean matched = false;
for (Dinic.Edge e : dinic.G.get(i)) {
if (e.to >= L && e.to < L + R && e.cap == 0) { matched = true; break; }
}
if (!matched) bottleneck.add(leftNodes.get(i));
}
}
for (int j = 0; j < R; j++) {
if (!sSide[L + j]) { // 在T侧
boolean matched = false;
for (Dinic.Edge e : dinic.G.get(L + j)) {
if (e.to == T && e.cap == 0) { matched = true; break; }
}
if (!matched) {
// 需要检查是否确实有连向S侧的边但容量为1（未匹配）
boolean hasUnsatEdge = false;
for (Dinic.Edge e : dinic.G.get(L + j)) {
if (e.to < L && e.cap == 1) { hasUnsatEdge = true; break; }
}
if (hasUnsatEdge) bottleneck.add(rightNodes.get(j));
}
}
}
}
return new MatchResult(maxMatch, matches, solvable, bottleneck, totalPatterns);
}
/** 执行一次消除：移除匹配对中的两个图案 */
public void eliminate(int id1, int id2) {
int r1 = id1 / cols, c1 = id1 % cols;
int r2 = id2 / cols, c2 = id2 % cols;
board[r1][c1] = EMPTY;
board[r2][c2] = EMPTY;
}
/** 打印棋盘 */
public void printBoard() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == EMPTY) System.out.print(" . ");
else System.out.printf("%3d ", board[r][c]);
}
System.out.println();
}
}
// ============ 结果类 ============
static class MatchResult {
int maxMatch; // 最大匹配数
List<int[]> matches; // 匹配对列表
boolean fullySolvable; // 是否能完全消除
List<int[]> bottlenecks; // 死局瓶颈节点
int totalPatterns; // 总图案数
public MatchResult(int maxMatch, List<int[]> matches, boolean fullySolvable,
List<int[]> bottlenecks, int totalPatterns) {
this.maxMatch = maxMatch;
this.matches = matches;
this.fullySolvable = fullySolvable;
this.bottlenecks = bottlenecks;
this.totalPatterns = totalPatterns;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("最大匹配数: ").append(maxMatch).append(" / ").append(totalPatterns / 2).append("\n");
sb.append("可完全消除: ").append(fullySolvable).append("\n");
sb.append("匹配对数: ").append(matches.size()).append("\n");
if (!fullySolvable) {
sb.append("死局瓶颈节点: ").append(bottlenecks.size()).append(" 个\n");
}
return sb.toString();
}
}
// ============ 主程序 ============
public static void main(String[] args) {
// 6×6棋盘，使用6种图案
int[][] initBoard = {
{1, 2, 3, 4, 5, 6},
{2, 1, 4, 3, 6, 5},
{3, 4, 5, 6, 1, 2},
{4, 3, 6, 5, 2, 1},
{5, 6, 1, 2, 3, 4},
{6, 5, 2, 1, 4, 3}
};
LinkGameMaxFlow game = new LinkGameMaxFlow(6, 6, 6);
game.setBoard(initBoard);
System.out.println("=== 连连看：网络流最大匹配与最小割 ===\n");
System.out.println("初始棋盘:");
game.printBoard();
System.out.println();
// 求解当前局面的最大匹配
MatchResult result = game.solveMaxMatching();
System.out.println(result);
// 演示消除过程
int step = 1;
while (!result.fullySolvable && result.maxMatch > 0) {
// 执行一个匹配对的消除
int[] pair = result.matches.get(0);
int r1 = pair[0] / 6, c1 = pair[0] % 6;
int r2 = pair[1] / 6, c2 = pair[1] % 6;
System.out.printf("步骤%d: 消除 (%d,%d)[%d] 与 (%d,%d)[%d]\n",
step++, r1, c1, initBoard[r1][c1], r2, c2, initBoard[r2][c2]);
game.eliminate(pair[0], pair[1]);
result = game.solveMaxMatching();
if (result.maxMatch == 0) break;
}
System.out.println("\n消除后剩余棋盘:");
game.printBoard();
System.out.println("\n最终状态: " + (result.fullySolvable ? "全部消除！" : "存在死局，无法继续消除。"));
// 演示路径连通性检查
System.out.println("\n【路径连通性测试】");
int[][] testBoard = {
{1, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
game.setBoard(testBoard);
boolean connected = game.canConnect(0, 0, 0, 5);
System.out.printf("(0,0)与(0,5)的1号图案可连通: %s (直线，0个转弯)\n", connected);
int[][] testBoard2 = {
{1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1}
};
game.setBoard(testBoard2);
boolean connected2 = game.canConnect(0, 0, 5, 5);
System.out.printf("(0,0)与(5,5)的1号图案可连通: %s (需要2个转弯的折线)\n", connected2);
}
}
关键代码解析
1. BFS路径连通性验证
while (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
if (nr == r2 && nc == c2) return true;
if (board[nr][nc] != EMPTY) break;
// ...
nr += DX[d]; nc += DY[d];
}
连连看的核心规则是”直线延伸+最多两次转弯”。代码采用多源BFS，每个状态记录当前方向和已用转弯数。沿当前方向直线滑动直到遇到边界或非空白格，在每个可停留的空白格处尝试向其他方向转弯（若转弯次数未超限）。
2. Dinic最大流算法
while (bfs(s, t)) {
Arrays.fill(iter, 0);
while ((f = dfs(s, t, INF)) > 0) flow += f;
}
Dinic通过BFS分层+DFS阻塞流的组合，在二分图匹配场景下达到 O(E × √V) 的优秀复杂度。相比匈牙利算法的 O(VE)，Dinic在大规模棋盘上具有显著速度优势。
3. 最小割死局判定
boolean[] sSide = dinic.minCutS(S);
最大流完成后，在残量网络中从源点进行BFS，所有可达节点属于最小割的 S 侧。根据最大流最小割定理，跨割的边即为限制匹配大小的瓶颈。未匹配且位于错误割侧的节点，就是导致死局的关键图案。
扩展思考
- 带权匹配：若不同图案的消除分值不同，可将边容量设为图案分值，转化为最大权匹配问题，需用费用流（Min-Cost Max-Flow）求解
- 多步前瞻：当前算法只评估当前局面的最大匹配，实际游戏中可通过递归消除评估多步后的死局概率，引入蒙特卡洛树搜索（MCTS）进行长程规划
- 提示系统设计：当玩家请求提示时，计算当前最大匹配并随机返回一条匹配边，保证提示一定有效（不会引入死局）
总结
本文以连连看游戏为载体，将消除问题转化为二分图最大匹配，并使用Dinic网络流算法高效求解。核心贡献包括：
– 基于坐标奇偶性的二分图建模方法
– BFS验证不超过2个转弯的连通路径
– 利用最大流-最小割定理进行死局判定与瓶颈定位
该框架适用于所有基于配对消除的益智游戏（如麻将消消乐、动物连连看），也可扩展至资源分配、任务调度等经典二分图匹配场景。
