连连看（Link Up / Onet）是经典的图案配对消除游戏：棋盘上随机分布若干成对图案，玩家需要在规定时间内找出所有可消除的相同图案对。两条连线转折不超过两次且路径上没有其他图案的图案对可以消除。本文将用 Java 将连连看可消除性判定问题建模为二分图最大匹配，通过匈牙利算法求解最优消除顺序，并分析可解性判定与策略优化。
一、问题分析与图论建模
1.1 游戏规则与路径判定
在标准连连看中，两个相同图案可以消除当且仅当：
- 两个图案相同
- 存在一条由水平或垂直线段组成的路径连接两者
- 路径的转折次数不超过 2 次（即最多 3 条线段）
- 路径经过的位置（除起点和终点外）必须是空的
1.2 二分图建模
将棋盘上的每种图案类型视为一个类别，所有可消除的图案对构成图中的边。消除策略的核心问题可以转化为：如何选择一个消除顺序，使得每一步都存在可消除的对，直到所有图案被消除或无法继续。
更进一步，对于同类型图案，我们可以构建一个二分图：
- 左部：该类型图案的所有位置
- 右部：该类型图案的所有位置（副本）
- 边：如果两个位置可以连通（转折 ≤ 2），则连边
该二分图的最大匹配给出了这种图案类型最多能消除多少对。如果所有类型的最大匹配之和等于总图案数的一半，则游戏有解。
二、Java 实现
2.1 棋盘表示与路径搜索
import java.util.*;
/**
* 连连看游戏核心：棋盘表示与路径搜索
*/
public class LinkUpBoard {
public static final int EMPTY = 0; // 空位
public static final int BLOCKED = -1; // 障碍（棋盘边界扩展用）
private int rows, cols;
private int[][] board; // 0表示空，正整数表示图案类型
public LinkUpBoard(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.board = new int[rows][cols];
}
public void setCell(int r, int c, int type) {
board[r][c] = type;
}
public int getCell(int r, int c) {
return board[r][c];
}
/**
* 方向向量：上、下、左、右
*/
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
/**
* BFS搜索从(r1,c1)到(r2,c2)的最短路径（转折次数最少）
* 返回路径的转折次数，若无法到达或转折>2则返回-1
*
* 状态设计：(r, c, direction, turns)
* direction: 0=上, 1=下, 2=左, 3=右, -1=起点
*/
public int findMinTurns(int r1, int c1, int r2, int c2) {
if (board[r1][c1] != board[r2][c2] || board[r1][c1] == EMPTY) {
return -1;
}
if (r1 == r2 && c1 == c2) return 0;
// visited[r][c][dir] = 到达(r,c)且最后方向为dir的最小转折数
int[][][] visited = new int[rows][cols][4];
for (int[][] arr2 : visited) {
for (int[] arr : arr2) {
Arrays.fill(arr, Integer.MAX_VALUE);
}
}
ArrayDeque<int[]> queue = new ArrayDeque<>();
// 从四个方向初始化起点
for (int d = 0; d < 4; d++) {
int nr = r1 + DIRS[d][0];
int nc = c1 + DIRS[d][1];
if (isValid(nr, nc) && board[nr][nc] == EMPTY) {
visited[nr][nc][d] = 0;
queue.offer(new int[]{nr, nc, d, 0});
}
}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int r = cur[0], c = cur[1], dir = cur[2], turns = cur[3];
if (turns > 2) continue;
if (r == r2 && c == c2) return turns;
if (turns >= visited[r][c][dir]) continue;
visited[r][c][dir] = turns;
for (int nd = 0; nd < 4; nd++) {
int nr = r + DIRS[nd][0];
int nc = c + DIRS[nd][1];
int nTurns = turns + (nd == dir ? 0 : 1);
if (!isValid(nr, nc) || nTurns > 2) continue;
// 路径上的中间点必须是空的，终点可以是有图案的
if (!(nr == r2 && nc == c2) && board[nr][nc] != EMPTY) continue;
if (nTurns < visited[nr][nc][nd]) {
queue.offer(new int[]{nr, nc, nd, nTurns});
}
}
}
return -1;
}
/**
* 判断两个位置是否可以消除（转折<=2）
*/
public boolean canConnect(int r1, int c1, int r2, int c2) {
return findMinTurns(r1, c1, r2, c2) != -1;
}
/**
* 执行消除：将两个位置置为空
*/
public void remove(int r1, int c1, int r2, int c2) {
board[r1][c1] = EMPTY;
board[r2][c2] = EMPTY;
}
private boolean isValid(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
/**
* 打印棋盘状态
*/
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(" %d ", board[r][c]);
}
}
System.out.println();
}
}
/**
* 获取指定类型的所有位置
*/
public List<int[]> getPositions(int type) {
List<int[]> positions = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == type) {
positions.add(new int[]{r, c});
}
}
}
return positions;
}
public static void main(String[] args) {
LinkUpBoard board = new LinkUpBoard(6, 6);
// 构造测试棋盘
int[][] layout = {
{1, 2, 3, 4, 5, 6},
{7, 8, 1, 2, 3, 4},
{5, 6, 7, 8, 9, 9},
{1, 2, 3, 4, 5, 6},
{7, 8, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
for (int r = 0; r < 6; r++) {
for (int c = 0; c < 6; c++) {
board.setCell(r, c, layout[r][c]);
}
}
System.out.println("棋盘布局:");
board.printBoard();
System.out.println();
// 测试连通性
System.out.println("连通性测试:");
System.out.println("(0,0)=1 到 (1,2)=1: " + board.canConnect(0, 0, 1, 2));
System.out.println("(0,0)=1 到 (3,0)=1: " + board.canConnect(0, 0, 3, 0));
}
}
2.2 匈牙利算法求解二分图最大匹配
import java.util.*;
/**
* 匈牙利算法（DFS增广路版本）
* 用于求解二分图最大匹配
*/
public class HungarianAlgorithm {
private int nLeft, nRight;
private List<Integer>[] graph; // 左部点到右部点的邻接表
private int[] matchR; // 右部点匹配的左部点
private boolean[] visited;
@SuppressWarnings("unchecked")
public HungarianAlgorithm(int nLeft, int nRight) {
this.nLeft = nLeft;
this.nRight = nRight;
this.graph = new ArrayList[nLeft];
for (int i = 0; i < nLeft; i++) {
graph[i] = new ArrayList<>();
}
this.matchR = new int[nRight];
Arrays.fill(matchR, -1);
}
/**
* 添加边：左部点 u 与右部点 v 相连
*/
public void addEdge(int u, int v) {
graph[u].add(v);
}
/**
* DFS寻找增广路
*/
private boolean dfs(int u) {
for (int v : graph[u]) {
if (visited[v]) continue;
visited[v] = true;
// 如果v未匹配，或者v的匹配点可以找到新的匹配
if (matchR[v] == -1 || dfs(matchR[v])) {
matchR[v] = u;
return true;
}
}
return false;
}
/**
* 求解最大匹配
* 时间复杂度: O(V * E)，实际运行接近 O(E * sqrt(V))
* 空间复杂度: O(V + E)
*/
public int maxMatching() {
int matchCount = 0;
for (int u = 0; u < nLeft; u++) {
visited = new boolean[nRight];
if (dfs(u)) {
matchCount++;
}
}
return matchCount;
}
/**
* 获取匹配结果：返回左部点匹配的右部点
*/
public int[] getMatchL() {
int[] matchL = new int[nLeft];
Arrays.fill(matchL, -1);
for (int v = 0; v < nRight; v++) {
if (matchR[v] != -1) {
matchL[matchR[v]] = v;
}
}
return matchL;
}
public static void main(String[] args) {
// 测试：标准二分图匹配
HungarianAlgorithm ha = new HungarianAlgorithm(4, 4);
ha.addEdge(0, 0);
ha.addEdge(0, 1);
ha.addEdge(1, 1);
ha.addEdge(1, 2);
ha.addEdge(2, 2);
ha.addEdge(2, 3);
ha.addEdge(3, 3);
int match = ha.maxMatching();
System.out.println("最大匹配数: " + match);
int[] matchL = ha.getMatchL();
for (int i = 0; i < matchL.length; i++) {
if (matchL[i] != -1) {
System.out.println("左部 " + i + " <-> 右部 " + matchL[i]);
}
}
}
}
2.3 连连看求解器：匹配 + 消除策略
import java.util.*;
/**
* 连连看求解器：使用匈牙利算法分析可解性，配合贪心策略寻找消除顺序
*/
public class LinkUpSolver {
private LinkUpBoard board;
public LinkUpSolver(LinkUpBoard board) {
this.board = board;
}
/**
* 对指定图案类型构建二分图并求最大匹配
* 返回该类型可以消除的最大对数
*/
public int analyzeType(int type) {
List<int[]> positions = board.getPositions(type);
int n = positions.size();
if (n < 2) return 0;
// 构建二分图：将n个位置分为左右两部分
HungarianAlgorithm ha = new HungarianAlgorithm(n, n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int[] p1 = positions.get(i);
int[] p2 = positions.get(j);
if (board.canConnect(p1[0], p1[1], p2[0], p2[1])) {
// 在二分图中添加边（i与j匹配表示消除这一对）
// 注意：匈牙利算法要求左部和右部是不同集合
// 这里左部是位置0~n-1，右部也是位置0~n-1（副本）
ha.addEdge(i, j);
ha.addEdge(j, i);
}
}
}
return ha.maxMatching() / 2; // 每对被计算了两次
}
/**
* 判断当前棋盘是否完全可解
*/
public boolean isSolvable() {
// 统计每种图案的最大可消除对数
Set<Integer> types = new HashSet<>();
for (int r = 0; r < board.rows; r++) {
for (int c = 0; c < board.cols; c++) {
if (board.getCell(r, c) != LinkUpBoard.EMPTY) {
types.add(board.getCell(r, c));
}
}
}
int totalPairs = 0;
int maxEliminable = 0;
for (int type : types) {
List<int[]> positions = board.getPositions(type);
totalPairs += positions.size() / 2;
maxEliminable += analyzeType(type);
}
// 如果最大可消除对数等于总对数，理论上可解
// 注意：这只是一个必要条件，不是充分条件
// 因为不同图案类型的消除可能互相阻挡
return maxEliminable >= totalPairs;
}
/**
* 贪心策略：每一步寻找可消除的对并消除
* 优先选择"消除后开辟更多路径"的对
*/
public List<int[]> solveGreedy() {
List<int[]> moves = new ArrayList<>();
while (true) {
int[] bestMove = findBestMove();
if (bestMove == null) break;
moves.add(bestMove);
board.remove(bestMove[0], bestMove[1], bestMove[2], bestMove[3]);
}
return moves;
}
/**
* 寻找当前最优消除对
* 评分标准：消除该对后，剩余棋盘的可连通对数增加最多
*/
private int[] findBestMove() {
int[] bestMove = null;
int bestScore = -1;
Set<Integer> types = new HashSet<>();
for (int r = 0; r < board.rows; r++) {
for (int c = 0; c < board.cols; c++) {
if (board.getCell(r, c) != LinkUpBoard.EMPTY) {
types.add(board.getCell(r, c));
}
}
}
for (int type : types) {
List<int[]> positions = board.getPositions(type);
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 (board.canConnect(p1[0], p1[1], p2[0], p2[1])) {
// 评分：优先选择位于边缘、角落的图案对
// 这些位置通常更难消除
int score = evaluateMove(p1[0], p1[1], p2[0], p2[1]);
if (score > bestScore) {
bestScore = score;
bestMove = new int[]{p1[0], p1[1], p2[0], p2[1]};
}
}
}
}
}
return bestMove;
}
/**
* 评估消除操作的优先级
* 角落和边缘的图案优先级更高
*/
private int evaluateMove(int r1, int c1, int r2, int c2) {
int score = 0;
score += edgeBonus(r1, c1);
score += edgeBonus(r2, c2);
return score;
}
private int edgeBonus(int r, int c) {
int bonus = 0;
if (r == 0 || r == board.rows - 1) bonus += 10;
if (c == 0 || c == board.cols - 1) bonus += 10;
return bonus;
}
public static void main(String[] args) {
// 构造可解的测试棋盘
LinkUpBoard board = new LinkUpBoard(8, 8);
int[][] layout = {
{1, 2, 3, 4, 1, 2, 3, 4},
{5, 6, 7, 8, 5, 6, 7, 8},
{9, 10, 11, 12, 9, 10, 11, 12},
{1, 2, 3, 4, 1, 2, 3, 4},
{5, 6, 7, 8, 5, 6, 7, 8},
{9, 10, 11, 12, 9, 10, 11, 12},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0}
};
for (int r = 0; r < 8; r++) {
for (int c = 0; c < 8; c++) {
board.setCell(r, c, layout[r][c]);
}
}
System.out.println("=== 连连看求解器 ===\n");
System.out.println("初始棋盘:");
board.printBoard();
System.out.println();
LinkUpSolver solver = new LinkUpSolver(board);
// 分析各类型图案的可消除性
System.out.println("各类型图案分析:");
for (int type = 1; type <= 12; type++) {
List<int[]> pos = board.getPositions(type);
if (pos.size() >= 2) {
int maxPairs = solver.analyzeType(type);
System.out.printf(" 类型 %d: %d 个, 最大可消除 %d 对%n",
type, pos.size(), maxPairs);
}
}
System.out.println();
// 执行贪心求解
List<int[]> moves = solver.solveGreedy();
System.out.println("消除步骤数: " + moves.size());
System.out.println("\n剩余棋盘:");
board.printBoard();
}
}
2.4 可解性判定的完整算法
import java.util.*;
/**
* 连连看可解性判定：综合多种启发式规则
*/
public class LinkUpSolvabilityChecker {
/**
* 检查当前棋盘是否还有可消除的对
*/
public static boolean hasAnyMove(LinkUpBoard board) {
Set<Integer> types = new HashSet<>();
for (int r = 0; r < board.rows; r++) {
for (int c = 0; c < board.cols; c++) {
if (board.getCell(r, c) != LinkUpBoard.EMPTY) {
types.add(board.getCell(r, c));
}
}
}
for (int type : types) {
List<int[]> positions = board.getPositions(type);
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 (board.canConnect(p1[0], p1[1], p2[0], p2[1])) {
return true;
}
}
}
}
return false;
}
/**
* 死锁检测：如果某种图案只剩奇数个，则无法完全消除
*/
public static boolean hasOddCount(LinkUpBoard board) {
Map<Integer, Integer> count = new HashMap<>();
for (int r = 0; r < board.rows; r++) {
for (int c = 0; c < board.cols; c++) {
int type = board.getCell(r, c);
if (type != LinkUpBoard.EMPTY) {
count.merge(type, 1, Integer::sum);
}
}
}
for (int c : count.values()) {
if (c % 2 != 0) return true;
}
return false;
}
/**
* 综合可解性评估
* 返回 0~100 的分数，越高表示越可能可解
*/
public static int solvabilityScore(LinkUpBoard board) {
if (hasOddCount(board)) return 0;
int score = 100;
// 空位越多，越容易解
int emptyCount = 0;
int totalCells = board.rows * board.cols;
for (int r = 0; r < board.rows; r++) {
for (int c = 0; c < board.cols; c++) {
if (board.getCell(r, c) == LinkUpBoard.EMPTY) emptyCount++;
}
}
score = score * (emptyCount + totalCells) / (2 * totalCells);
return score;
}
public static void main(String[] args) {
LinkUpBoard board = new LinkUpBoard(6, 6);
int[][] layout = {
{1, 1, 2, 2, 3, 3},
{4, 4, 5, 5, 6, 6},
{1, 1, 2, 2, 3, 3},
{4, 4, 5, 5, 6, 6},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
for (int r = 0; r < 6; r++) {
for (int c = 0; c < 6; c++) {
board.setCell(r, c, layout[r][c]);
}
}
System.out.println("可解性评分: " + solvabilityScore(board));
System.out.println("是否存在可行移动: " + hasAnyMove(board));
System.out.println("是否存在奇数个图案: " + hasOddCount(board));
}
}
三、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 单对连通性判定（BFS） | O(rc) | O(rc) | r=行数, c=列数 |
| 某类型最大匹配 | O(n² × E) | O(n²) | n为该类型图案数 |
| 全棋盘可解性分析 | O(T × n² × E) | O(n²) | T为图案类型数 |
| 贪心求解 | O(k × T × n² × rc) | O(1) | k为消除步数 |
四、算法优化方向
- 预处理连通性：在游戏开始前预计算所有同类型图案对的连通性，避免重复BFS
- 增量更新：每次消除后，只更新受影响区域的连通性
- 启发式排序：优先消除边缘和角落的图案，这些位置的路径选择最少
- A*搜索消除顺序：将消除序列搜索建模为状态空间搜索，用启发函数指导
- 死锁避免：在生成关卡时，使用逆向构造法确保可解性
五、总结
本文从图论视角重新解读了连连看游戏，将消除可行性判定转化为二分图最大匹配问题。匈牙利算法虽然时间复杂度为 O(VE)，但对于连连看这种每类型图案数量有限的场景完全可行。实际游戏中，二分图分析主要用于关卡生成阶段的可解性验证，而运行时则配合贪心启发式快速响应玩家操作。读者可以在此基础上实现更智能的提示系统，或在关卡编辑器中集成可解性自动检测功能。
