问题背景
八数码问题（8-Puzzle）是人工智能领域的经典搜索问题。在一个 $3 \times 3$ 的棋盘上放置8个数字方块（1-8）和一个空白格，玩家可以通过将空白格与相邻方块交换来移动方块，目标是从初始状态到达指定的目标状态（通常为有序排列）。
与数字华容道（15-Puzzle）不同，八数码的搜索空间更小（$9!/2 = 181440$ 种可达状态），更适合作为入门级的启发式搜索教学案例。本文将讲解如何用 A* 搜索算法 高效求解八数码问题，以及如何通过逆序数快速判定问题是否有解。
核心算法思路
逆序数可解性判定
并非所有初始状态都能到达目标状态。八数码问题有一个重要的数学性质：状态可达的充要条件是逆序数的奇偶性保持不变。
具体判定方法：将棋盘按行展开为一个序列（忽略空白格），计算序列的逆序数。若初始状态与目标状态的逆序数奇偶性相同，则二者可达；否则不可达。
原理：每次移动空白格（上下左右），相当于将一个数字向前或向后移动1-2个位置，逆序数的变化量始终为偶数，因此逆序数的奇偶性是状态空间的不变量。
A* 搜索算法
A* 算法是一种启发式搜索算法，其核心是维护一个评价函数：
$$f(n) = g(n) + h(n)$$
其中：
– $g(n)$：从初始状态到当前状态 $n$ 的实际代价（步数）
– $h(n)$：从当前状态 $n$ 到目标状态的估计代价（启发函数）
对于八数码问题，常用的启发函数有：
1. 曼哈顿距离（Manhattan Distance）：每个数字到目标位置的横向加纵向距离之和
2. 错位棋子数（Misplaced Tiles）：不在目标位置上的数字个数
曼哈顿距离是可采纳的（admissible），即永远不会高估实际代价，因此能保证A*算法找到最优解。
Java 完整实现
import java.util.*;
/**
* 八数码问题求解器
* 使用A*搜索算法，支持逆序数可解性判定
*/
public class EightPuzzleSolver {
// 目标状态
private static final int[][] GOAL = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};
// 每个数字在目标状态中的位置，用于快速计算曼哈顿距离
// goalPos[v] = {row, col}
private static final int[][] GOAL_POS = new int[9][2];
static {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
GOAL_POS[GOAL[i][j]] = new int[]{i, j};
}
}
}
/**
* 状态节点类
*/
static class State implements Comparable<State> {
int[][] board; // 当前棋盘
int blankRow; // 空白格行坐标
int blankCol; // 空白格列坐标
int g; // 实际代价（已走步数）
int h; // 启发函数值（曼哈顿距离）
int f; // f = g + h
State parent; // 父节点，用于回溯路径
String move; // 从父节点到当前节点的移动方向
State(int[][] board, int blankRow, int blankCol, int g, State parent, String move) {
this.board = new int[3][3];
for (int i = 0; i < 3; i++) {
System.arraycopy(board[i], 0, this.board[i], 0, 3);
}
this.blankRow = blankRow;
this.blankCol = blankCol;
this.g = g;
this.h = manhattanDistance();
this.f = g + h;
this.parent = parent;
this.move = move;
}
/**
* 计算曼哈顿距离启发函数
*/
private int manhattanDistance() {
int dist = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int val = board[i][j];
if (val != 0) {
dist += Math.abs(i - GOAL_POS[val][0]) + Math.abs(j - GOAL_POS[val][1]);
}
}
}
return dist;
}
/**
* 将棋盘编码为字符串，用于判重
*/
String encode() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sb.append(board[i][j]);
}
}
return sb.toString();
}
@Override
public int compareTo(State other) {
return Integer.compare(this.f, other.f);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof State)) return false;
return encode().equals(((State) obj).encode());
}
@Override
public int hashCode() {
return encode().hashCode();
}
}
/**
* 计算逆序数，用于判定可解性
* @param board 3x3棋盘
* @return 逆序数
*/
public static int inversionCount(int[][] board) {
int[] seq = new int[8];
int idx = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] != 0) {
seq[idx++] = board[i][j];
}
}
}
int inv = 0;
for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 8; j++) {
if (seq[i] > seq[j]) inv++;
}
}
return inv;
}
/**
* 判定状态是否可解
* @param board 初始棋盘
* @return true 如果可达目标状态
*/
public static boolean isSolvable(int[][] board) {
int initInv = inversionCount(board);
int goalInv = inversionCount(GOAL);
// 逆序数奇偶性相同则可解
return (initInv % 2) == (goalInv % 2);
}
/**
* A*搜索求解八数码问题
* @param initial 初始棋盘
* @return 移动步骤列表，若不可解返回null
*/
public static List<String> solve(int[][] initial) {
if (!isSolvable(initial)) {
return null; // 不可解
}
// 找到空白格位置
int blankRow = -1, blankCol = -1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (initial[i][j] == 0) {
blankRow = i;
blankCol = j;
}
}
}
PriorityQueue<State> openSet = new PriorityQueue<>();
Set<String> closedSet = new HashSet<>();
State start = new State(initial, blankRow, blankCol, 0, null, null);
openSet.add(start);
// 四个方向：上、下、左、右
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
String[] dirNames = {"上", "下", "左", "右"};
while (!openSet.isEmpty()) {
State current = openSet.poll();
String code = current.encode();
if (closedSet.contains(code)) continue;
closedSet.add(code);
// 检查是否到达目标
if (current.h == 0) {
return reconstructPath(current);
}
// 扩展相邻状态
for (int d = 0; d < 4; d++) {
int nr = current.blankRow + dx[d];
int nc = current.blankCol + dy[d];
if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
int[][] newBoard = new int[3][3];
for (int i = 0; i < 3; i++) {
System.arraycopy(current.board[i], 0, newBoard[i], 0, 3);
}
// 交换空白格与相邻数字
newBoard[current.blankRow][current.blankCol] = newBoard[nr][nc];
newBoard[nr][nc] = 0;
State next = new State(newBoard, nr, nc, current.g + 1, current, dirNames[d]);
if (!closedSet.contains(next.encode())) {
openSet.add(next);
}
}
}
return null; // 理论上不会执行到这里（已判定可解）
}
/**
* 回溯重建路径
*/
private static List<String> reconstructPath(State state) {
List<String> path = new ArrayList<>();
while (state.parent != null) {
path.add(state.move);
state = state.parent;
}
Collections.reverse(path);
return path;
}
/**
* 打印棋盘状态
*/
public static void printBoard(int[][] board) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == 0) {
System.out.print(" ");
} else {
System.out.printf(" %d ", board[i][j]);
}
}
System.out.println();
}
}
// ==================== 主程序 ====================
public static void main(String[] args) {
// 示例1：有解的初始状态（最优解步数为8）
int[][] puzzle1 = {
{2, 8, 3},
{1, 6, 4},
{7, 0, 5}
};
System.out.println("=== 示例1 ===");
System.out.println("初始状态：");
printBoard(puzzle1);
System.out.println("逆序数: " + inversionCount(puzzle1));
System.out.println("是否可解: " + isSolvable(puzzle1));
List<String> solution1 = solve(puzzle1);
if (solution1 != null) {
System.out.println("最优解步数: " + solution1.size());
System.out.println("移动序列: " + String.join(" -> ", solution1));
} else {
System.out.println("该状态不可解");
}
// 示例2：无解的初始状态
int[][] puzzle2 = {
{1, 2, 3},
{4, 5, 6},
{8, 7, 0}
};
System.out.println("\n=== 示例2 ===");
System.out.println("初始状态：");
printBoard(puzzle2);
System.out.println("逆序数: " + inversionCount(puzzle2));
System.out.println("是否可解: " + isSolvable(puzzle2));
// 示例3：随机生成并求解
System.out.println("\n=== 示例3：随机生成状态 ===");
int[][] puzzle3 = generateRandomSolvable();
System.out.println("随机初始状态：");
printBoard(puzzle3);
List<String> solution3 = solve(puzzle3);
System.out.println("最优解步数: " + solution3.size());
System.out.println("移动序列: " + String.join(" -> ", solution3));
}
/**
* 随机生成一个有解的八数码状态
*/
public static int[][] generateRandomSolvable() {
Random rand = new Random();
int[][] board;
do {
List<Integer> nums = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8));
Collections.shuffle(nums);
board = new int[3][3];
for (int i = 0; i < 9; i++) {
board[i / 3][i % 3] = nums.get(i);
}
} while (!isSolvable(board));
return board;
}
}
算法复杂度分析
可解性判定：计算逆序数需要 $O(n^2)$ 时间，对于八数码问题（$n=8$）可以视为 $O(1)$。
A* 搜索：
– 时间复杂度：取决于启发函数的质量。使用曼哈顿距离时，A 算法扩展的节点数远少于朴素 BFS。在最坏情况下为 $O(b^d)$，其中 $b \approx 2.67$ 是平均分支因子，$d$ 是最优解深度。对于八数码问题，平均求解时间通常在毫秒级。
– 空间复杂度：$O(b^d)$，需要存储 openSet 和 closedSet。可以使用 IDA 迭代加深算法将空间复杂度优化到 $O(d)$。
关键结论与扩展
- 可解性判定：逆序数奇偶性是八数码问题的不变量，可以在搜索前 $O(1)$ 时间排除不可解状态，避免无效搜索。
- 启发函数选择：曼哈顿距离比错位棋子数更强（更接近真实代价），能显著减少搜索节点数。
- 线性冲突启发式：在曼哈顿距离基础上增加线性冲突惩罚（同一行/列中两个数字目标位置也在同一行/列但顺序相反），可以进一步减少搜索空间。
- IDA* 优化：当内存受限时，可以使用迭代加深 A（IDA）替代标准 A*，以时间换空间。
总结
本文通过八数码问题展示了 A 搜索算法的完整实现流程。从逆序数判定可解性到曼哈顿距离启发函数设计，再到优先队列的状态管理，完整呈现了一个经典 AI 搜索问题的求解范式。理解 A 算法的精髓——在信息不完备时做出最优决策——对于路径规划、游戏 AI 等领域都具有重要的指导意义。
