对对碰是一款经典的消除类益智游戏，玩家需要在棋盘上找出两个可以通过不超过两次转折相连的相同图案进行消除，直到所有图案被清空。本文将用Java完整实现对对碰游戏的核心算法，重点讲解BFS连通路径检测、匹配判定与贪心消除策略，帮助读者掌握图搜索与状态空间优化技巧。
一、游戏规则与算法建模
对对碰的核心规则可归纳为三点：
- 选择两个相同图案的方块；
- 两个方块之间的连线转折次数不超过两次；
- 连线不能穿过未消除的方块。
从算法角度，我们可以将棋盘建模为一个二维网格图，每个格子是一个节点。两个格子能否消除，等价于在网格图中寻找一条满足约束的最短路径——路径的转折次数不超过2，且只能经过空格子（已消除的位置）或路径的两个端点。
二、BFS连通路径检测
判断两个方块是否可以消除，是游戏的核心算法问题。我们采用BFS（广度优先搜索）来寻找满足条件的路径。为了在搜索过程中记录转折次数，每个搜索状态需要包含当前坐标、当前方向以及已经转折的次数。
import java.util.*;
/**
* 对对碰游戏核心算法实现
* 包含BFS连通检测与贪心消除策略
*/
public class LinkLinkGame {
// 棋盘行数和列数
private static final int ROWS = 8;
private static final int COLS = 8;
// 四个方向：上、右、下、左
private static final int[][] DIRS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
// 棋盘状态，0表示空，其他数字表示不同图案
private int[][] board;
public LinkLinkGame() {
this.board = new int[ROWS][COLS];
}
/**
* 判断两个位置是否可以连通消除
* 使用BFS搜索，限制转折次数不超过2次
*
* @param r1 第一个点的行
* @param c1 第一个点的列
* @param r2 第二个点的行
* @param c2 第二个点的列
* @return 如果可以连通则返回路径，否则返回null
*/
public List<int[]> findPath(int r1, int c1, int r2, int c2) {
// 边界检查
if (!inBounds(r1, c1) || !inBounds(r2, c2)) {
return null;
}
// 必须是相同图案且非空
if (board[r1][c1] == 0 || board[r1][c1] != board[r2][c2]) {
return null;
}
// BFS队列：每个元素为 {row, col, direction, turnCount, parentIndex}
// direction: 0-3表示四个方向，-1表示起点无方向
Queue<Node> queue = new LinkedList<>();
// visited[r][c][dir] 表示从某个方向到达(r,c)时的最小转折次数
int[][][] visited = new int[ROWS][COLS][4];
for (int[][] arr2 : visited) {
for (int[] arr1 : arr2) {
Arrays.fill(arr1, Integer.MAX_VALUE);
}
}
// 从起点向四个方向扩展
List<Node> allNodes = new ArrayList<>();
for (int d = 0; d < 4; d++) {
int nr = r1 + DIRS[d][0];
int nc = c1 + DIRS[d][1];
if (canPass(nr, nc) || (nr == r2 && nc == c2)) {
Node node = new Node(nr, nc, d, 0, -1);
queue.offer(node);
allNodes.add(node);
visited[nr][nc][d] = 0;
}
}
while (!queue.isEmpty()) {
Node cur = queue.poll();
// 到达终点
if (cur.r == r2 && cur.c == c2 && cur.turns <= 2) {
return reconstructPath(allNodes, cur);
}
// 向四个方向扩展
for (int d = 0; d < 4; d++) {
int nr = cur.r + DIRS[d][0];
int nc = cur.c + DIRS[d][1];
// 计算新的转折次数
int newTurns = cur.turns + (d == cur.dir ? 0 : 1);
if (newTurns > 2) {
continue; // 转折次数超过2次，剪枝
}
// 检查是否可以经过该位置
if (!canPass(nr, nc) && !(nr == r2 && nc == c2)) {
continue;
}
// 如果从这个方向到达该位置的最小转折次数已经被更小的值访问过，则跳过
if (newTurns >= visited[nr][nc][d]) {
continue;
}
visited[nr][nc][d] = newTurns;
Node next = new Node(nr, nc, d, newTurns, allNodes.indexOf(cur));
queue.offer(next);
allNodes.add(next);
}
}
return null; // 未找到可行路径
}
/**
* 重构路径
*/
private List<int[]> reconstructPath(List<Node> nodes, Node end) {
List<int[]> path = new ArrayList<>();
Node cur = end;
while (cur != null) {
path.add(new int[]{cur.r, cur.c});
if (cur.parentIdx == -1) {
break;
}
cur = nodes.get(cur.parentIdx);
}
Collections.reverse(path);
return path;
}
/**
* 判断位置是否在棋盘范围内
*/
private boolean inBounds(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS;
}
/**
* 判断位置是否可以通过（在范围内且为空）
*/
private boolean canPass(int r, int c) {
return inBounds(r, c) && board[r][c] == 0;
}
/**
* BFS搜索节点
*/
private static class Node {
int r, c; // 坐标
int dir; // 到达该点的方向
int turns; // 转折次数
int parentIdx; // 父节点在allNodes中的索引
Node(int r, int c, int dir, int turns, int parentIdx) {
this.r = r;
this.c = c;
this.dir = dir;
this.turns = turns;
this.parentIdx = parentIdx;
}
}
/**
* 设置棋盘状态
*/
public void setBoard(int[][] board) {
this.board = board;
}
/**
* 打印棋盘
*/
public void printBoard() {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
System.out.printf("%3d", board[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
LinkLinkGame game = new LinkLinkGame();
// 构造测试棋盘：0表示空，1-6表示不同图案
int[][] testBoard = {
{1, 2, 3, 4, 5, 6, 1, 2},
{3, 4, 5, 6, 0, 0, 3, 4},
{5, 6, 1, 2, 3, 4, 5, 6},
{0, 0, 0, 0, 0, 0, 0, 0},
{1, 2, 3, 4, 5, 6, 1, 2},
{3, 4, 5, 6, 0, 0, 3, 4},
{5, 6, 1, 2, 3, 4, 5, 6},
{1, 2, 3, 4, 5, 6, 1, 2}
};
game.setBoard(testBoard);
System.out.println("初始棋盘：");
game.printBoard();
// 测试连通：(0,0)和(0,6)都是图案1
List<int[]> path = game.findPath(0, 0, 0, 6);
if (path != null) {
System.out.println("找到连通路径，共" + path.size() + "个点：");
for (int[] p : path) {
System.out.print("(" + p[0] + "," + p[1] + ") ");
}
System.out.println();
} else {
System.out.println("无法连通！");
}
}
}
三、贪心消除策略
在实现单对连通检测后，我们需要解决”先消除哪一对”的问题。对对碰存在无解的情况，合理的消除顺序会影响游戏能否通关。这里采用贪心策略：每次选择消除后”释放”最多潜在匹配的对。
/**
* 贪心策略：寻找当前最优消除对
* 优先选择消除后能为其他图案创造更多连通机会的对
*/
public int[] findBestMatch() {
int bestScore = -1;
int[] bestPair = null;
// 遍历所有相同图案的位置对
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++) {
for (int c2 = (r2 == r1 ? c1 + 1 : 0); c2 < COLS; c2++) {
if (board[r2][c2] != board[r1][c1]) continue;
List<int[]> path = findPath(r1, c1, r2, c2);
if (path == null) continue;
// 评估消除这对后的局面得分
int score = evaluateElimination(r1, c1, r2, c2);
if (score > bestScore) {
bestScore = score;
bestPair = new int[]{r1, c1, r2, c2};
}
}
}
}
}
return bestPair;
}
/**
* 评估消除某一对后的局面得分
* 得分越高表示越有利于后续消除
*/
private int evaluateElimination(int r1, int c1, int r2, int c2) {
// 临时消除
int val = board[r1][c1];
board[r1][c1] = 0;
board[r2][c2] = 0;
int score = 0;
// 统计消除后新增的可匹配对数
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (board[i][j] == 0) continue;
for (int x = i; x < ROWS; x++) {
for (int y = (x == i ? j + 1 : 0); y < COLS; y++) {
if (board[x][y] != board[i][j]) continue;
if (findPath(i, j, x, y) != null) {
score++;
}
}
}
}
}
// 恢复棋盘
board[r1][c1] = val;
board[r2][c2] = val;
return score;
}
四、自动求解器
将上述模块组合，实现一个自动求解器：
/**
* 自动求解对对碰
* @return 消除步骤列表
*/
public List<int[]> autoSolve() {
List<int[]> steps = new ArrayList<>();
while (true) {
int[] pair = findBestMatch();
if (pair == null) {
break; // 无解或已完成
}
// 执行消除
board[pair[0]][pair[1]] = 0;
board[pair[2]][pair[3]] = 0;
steps.add(pair);
// 检查是否全部消除
boolean allClear = true;
for (int[] row : board) {
for (int cell : row) {
if (cell != 0) {
allClear = false;
break;
}
}
}
if (allClear) break;
}
return steps;
}
五、复杂度分析
- BFS连通检测：最坏情况下搜索整个棋盘，时间复杂度为O(ROWS × COLS × 4)，空间复杂度为O(ROWS × COLS × 4)。由于棋盘大小固定为8×8，实际运行效率很高。
- 贪心消除策略：需要遍历所有位置对并评估，时间复杂度为O((ROWS × COLS)² × BFS代价)，适合小规模棋盘。
- 整体求解：最多消除(ROWS × COLS)/2对，总复杂度在可接受范围内。
六、总结
本文完整实现了对对碰游戏的核心算法，重点展示了：
- BFS路径搜索：通过状态扩展记录方向与转折次数，精确判断两个方块是否可连通；
- 贪心策略：通过局面评估选择最优消除顺序，提高通关概率；
- 剪枝优化：转折次数超过2立即剪枝，减少无效搜索。
读者可以在此基础上扩展更多功能，如图案随机生成、死局自动重排、倒计时挑战等，进一步加深对图搜索与启发式策略的理解。
