引言
滑动拼图（Sliding Puzzle），又称15-puzzle，是一款经典的益智游戏。玩家需要在4×4的网格中，通过上下左右滑动数字方块，将打乱的数字按顺序排列。空位仅有一个，每次只能将与空位相邻的方块移入空位。本文将用Java实现一个带AI求解器的滑动拼图，核心采用A*搜索算法，配合曼哈顿距离与线性冲突两种启发式函数，高效寻找最少步数解。
问题建模
将滑动拼图的当前盘面表示为一个16维状态向量，其中0代表空位。目标状态为 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]。每次合法移动产生一个新状态，所有状态构成一张隐式图。我们的任务是在这张图中寻找从初始状态到目标状态的最短路径。
A*搜索算法原理
A*算法通过评估函数 f(n) = g(n) + h(n) 来引导搜索方向：
– g(n) 表示从初始状态到当前状态 n 已走的实际步数；
– h(n) 是启发式估计值，表示从 n 到目标状态的预估代价。
只要 h(n) 满足可采纳性（不超过真实代价），A*就能保证找到最优解。本文使用两种启发式：
曼哈顿距离
每个数字方块到其目标位置的横向与纵向距离之和。计算公式为：
h_manhattan = Σ |当前行 - 目标行| + |当前列 - 目标列|
线性冲突
当两个方块在同一行（或列）上，且它们的目标位置也在同一行（或列），但顺序相反时，产生线性冲突。每对冲突需要额外2步才能化解。线性冲突是对曼哈顿距离的有效增强，能显著减少搜索节点数。
Java实现
import java.util.*;
/**
* 滑动拼图求解器：A*搜索 + 曼哈顿距离 + 线性冲突启发式
*/
public class SlidingPuzzleSolver {
// 目标状态：1~15顺序排列，0表示空位
private static final int[] GOAL = {
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 0
};
private static final int SIZE = 4; // 4x4 网格
private static final int TOTAL = 16; // 总格子数
/**
* 状态节点，存储盘面、步数、启发值与前驱指针
*/
static class Node implements Comparable<Node> {
int[] board; // 当前盘面
int g; // 已走步数
int h; // 启发估计值
int blank; // 空位索引
Node parent; // 前驱节点
char move; // 到达此节点的移动方向
Node(int[] board, int g, int blank, Node parent, char move) {
this.board = board.clone();
this.g = g;
this.blank = blank;
this.parent = parent;
this.move = move;
this.h = heuristic(this.board);
}
int f() { return g + h; }
@Override
public int compareTo(Node o) {
int cmp = Integer.compare(this.f(), o.f());
return cmp != 0 ? cmp : Integer.compare(this.h, o.h);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
return Arrays.equals(board, ((Node) o).board);
}
@Override
public int hashCode() {
return Arrays.hashCode(board);
}
}
/**
* 启发式函数：曼哈顿距离 + 线性冲突
*/
static int heuristic(int[] board) {
return manhattan(board) + linearConflict(board);
}
/**
* 计算曼哈顿距离
*/
static int manhattan(int[] board) {
int sum = 0;
for (int i = 0; i < TOTAL; i++) {
int val = board[i];
if (val == 0) continue; // 空位不计
int targetRow = (val - 1) / SIZE;
int targetCol = (val - 1) % SIZE;
int curRow = i / SIZE;
int curCol = i % SIZE;
sum += Math.abs(curRow - targetRow) + Math.abs(curCol - targetCol);
}
return sum;
}
/**
* 计算线性冲突：同一行/列中目标位置也在同行/列但顺序相反的对数 × 2
*/
static int linearConflict(int[] board) {
int conflicts = 0;
// 行冲突
for (int row = 0; row < SIZE; row++) {
for (int i = 0; i < SIZE; i++) {
int vi = board[row * SIZE + i];
if (vi == 0) continue;
int targetRowI = (vi - 1) / SIZE;
if (targetRowI != row) continue; // 目标不在本行
for (int j = i + 1; j < SIZE; j++) {
int vj = board[row * SIZE + j];
if (vj == 0) continue;
int targetRowJ = (vj - 1) / SIZE;
if (targetRowJ != row) continue;
// 两者目标都在本行，检查顺序是否颠倒
if ((vi - 1) % SIZE > (vj - 1) % SIZE) {
conflicts += 2;
}
}
}
}
// 列冲突
for (int col = 0; col < SIZE; col++) {
for (int i = 0; i < SIZE; i++) {
int vi = board[i * SIZE + col];
if (vi == 0) continue;
int targetColI = (vi - 1) % SIZE;
if (targetColI != col) continue; // 目标不在本列
for (int j = i + 1; j < SIZE; j++) {
int vj = board[j * SIZE + col];
if (vj == 0) continue;
int targetColJ = (vj - 1) % SIZE;
if (targetColJ != col) continue;
if ((vi - 1) / SIZE > (vj - 1) / SIZE) {
conflicts += 2;
}
}
}
}
return conflicts;
}
/**
* A*搜索主算法
*/
public static List<Character> solve(int[] start) {
// 先判断是否有解
if (!isSolvable(start)) {
return Collections.emptyList();
}
// 找到空位位置
int blankPos = -1;
for (int i = 0; i < TOTAL; i++) {
if (start[i] == 0) { blankPos = i; break; }
}
Node startNode = new Node(start, 0, blankPos, null, ' ');
PriorityQueue<Node> open = new PriorityQueue<>();
open.add(startNode);
// 用HashSet记录已访问状态（以board数组的hashCode为键）
Set<String> closed = new HashSet<>();
// 方向数组：上、下、左、右
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
char[] dirChars = {'U', 'D', 'L', 'R'};
while (!open.isEmpty()) {
Node cur = open.poll();
String key = Arrays.toString(cur.board);
if (closed.contains(key)) continue;
closed.add(key);
// 检查是否到达目标
if (Arrays.equals(cur.board, GOAL)) {
return reconstructPath(cur);
}
int r = cur.blank / SIZE;
int c = cur.blank % SIZE;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= SIZE || nc < 0 || nc >= SIZE) continue;
int newBlank = nr * SIZE + nc;
int[] newBoard = cur.board.clone();
// 交换空位与相邻方块
newBoard[cur.blank] = newBoard[newBlank];
newBoard[newBlank] = 0;
String newKey = Arrays.toString(newBoard);
if (closed.contains(newKey)) continue;
open.add(new Node(newBoard, cur.g + 1, newBlank, cur, dirChars[d]));
}
}
return Collections.emptyList(); // 无解（理论上不会到达此处）
}
/**
* 判断初始状态是否可解：逆序数 + 空位所在行
*/
static boolean isSolvable(int[] board) {
int inversions = 0;
int blankRow = 0;
for (int i = 0; i < TOTAL; i++) {
if (board[i] == 0) {
blankRow = SIZE - (i / SIZE); // 从底部数行号
continue;
}
for (int j = i + 1; j < TOTAL; j++) {
if (board[j] != 0 && board[i] > board[j]) {
inversions++;
}
}
}
// 4x4拼图：逆序数 + 空位从底部数的行号 必须为偶数
return (inversions + blankRow) % 2 == 0;
}
/**
* 从目标节点回溯重建移动路径
*/
static List<Character> reconstructPath(Node node) {
LinkedList<Character> path = new LinkedList<>();
while (node.parent != null) {
path.addFirst(node.move);
node = node.parent;
}
return path;
}
/**
* 打印盘面
*/
static void printBoard(int[] board) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
int v = board[i * SIZE + j];
System.out.printf(v == 0 ? " " : "%2d ", v);
}
System.out.println();
}
}
public static void main(String[] args) {
// 一个可解的初始状态（打乱后的15-puzzle）
int[] start = {
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 0, 12,
13, 14, 11, 15
};
System.out.println("初始状态：");
printBoard(start);
long t0 = System.currentTimeMillis();
List<Character> solution = solve(start);
long t1 = System.currentTimeMillis();
if (solution.isEmpty()) {
System.out.println("该状态无解！");
} else {
System.out.println("\n求解成功！步数：" + solution.size());
System.out.println("移动序列：" + solution);
System.out.println("耗时：" + (t1 - t0) + " ms");
}
}
}
复杂度分析
- 时间复杂度：最坏情况下需要遍历所有可达状态，4×4拼图共有
16! / 2 ≈ 10^13个状态。但在强启发式引导下，实际求解通常只需数万到数十万个节点。 - 空间复杂度：
O(b^d)，其中b为分支因子（平均约2.67），d为最优解深度。优先队列与闭集共同存储已访问节点。
总结
滑动拼图是理解启发式搜索的经典载体。本文通过A算法结合曼哈顿距离与线性冲突启发式，实现了对15-puzzle的高效最优求解。关键要点包括：状态表示、可解性判定（逆序数法）、启发式设计与A搜索框架。读者可在此基础上尝试模式数据库等更强启发式，进一步压缩搜索空间。
