贪吃蛇（Snake）是伴随无数人成长的经典街机游戏。与常见的A寻路或贪心策略不同，本文将探索一种理论上永不撞墙的终极解法——通过构建网格上的哈密顿回路（Hamiltonian Cycle），让蛇身沿着一条访问每个格子恰好一次并回到起点的闭合路径持续移动。无论蛇身多长，只要严格遵循回路，头部永远不会撞上自己的身体。文中还将引入动态捷径优化*，让AI在确保安全的前提下抄近路吃食物，大幅缩短游戏时长。
一、问题建模与核心思路
将游戏棋盘抽象为无向图：每个格子是一个节点，上下左右相邻的格子之间有边相连。贪吃蛇的躯体占据若干连续节点，食物随机出现在某个空闲节点上。
哈密顿回路定义为：经过图中每个节点恰好一次，并最终回到起点的闭合路径。若蛇头始终沿着哈密顿回路向前移动，由于蛇身各节也分布在回路上，且头部速度严格等于尾部”退场”速度，头部永远不会追上尾部——因为尾部刚离开的节点正是头部即将进入的下一个节点，中间永远隔着固定数量的已访问节点。
核心策略：
– 离线阶段：使用DFS回溯在网格上搜索一条哈密顿回路
– 在线阶段：蛇头沿回路方向移动，遇到食物时评估是否可安全偏离回路走捷径
– 安全性保证：任何捷径都必须确保捷径结束后仍能被回路”接回”，且不造成自撞
二、网格图与哈密顿回路的数据结构
import java.util.*;
/**
* 网格节点，表示棋盘上的一个格子
*/
class Cell {
final int row;
final int col;
// 在哈密顿回路中的下一个节点（循环链表结构）
Cell next;
// 在哈密顿回路中的序号（0 ~ rows*cols - 1）
int cycleIndex;
Cell(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Cell)) return false;
Cell cell = (Cell) o;
return row == cell.row && col == cell.col;
}
@Override
public int hashCode() {
return Objects.hash(row, col);
}
}
/**
* 贪吃蛇游戏核心引擎
* 包含棋盘状态、蛇身队列、哈密顿回路以及AI决策逻辑
*/
public class HamiltonianSnake {
// 棋盘尺寸
private final int rows;
private final int cols;
// 总格子数
private final int totalCells;
// 二维网格，存储每个格子的节点对象
private final Cell[][] grid;
// 记录每个格子是否在哈密顿回路中已确定连接关系
private final boolean[][] inCycle;
// 蛇身：用双端队列表示，头部在队尾，尾部在队首
private final ArrayDeque<Cell> snake;
// 记录每个格子当前是否被蛇身占据
private final boolean[][] occupied;
// 当前食物位置
private Cell food;
// 随机数生成器
private final Random random;
// 移动方向：上、下、左、右
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public HamiltonianSnake(int rows, int cols) {
if (rows < 2 || cols < 2 || (rows * cols) % 2 != 0) {
throw new IllegalArgumentException(
"哈密顿回路要求棋盘为偶数格（2xN或Mx2以上且总格数为偶数）");
}
this.rows = rows;
this.cols = cols;
this.totalCells = rows * cols;
this.grid = new Cell[rows][cols];
this.inCycle = new boolean[rows][cols];
this.occupied = new boolean[rows][cols];
this.snake = new ArrayDeque<>();
this.random = new Random();
// 初始化网格节点
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
grid[r][c] = new Cell(r, c);
}
}
// 构建哈密顿回路
buildHamiltonianCycle();
// 初始化蛇身：从回路起点开始，长度为1
Cell start = grid[0][0];
snake.addLast(start);
occupied[start.row][start.col] = true;
// 生成第一个食物
spawnFood();
}
三、DFS回溯构造哈密顿回路
在网格图中寻找哈密顿回路是NP完全问题，但对于小型矩形网格（如10×10以内），DFS回溯配合剪枝可在毫秒级完成。核心剪枝策略如下：
- 奇偶性剪枝：网格图是二分图，回路长度必须为偶数（总格数为偶数时才有可能）
- 邻居度剪枝：若某未访问节点的邻居中已访问节点过多，可能导致其后续无法被访问
- 提前失败检测：若某未访问区域被已访问节点完全包围，则不可能完成回路
/**
* 使用DFS回溯构建哈密顿回路
* 从(0,0)出发，尝试访问所有格子后回到起点
*/
private void buildHamiltonianCycle() {
List<Cell> path = new ArrayList<>();
boolean[][] visited = new boolean[rows][cols];
// 从左上角开始搜索
Cell start = grid[0][0];
visited[0][0] = true;
path.add(start);
if (!dfsHamiltonian(start, path, visited, 1)) {
throw new RuntimeException("无法在该尺寸棋盘上构建哈密顿回路");
}
// 将路径转换为循环链表结构
int index = 0;
for (int i = 0; i < path.size(); i++) {
Cell cur = path.get(i);
Cell nxt = path.get((i + 1) % path.size());
cur.next = nxt;
cur.cycleIndex = index++;
}
}
/**
* DFS递归搜索哈密顿回路
* @param current 当前所在节点
* @param path 当前已构建的路径
* @param visited 访问标记矩阵
* @param count 已访问节点数
* @return 是否成功找到回路
*/
private boolean dfsHamiltonian(Cell current, List<Cell> path,
boolean[][] visited, int count) {
// 终止条件：所有节点已访问，且当前节点与起点相邻（可闭合回路）
if (count == totalCells) {
return isAdjacent(current, grid[0][0]);
}
// 按启发式顺序尝试邻居：优先选择"最受限"的邻居（度数最小）
List<Cell> neighbors = getUnvisitedNeighbors(current, visited);
neighbors.sort(Comparator.comparingInt(c ->
countUnvisitedNeighbors(c, visited)));
for (Cell next : neighbors) {
// 剪枝：若将next加入路径后，存在不可达的未访问区域，则跳过
visited[next.row][next.col] = true;
path.add(next);
if (!hasUnreachableRegion(visited) &&
dfsHamiltonian(next, path, visited, count + 1)) {
return true;
}
// 回溯
path.remove(path.size() - 1);
visited[next.row][next.col] = false;
}
return false;
}
/**
* 检查是否存在被已访问节点完全包围的未访问区域
* 若存在，则后续无法完成哈密顿回路
*/
private boolean hasUnreachableRegion(boolean[][] visited) {
boolean[][] checked = new boolean[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (!visited[r][c] && !checked[r][c]) {
int regionSize = floodFillSize(r, c, visited, checked);
if (regionSize == 1) {
// 单个未访问节点若被已访问节点包围则无法接入回路
Cell isolated = grid[r][c];
int freeNeighbors = 0;
for (int[] d : DIRS) {
int nr = isolated.row + d[0];
int nc = isolated.col + d[1];
if (inBounds(nr, nc) && !visited[nr][nc]) {
freeNeighbors++;
}
}
if (freeNeighbors == 0) return true;
}
}
}
}
return false;
}
/**
* 洪水填充计算连通区域大小
*/
private int floodFillSize(int r, int c, boolean[][] visited, boolean[][] checked) {
if (!inBounds(r, c) || visited[r][c] || checked[r][c]) return 0;
checked[r][c] = true;
int size = 1;
for (int[] d : DIRS) {
size += floodFillSize(r + d[0], c + d[1], visited, checked);
}
return size;
}
/**
* 获取当前节点的所有未访问邻居
*/
private List<Cell> getUnvisitedNeighbors(Cell cell, boolean[][] visited) {
List<Cell> list = new ArrayList<>();
for (int[] d : DIRS) {
int nr = cell.row + d[0];
int nc = cell.col + d[1];
if (inBounds(nr, nc) && !visited[nr][nc]) {
list.add(grid[nr][nc]);
}
}
return list;
}
/**
* 计算某节点的未访问邻居数量（用于排序，优先扩展受限节点）
*/
private int countUnvisitedNeighbors(Cell cell, boolean[][] visited) {
int count = 0;
for (int[] d : DIRS) {
int nr = cell.row + d[0];
int nc = cell.col + d[1];
if (inBounds(nr, nc) && !visited[nr][nc]) count++;
}
return count;
}
private boolean isAdjacent(Cell a, Cell b) {
return Math.abs(a.row - b.row) + Math.abs(a.col - b.col) == 1;
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
四、蛇的移动、食物生成与占据管理
/**
* 在随机空闲位置生成食物
*/
private void spawnFood() {
List<Cell> freeCells = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (!occupied[r][c]) {
freeCells.add(grid[r][c]);
}
}
}
if (freeCells.isEmpty()) return; // 棋盘已满，游戏胜利
food = freeCells.get(random.nextInt(freeCells.size()));
}
/**
* 执行一步移动（由AI决策）
* @return 0=正常移动, 1=吃到食物, -1=撞墙/自撞（理论上不会发生）
*/
public int step() {
Cell head = snake.peekLast();
Cell nextMove = decideNextMove(head);
if (nextMove == null) {
return -1; // 无路可走（在哈密顿策略下不应出现）
}
// 检查是否吃到食物
boolean ateFood = nextMove.equals(food);
// 移动头部
snake.addLast(nextMove);
occupied[nextMove.row][nextMove.col] = true;
if (ateFood) {
// 吃到食物：不删除尾部，蛇身增长
spawnFood();
return 1;
} else {
// 未吃到食物：删除尾部，保持长度
Cell tail = snake.pollFirst();
occupied[tail.row][tail.col] = false;
return 0;
}
}
五、AI决策：回路跟随与动态捷径
纯粹的哈密顿回路策略虽然安全，但效率极低——蛇需要遍历几乎所有格子才能吃到食物。本节的动态捷径算法是性能提升的关键：
安全性判定：当蛇头位于节点A、食物位于节点F时，若沿回路从A到F的距离为D1，从F继续沿回路回到A（绕过蛇尾）的距离为D2，则只有当D1 > 蛇身长度时，沿回路前进吃食物才是绝对安全的（因为尾部会不断释放空间）。若D1 ≤ 蛇身长度，则头部可能在到达F之前追上尾部。
更实用的捷径策略：蛇头当前在节点H，回路下一节点为N。若存在一个邻居节点S（S≠N），使得：
1. S为空节点且不是蛇身
2. 从S沿回路到食物的距离更短
3. 走捷径后，蛇头仍能在尾部离开相应区域前被回路”接回”
则AI选择走捷径S。
/**
* AI决策下一移动位置
* 优先尝试走安全捷径，否则沿哈密顿回路前进
*/
private Cell decideNextMove(Cell head) {
// 策略1：尝试直接走向食物的捷径（若安全）
Cell shortcut = findSafeShortcut(head);
if (shortcut != null) {
return shortcut;
}
// 策略2：严格沿哈密顿回路前进（绝对安全）
return head.next;
}
/**
* 寻找安全的捷径
* 核心思想：若存在某邻居节点，从该节点沿回路到食物的距离
* 小于从当前回路下一节点沿回路到食物的距离，且不会造成自撞
*/
private Cell findSafeShortcut(Cell head) {
if (food == null) return null;
Cell cycleNext = head.next;
int distViaCycle = distanceOnCycle(cycleNext, food);
for (int[] d : DIRS) {
int nr = head.row + d[0];
int nc = head.col + d[1];
if (!inBounds(nr, nc)) continue;
Cell neighbor = grid[nr][nc];
// 不能是蛇身（除尾部外，因为尾部即将移动）
if (occupied[nr][nc] && !neighbor.equals(snake.peekFirst())) {
continue;
}
// 不能是回路下一节点（否则不算捷径）
if (neighbor.equals(cycleNext)) continue;
int distViaShortcut = distanceOnCycle(neighbor, food);
// 捷径必须比原回路更短
if (distViaShortcut >= distViaCycle) continue;
// 安全性检查：走捷径后，蛇头到达食物时，尾部是否已释放足够空间
// 简化判定：计算从neighbor沿回路到food的距离，必须小于当前尾部到food的回路距离
// 这确保头部不会比尾部更早进入同一区域
Cell tail = snake.peekFirst();
int tailToFood = distanceOnCycle(tail, food);
if (distViaShortcut < tailToFood) {
return neighbor;
}
}
return null;
}
/**
* 计算从起点到终点沿哈密顿回路的正向距离
* 假设回路是有向循环链表，沿next指针前进
*/
private int distanceOnCycle(Cell from, Cell to) {
int dist = 0;
Cell cur = from;
// 防止死循环
int maxSteps = totalCells;
while (!cur.equals(to) && maxSteps-- > 0) {
cur = cur.next;
dist++;
}
return dist;
}
六、控制台可视化与游戏循环
/**
* 打印当前棋盘状态到控制台
*/
public void printBoard() {
// 构建蛇身位置到符号的映射
char[][] display = new char[rows][cols];
for (int r = 0; r < rows; r++) {
Arrays.fill(display[r], '.');
}
// 标记蛇身：头部用'H'，身体用'o'，尾部用't'
int idx = 0;
for (Cell cell : snake) {
if (idx == 0) {
display[cell.row][cell.col] = 't';
} else if (idx == snake.size() - 1) {
display[cell.row][cell.col] = 'H';
} else {
display[cell.row][cell.col] = 'o';
}
idx++;
}
// 标记食物
if (food != null) {
display[food.row][food.col] = '*';
}
System.out.println("\n+" + "-".repeat(cols * 2 + 1) + "+");
for (int r = 0; r < rows; r++) {
System.out.print("| ");
for (int c = 0; c < cols; c++) {
System.out.print(display[r][c] + " ");
}
System.out.println("|");
}
System.out.println("+" + "-".repeat(cols * 2 + 1) + "+");
System.out.println("Score: " + (snake.size() - 1) + " / Target: " + (totalCells - 1));
}
/**
* 检查是否获胜（蛇身填满棋盘）
*/
public boolean isWin() {
return snake.size() == totalCells;
}
/**
* 获取当前蛇身长度
*/
public int getScore() {
return snake.size() - 1;
}
// ------------------- 主入口 -------------------
public static void main(String[] args) throws InterruptedException {
// 使用6x6棋盘演示（需保证总格数为偶数）
HamiltonianSnake game = new HamiltonianSnake(6, 6);
System.out.println("===== 哈密顿回路贪吃蛇 AI 演示 =====");
System.out.println("H=蛇头, o=蛇身, t=蛇尾, *=食物, .=空格");
game.printBoard();
int steps = 0;
while (!game.isWin()) {
int result = game.step();
if (result < 0) {
System.out.println("AI撞墙/自撞，游戏结束（理论上不会发生）");
break;
}
steps++;
// 每吃到食物或每20步刷新一次画面
if (result == 1 || steps % 20 == 0) {
Thread.sleep(80);
game.printBoard();
}
}
if (game.isWin()) {
System.out.println("\n恭喜！AI成功填满棋盘！总步数：" + steps);
}
}
}
七、复杂度分析
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 哈密顿回路构建 | O(4^(rows×cols)) 最坏情况 | DFS回溯，实际因剪枝在小型网格（≤10×10）可秒级完成 |
| 单次移动决策 | O(rows×cols) | 遍历四个方向邻居并计算回路距离 |
| 空间复杂度 | O(rows×cols) | 网格节点、访问标记、蛇身队列 |
| 单局总步数 | O(rows×cols) | 若全程走捷径，步数接近格子数；纯回路约(rows×cols)^2 |
八、算法延伸与变种
本文演示的哈密顿回路策略是贪吃蛇的理论最优安全策略，但实战中存在多种改进方向：
- 局部重路由：当食物恰好出现在蛇头前方附近时，可动态局部修改回路方向，而非坚持全局回路
- 双向哈密顿路径：不求回路而求起点到终点的哈密顿路径，省去”闭合”约束，搜索更快
- 机器学习方法：用强化学习训练神经网络判断何时该走捷径、何时该保守跟随回路，可在大棋盘上超越手工启发式
- 多蛇对抗：将哈密顿回路策略扩展到多条蛇共享棋盘的竞争场景，引入博弈论与领地划分
通过这个游戏实现，读者不仅能掌握DFS回溯与剪枝的经典技巧，还能深入理解图论中哈密顿回路的实际意义——它不仅仅是一个抽象的数学概念，更是确保贪吃蛇”永生”的终极密码。
