数字华容道（又称15-puzzle）是一个经典的滑块拼图游戏，玩家在4×4的棋盘上通过移动空白格周围的数字块，将打乱的数字按顺序排列。这个看似简单的游戏背后蕴含着丰富的搜索算法知识，其状态空间高达16!≈2×10^13种，对算法的效率提出了极高要求。本文将用Java实现一个基于迭代加深A星（IDA*）算法的高效求解器，并引入线性冲突启发式（Linear Conflict Heuristic）对估价函数进行优化，显著减少搜索节点数量。
一、问题建模与可解性判定
数字华容道的棋盘可以表示为一个一维整数数组，其中0代表空白格。每次移动等价于将空白格与上下左右相邻的数字交换位置。
1.1 逆序数可解性判定
并非所有随机打乱的棋盘都有解。判定可解性的经典方法是计算逆序数：将棋盘按行展开成一维数组（忽略空白格0），若逆序数为偶数则棋盘可解，奇数则不可解。
/**
* 计算逆序数，用于判定棋盘是否可解
* @param board 一维棋盘数组，0表示空白格
* @return 逆序数
*/
public static int countInversions(int[] board) {
int inversions = 0;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) continue;
for (int j = i + 1; j < board.length; j++) {
if (board[j] == 0) continue;
if (board[i] > board[j]) {
inversions++;
}
}
}
return inversions;
}
/**
* 判定当前棋盘状态是否可解
* 对于4×4棋盘，逆序数为偶数时可解
*/
public static boolean isSolvable(int[] board) {
return countInversions(board) % 2 == 0;
}
二、估价函数设计：从曼哈顿距离到线性冲突
IDA*算法的效率高度依赖于估价函数的准确性。估价函数h(n)必须满足可采纳性（admissible），即永远不高估实际代价。
2.1 曼哈顿距离启发式
曼哈顿距离是数字华容道最基础的启发式：每个数字块到其目标位置的横向与纵向距离之和。
/**
* 计算曼哈顿距离启发式
* @param board 当前棋盘
* @param size 棋盘边长（4表示4×4）
* @return 所有数字的曼哈顿距离之和
*/
public static int manhattanDistance(int[] board, int size) {
int distance = 0;
for (int i = 0; i < board.length; i++) {
int value = board[i];
if (value == 0) continue; // 跳过空白格
int targetRow = (value - 1) / size;
int targetCol = (value - 1) % size;
int currentRow = i / size;
int currentCol = i % size;
distance += Math.abs(targetRow - currentRow) + Math.abs(targetCol - currentCol);
}
return distance;
}
2.2 线性冲突启发式
线性冲突是对曼哈顿距离的重要增强。当两个数字在同一行（或列）中，且它们的目标位置也在同一行（或列），但相对顺序相反时，就发生了线性冲突。解决每个线性冲突至少需要额外2步移动（因为其中一个数字必须先绕出当前行/列）。
/**
* 计算线性冲突启发式
* 在同一行/列中，若两个数字的目标也在同行/列但顺序相反，则产生冲突
* 每个冲突至少增加2步额外移动
*/
public static int linearConflict(int[] board, int size) {
int conflict = 0;
// 逐行检查水平冲突
for (int row = 0; row < size; row++) {
for (int colA = 0; colA < size; colA++) {
int valA = board[row * size + colA];
if (valA == 0) continue;
int targetRowA = (valA - 1) / size;
if (targetRowA != row) continue; // 目标不在本行，跳过
for (int colB = colA + 1; colB < size; colB++) {
int valB = board[row * size + colB];
if (valB == 0) continue;
int targetRowB = (valB - 1) / size;
if (targetRowB != row) continue;
// 两者目标都在本行，检查列顺序是否冲突
int targetColA = (valA - 1) % size;
int targetColB = (valB - 1) % size;
if (targetColA > targetColB) {
conflict += 2; // 发生线性冲突，至少多2步
}
}
}
}
// 逐列检查垂直冲突
for (int col = 0; col < size; col++) {
for (int rowA = 0; rowA < size; rowA++) {
int valA = board[rowA * size + col];
if (valA == 0) continue;
int targetColA = (valA - 1) % size;
if (targetColA != col) continue;
for (int rowB = rowA + 1; rowB < size; rowB++) {
int valB = board[rowB * size + col];
if (valB == 0) continue;
int targetColB = (valB - 1) % size;
if (targetColB != col) continue;
int targetRowA = (valA - 1) / size;
int targetRowB = (valB - 1) / size;
if (targetRowA > targetRowB) {
conflict += 2;
}
}
}
}
return conflict;
}
/**
* 综合启发式：曼哈顿距离 + 线性冲突
*/
public static int heuristic(int[] board, int size) {
return manhattanDistance(board, size) + linearConflict(board, size);
}
线性冲突启发式显著提升了估价函数的判别能力。以15-puzzle为例，曼哈顿距离平均分支因子约为3，而加入线性冲突后可降至约1.5，搜索节点数可减少数个数量级。
三、IDA*迭代加深搜索
3.1 为什么选IDA*而非普通A*？
传统A*需要维护OpenSet和ClosedSet，对于15-puzzle这类状态空间巨大的问题，内存消耗会迅速爆炸。IDA*（Iterative Deepening A*）是A*与迭代加深深度优先搜索的结合：
- 无显式队列：仅通过递归深度优先搜索，内存复杂度为O(深度)
- 迭代加深：从初始启发值开始逐步放宽阈值，直到找到解
- 完备且最优：只要启发函数可采纳，IDA*保证找到最优解
3.2 核心搜索逻辑
public class IDAStarSolver {
private static final int[] DR = {-1, 1, 0, 0}; // 上、下、左、右的行偏移
private static final int[] DC = {0, 0, -1, 1};
private static final String[] MOVE_NAMES = {"上", "下", "左", "右"};
private int size; // 棋盘边长
private int[] goalBoard; // 目标状态
private List<String> solution; // 存储解路径
private int nodesExpanded; // 扩展节点数统计
private int threshold; // 当前搜索阈值
private int minExceeded; // 本轮超出阈值的最小f值
public IDAStarSolver(int size) {
this.size = size;
this.goalBoard = generateGoal(size);
}
/**
* 生成目标棋盘：1,2,3,...,15,0
*/
private int[] generateGoal(int size) {
int[] goal = new int[size * size];
for (int i = 0; i < goal.length - 1; i++) {
goal[i] = i + 1;
}
goal[goal.length - 1] = 0;
return goal;
}
/**
* 执行IDA\*搜索，返回是否找到解
*/
public boolean solve(int[] initialBoard) {
if (!isSolvable(initialBoard)) {
System.out.println("该棋盘状态不可解！");
return false;
}
// 找到空白格位置
int blankPos = findBlank(initialBoard);
// 初始阈值为启发函数值
threshold = heuristic(initialBoard, size);
solution = new ArrayList<>();
nodesExpanded = 0;
System.out.println("初始启发值: " + threshold);
while (true) {
minExceeded = Integer.MAX_VALUE;
List<String> path = new ArrayList<>();
int result = search(initialBoard, blankPos, 0, -1, path);
if (result == FOUND) {
solution = path;
return true;
}
if (minExceeded == Integer.MAX_VALUE) {
return false; // 无解
}
threshold = minExceeded; // 提高阈值继续搜索
System.out.println("阈值提升至: " + threshold);
}
}
private static final int FOUND = -1;
/**
* 深度优先搜索核心递归
* @param board 当前棋盘状态
* @param blankPos 空白格位置
* @param g 已走步数（实际代价）
* @param lastMove 上一步移动方向，用于避免立即回退
* @param path 当前路径
* @return FOUND表示找到解，否则返回f值
*/
private int search(int[] board, int blankPos, int g, int lastMove, List<String> path) {
int h = heuristic(board, size);
int f = g + h;
if (f > threshold) {
if (f < minExceeded) {
minExceeded = f;
}
return f;
}
if (h == 0) {
return FOUND; // 到达目标
}
nodesExpanded++;
int blankRow = blankPos / size;
int blankCol = blankPos % size;
for (int dir = 0; dir < 4; dir++) {
// 避免立即回退（例如上一步是"上"，这一步就不要"下"）
if (lastMove != -1 && dir == opposite(lastMove)) {
continue;
}
int newRow = blankRow + DR[dir];
int newCol = blankCol + DC[dir];
if (newRow < 0 || newRow >= size || newCol < 0 || newCol >= size) {
continue;
}
int newBlankPos = newRow * size + newCol;
// 执行移动：交换空白格与相邻数字
swap(board, blankPos, newBlankPos);
path.add(MOVE_NAMES[dir]);
int result = search(board, newBlankPos, g + 1, dir, path);
// 回溯
path.remove(path.size() - 1);
swap(board, blankPos, newBlankPos);
if (result == FOUND) {
return FOUND;
}
}
return f;
}
private int opposite(int dir) {
return dir < 2 ? 1 - dir : 5 - dir; // 0↔1, 2↔3
}
private void swap(int[] board, int i, int j) {
int tmp = board[i];
board[i] = board[j];
board[j] = tmp;
}
private int findBlank(int[] board) {
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) return i;
}
return -1;
}
public List<String> getSolution() {
return solution;
}
public int getNodesExpanded() {
return nodesExpanded;
}
}
3.3 增量式启发式更新（性能优化）
每次移动一个数字块后，无需重新计算整个棋盘的启发值。利用增量更新可将每次估价降至O(1)：
/**
* 增量计算移动后的启发值变化
* 当数字val从oldPos移动到newPos时，只需重新计算该数字的贡献
*/
public static int deltaManhattan(int val, int oldPos, int newPos, int size) {
int targetRow = (val - 1) / size;
int targetCol = (val - 1) % size;
int oldRow = oldPos / size;
int oldCol = oldPos % size;
int newRow = newPos / size;
int newCol = newPos % size;
int oldDist = Math.abs(targetRow - oldRow) + Math.abs(targetCol - oldCol);
int newDist = Math.abs(targetRow - newRow) + Math.abs(targetCol - newCol);
return newDist - oldDist; // 返回变化量
}
在完整实现中，可将启发值作为参数传递并在递归中增量维护，避免重复计算。
四、完整可运行程序
import java.util.*;
/**
* 数字华容道（15-puzzle）IDA\*求解器
* 使用线性冲突启发式优化搜索效率
*/
public class NumberPuzzleSolver {
// ==================== 启发式函数 ====================
public static int manhattanDistance(int[] board, int size) {
int distance = 0;
for (int i = 0; i < board.length; i++) {
int value = board[i];
if (value == 0) continue;
int targetRow = (value - 1) / size;
int targetCol = (value - 1) % size;
int currentRow = i / size;
int currentCol = i % size;
distance += Math.abs(targetRow - currentRow) + Math.abs(targetCol - currentCol);
}
return distance;
}
public static int linearConflict(int[] board, int size) {
int conflict = 0;
// 水平冲突
for (int row = 0; row < size; row++) {
for (int colA = 0; colA < size; colA++) {
int valA = board[row * size + colA];
if (valA == 0) continue;
if ((valA - 1) / size != row) continue;
for (int colB = colA + 1; colB < size; colB++) {
int valB = board[row * size + colB];
if (valB == 0) continue;
if ((valB - 1) / size != row) continue;
if ((valA - 1) % size > (valB - 1) % size) {
conflict += 2;
}
}
}
}
// 垂直冲突
for (int col = 0; col < size; col++) {
for (int rowA = 0; rowA < size; rowA++) {
int valA = board[rowA * size + col];
if (valA == 0) continue;
if ((valA - 1) % size != col) continue;
for (int rowB = rowA + 1; rowB < size; rowB++) {
int valB = board[rowB * size + col];
if (valB == 0) continue;
if ((valB - 1) % size != col) continue;
if ((valA - 1) / size > (valB - 1) / size) {
conflict += 2;
}
}
}
}
return conflict;
}
public static int heuristic(int[] board, int size) {
return manhattanDistance(board, size) + linearConflict(board, size);
}
// ==================== 可解性判定 ====================
public static int countInversions(int[] board) {
int inversions = 0;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) continue;
for (int j = i + 1; j < board.length; j++) {
if (board[j] == 0) continue;
if (board[i] > board[j]) inversions++;
}
}
return inversions;
}
public static boolean isSolvable(int[] board) {
return countInversions(board) % 2 == 0;
}
// ==================== IDA\* 搜索 ====================
private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};
private static final String[] MOVE_NAMES = {"上", "下", "左", "右"};
private static final int FOUND = -1;
private int size;
private List<String> solution;
private int nodesExpanded;
private int threshold;
private int minExceeded;
public NumberPuzzleSolver(int size) {
this.size = size;
}
public boolean solve(int[] initialBoard) {
if (!isSolvable(initialBoard)) {
System.out.println("该棋盘不可解！");
return false;
}
int blankPos = -1;
for (int i = 0; i < initialBoard.length; i++) {
if (initialBoard[i] == 0) {
blankPos = i;
break;
}
}
threshold = heuristic(initialBoard, size);
solution = new ArrayList<>();
nodesExpanded = 0;
System.out.println("初始启发值 (曼哈顿+线性冲突): " + threshold);
long startTime = System.currentTimeMillis();
while (true) {
minExceeded = Integer.MAX_VALUE;
List<String> path = new ArrayList<>();
int result = search(initialBoard, blankPos, 0, -1, path);
if (result == FOUND) {
solution = path;
long elapsed = System.currentTimeMillis() - startTime;
System.out.println("求解成功！耗时: " + elapsed + "ms, 扩展节点: " + nodesExpanded);
return true;
}
if (minExceeded == Integer.MAX_VALUE) return false;
threshold = minExceeded;
}
}
private int search(int[] board, int blankPos, int g, int lastMove, List<String> path) {
int h = heuristic(board, size);
int f = g + h;
if (f > threshold) {
if (f < minExceeded) minExceeded = f;
return f;
}
if (h == 0) return FOUND;
nodesExpanded++;
int blankRow = blankPos / size;
int blankCol = blankPos % size;
for (int dir = 0; dir < 4; dir++) {
if (lastMove != -1 && dir == opposite(lastMove)) continue;
int newRow = blankRow + DR[dir];
int newCol = blankCol + DC[dir];
if (newRow < 0 || newRow >= size || newCol < 0 || newCol >= size) continue;
int newBlankPos = newRow * size + newCol;
swap(board, blankPos, newBlankPos);
path.add(MOVE_NAMES[dir]);
int result = search(board, newBlankPos, g + 1, dir, path);
path.remove(path.size() - 1);
swap(board, blankPos, newBlankPos);
if (result == FOUND) return FOUND;
}
return f;
}
private int opposite(int dir) {
return dir < 2 ? 1 - dir : 5 - dir;
}
private void swap(int[] board, int i, int j) {
int tmp = board[i]; board[i] = board[j]; board[j] = tmp;
}
public List<String> getSolution() { return solution; }
public int getNodesExpanded() { return nodesExpanded; }
// ==================== 棋盘工具 ====================
public static void printBoard(int[] board, int size) {
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) System.out.printf("%3s ", " ");
else System.out.printf("%3d ", board[i]);
if ((i + 1) % size == 0) System.out.println();
}
}
public static int[] shuffleBoard(int size, int shuffleSteps) {
int[] board = new int[size * size];
for (int i = 0; i < board.length - 1; i++) board[i] = i + 1;
board[board.length - 1] = 0;
int blankPos = board.length - 1;
Random rand = new Random();
int lastDir = -1;
for (int step = 0; step < shuffleSteps; step++) {
List<Integer> validDirs = new ArrayList<>();
int row = blankPos / size;
int col = blankPos % size;
for (int dir = 0; dir < 4; dir++) {
if (lastDir != -1 && dir == (lastDir < 2 ? 1 - lastDir : 5 - lastDir)) continue;
int nr = row + DR[dir];
int nc = col + DC[dir];
if (nr >= 0 && nr < size && nc >= 0 && nc < size) {
validDirs.add(dir);
}
}
int dir = validDirs.get(rand.nextInt(validDirs.size()));
int newPos = (row + DR[dir]) * size + (col + DC[dir]);
int tmp = board[blankPos];
board[blankPos] = board[newPos];
board[newPos] = tmp;
blankPos = newPos;
lastDir = dir;
}
return board;
}
// ==================== 主程序 ====================
public static void main(String[] args) {
int size = 4; // 4×4 = 15-puzzle
int shuffleSteps = 80; // 随机打乱步数
System.out.println("========== 数字华容道 IDA\* 求解器 ==========");
int[] board = shuffleBoard(size, shuffleSteps);
System.out.println("初始棋盘:");
printBoard(board, size);
System.out.println("可解性: " + (isSolvable(board) ? "可解" : "不可解"));
System.out.println("曼哈顿距离: " + manhattanDistance(board, size));
System.out.println("线性冲突: " + linearConflict(board, size));
System.out.println("综合启发值: " + heuristic(board, size));
System.out.println();
NumberPuzzleSolver solver = new NumberPuzzleSolver(size);
if (solver.solve(board)) {
System.out.println("最优解步数: " + solver.getSolution().size());
System.out.println("移动序列: " + String.join(", ", solver.getSolution()));
} else {
System.out.println("未能找到解。");
}
}
}
五、算法复杂度分析
| 指标 | 传统BFS | A*+曼哈顿 | IDA*+曼哈顿 | IDA*+线性冲突 |
|---|---|---|---|---|
| 时间复杂度 | O(b^d) | O(b^d) | O(b^d) | O(b^d) |
| 空间复杂度 | O(b^d) | O(b^d) | O(d) | O(d) |
| 实际扩展节点 | 极大 | 较大 | 中等 | 显著减少 |
| 最优解保证 | 是 | 是 | 是 | 是 |
其中b为分支因子，d为解深度。线性冲突启发式通过提供更紧的下界，有效剪枝了大量无效搜索路径。在15-puzzle的80步随机实例中，IDA*配合线性冲突通常可在毫秒级完成求解。
六、扩展思路
- 模式数据库（Pattern Database）：预计算部分数字块的最优移动代价，可获得更强的启发式，但会牺牲一定内存。
- 多线程并行搜索：利用Java的Fork/Join框架对IDA*的多个阈值迭代进行并行化。
- 可视化界面：使用JavaFX或Swing将求解过程动画化，直观展示搜索与回溯。
数字华容道虽小，却是理解启发式搜索、可采纳性与算法优化的绝佳载体。通过IDA*与线性冲突启发式的结合，我们在有限的内存下实现了对庞大状态空间的高效遍历。
