滑块拼图（Sliding Puzzle）是经典的益智游戏，玩家通过移动方块将打乱的拼图恢复有序。NxM滑块拼图的状态空间极其庞大，盲目搜索不可行。本文用Java实现带AI求解的滑块拼图，核心采用A*搜索算法，配合曼哈顿距离启发式函数，快速找到最优解路径。
算法核心思路
1. 状态表示
将拼图展平为一维数组，记录空格位置。每个状态是一个节点，包含当前拼图布局、空格坐标、已走步数g值和启发值h值。
2. 曼哈顿距离启发式
对于每个方块（除空格外），计算其当前位置到目标位置的水平与垂直距离之和。该值是到达目标状态的下界估计，满足可采纳性（不会高估实际代价）。
3. 逆序数可解性判定
并非所有初始状态都有解。对于标准滑块拼图，通过计算逆序数加上空格所在行号，可以快速判定当前状态是否可解，避免在不可解状态上浪费搜索时间。
4. A*搜索流程
使用优先队列（最小堆）按f=g+h排序。每次取出f值最小的节点，生成其上下左右四个邻接状态。若邻接状态未访问过或找到更优路径，则加入队列。当取出目标状态时，搜索结束，回溯输出移动序列。
Java实现
import java.util.*;
public class SlidingPuzzleSolver {
private final int rows;
private final int cols;
private final int[] goal;
private final int[] dr = {-1, 1, 0, 0};
private final int[] dc = {0, 0, -1, 1};
private final String[] dirName = {"UP", "DOWN", "LEFT", "RIGHT"};
public SlidingPuzzleSolver(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.goal = new int[rows * cols];
for (int i = 0; i < goal.length - 1; i++) goal[i] = i + 1;
goal[goal.length - 1] = 0;
}
private int manhattan(int[] board) {
int dist = 0;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) continue;
int targetRow = (board[i] - 1) / cols;
int targetCol = (board[i] - 1) % cols;
int curRow = i / cols;
int curCol = i % cols;
dist += Math.abs(targetRow - curRow) + Math.abs(targetCol - curCol);
}
return dist;
}
public boolean isSolvable(int[] board) {
int inversions = 0;
int blankRow = -1;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) {
blankRow = rows - (i / cols);
continue;
}
for (int j = i + 1; j < board.length; j++) {
if (board[j] != 0 && board[i] > board[j]) inversions++;
}
}
if (rows % 2 == 1) return inversions % 2 == 0;
else return (inversions + blankRow) % 2 == 0;
}
public List<String> solve(int[] initial) {
if (!isSolvable(initial)) return null;
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
Map<String, Integer> visited = new HashMap<>();
Map<String, Node> parent = new HashMap<>();
Map<String, String> moveDir = new HashMap<>();
Node start = new Node(initial, findBlank(initial), 0, manhattan(initial));
open.offer(start);
visited.put(start.key, 0);
while (!open.isEmpty()) {
Node cur = open.poll();
if (cur.h == 0) return reconstructPath(cur, parent, moveDir);
int r = cur.blank / cols;
int c = cur.blank % cols;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int newBlank = nr * cols + nc;
int[] nextBoard = cur.board.clone();
nextBoard[cur.blank] = nextBoard[newBlank];
nextBoard[newBlank] = 0;
Node next = new Node(nextBoard, newBlank, cur.g + 1, manhattan(nextBoard));
int prevG = visited.getOrDefault(next.key, Integer.MAX_VALUE);
if (next.g < prevG) {
visited.put(next.key, next.g);
parent.put(next.key, cur);
moveDir.put(next.key, dirName[d]);
open.offer(next);
}
}
}
return null;
}
private List<String> reconstructPath(Node goal, Map<String, Node> parent, Map<String, String> moveDir) {
LinkedList<String> path = new LinkedList<>();
Node cur = goal;
while (parent.containsKey(cur.key)) {
path.addFirst(moveDir.get(cur.key));
cur = parent.get(cur.key);
}
return path;
}
private int findBlank(int[] board) {
for (int i = 0; i < board.length; i++) if (board[i] == 0) return i;
return -1;
}
private class Node {
int[] board;
int blank, g, h, f;
String key;
Node(int[] board, int blank, int g, int h) {
this.board = board.clone();
this.blank = blank;
this.g = g;
this.h = h;
this.f = g + h;
this.key = Arrays.toString(board);
}
}
public void printBoard(int[] board) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int v = board[i * cols + j];
System.out.print(v == 0 ? " " : String.format("%2d ", v));
}
System.out.println();
}
}
public static void main(String[] args) {
SlidingPuzzleSolver solver = new SlidingPuzzleSolver(3, 3);
int[] init = {1, 2, 3, 4, 0, 6, 7, 5, 8};
System.out.println("初始状态：");
solver.printBoard(init);
System.out.println("可解性：" + solver.isSolvable(init));
List<String> solution = solver.solve(init);
if (solution == null) {
System.out.println("该状态不可解！");
} else {
System.out.println("最优解步数：" + solution.size());
System.out.println("移动序列：" + String.join(" -> ", solution));
}
}
}
复杂度分析
- 时间复杂度：最坏情况下遍历整个状态空间。对于3×3八数码问题，状态空间为9!/2=181440种，A*搜索可在毫秒级求解；4×4十五拼图状态空间达16!/2≈10万亿，需配合更优启发式才能高效求解。
- 空间复杂度：O(b^d)，b为分支因子（最多4），d为解深度。优先队列和访问集合需要存储大量中间状态。
扩展方向
- 线性冲突优化：在同一行/列中，两个方块目标位置也在同一行/列但顺序相反，需额外增加2的代价。
- IDA*迭代加深：用递归+阈值限制替代优先队列，大幅降低内存占用，适合更大规模拼图。
- 模式数据库：预先计算子问题的精确代价，作为更强启发式。
