引言
十五拼图（15-Puzzle）是Sam Loyd在1878年推广的经典滑块谜题，在4×4棋盘上通过滑动数字方块将乱序状态恢复为有序。本文用Java完整实现十五拼图求解器，核心讲解两个算法：一是利用逆序数（Inversion Count）快速判定拼图是否有解，二是使用A*搜索配合曼哈顿距离启发式寻找最优移动序列。
核心算法设计
1. 逆序数可解性判定
对于N×N拼图，将序列（去掉空白格）展平后，若逆序数与空白格所在行号之和的奇偶性满足特定条件，则拼图有解。对于4×4标准拼图：
– 从底部往上数空白格行号为 rowFromBottom
– 若棋盘宽度为奇数，逆序数必须为偶数
– 若棋盘宽度为偶数，逆序数与 rowFromBottom 的奇偶性必须相同
2. A*搜索与曼哈顿距离
将棋盘状态编码为字符串或一维数组，每个状态的启发式值h为所有方块到目标位置的曼哈顿距离之和。A*按 f = g + h 扩展状态，g为已走步数。
完整Java实现
import java.util.*;
/**
* 十五拼图求解器：逆序数判定 + A*搜索
*/
public class FifteenPuzzle {
static final int N = 4; // 4x4 棋盘
static final int[] GOAL = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
public static void main(String[] args) {
// 测试用例：有解状态
int[] start = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15};
FifteenPuzzle solver = new FifteenPuzzle();
if (!solver.isSolvable(start)) {
System.out.println("该拼图状态无解！");
return;
}
System.out.println("拼图有解，开始A*搜索...");
List<String> path = solver.solve(start);
System.out.println("最少步数: " + path.size());
System.out.println("移动序列: " + path);
}
/**
* 逆序数可解性判定
* 规则：对于4x4拼图，逆序数 + 空白格从底部数行号 必须为偶数
*/
boolean isSolvable(int[] board) {
int inversions = 0;
int blankRow = -1;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) {
blankRow = i / N; // 空白格所在行（0-based从上往下）
continue;
}
for (int j = i + 1; j < board.length; j++) {
if (board[j] != 0 && board[i] > board[j]) {
inversions++;
}
}
}
int rowFromBottom = N - blankRow; // 从底部往上数
// 对于偶数宽度（如4），逆序数与rowFromBottom同奇偶则有解
if (N % 2 == 0) {
return (inversions + rowFromBottom) % 2 == 0;
} else {
return inversions % 2 == 0;
}
}
/**
* A*搜索求解
*/
List<String> solve(int[] start) {
PriorityQueue<State> open = new PriorityQueue<>(Comparator.comparingInt(s -> s.f));
Map<String, Integer> dist = new HashMap<>(); // 记录已发现的最短距离
Map<String, State> parent = new HashMap<>();
State startState = new State(start, 0, heuristic(start), null, "");
open.offer(startState);
dist.put(startState.key, 0);
while (!open.isEmpty()) {
State cur = open.poll();
if (Arrays.equals(cur.board, GOAL)) {
return reconstructPath(cur);
}
if (cur.g > dist.getOrDefault(cur.key, Integer.MAX_VALUE)) continue;
int blankIdx = findBlank(cur.board);
int br = blankIdx / N, bc = blankIdx % N;
// 四个方向移动
int[][] dirs = {{-1,0,"下"},{1,0,"上"},{0,-1,"右"},{0,1,"左"}};
for (int[] d : dirs) {
int nr = br + d[0], nc = bc + d[1];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
int nIdx = nr * N + nc;
int[] nextBoard = cur.board.clone();
// 交换空白格与相邻数字
nextBoard[blankIdx] = nextBoard[nIdx];
nextBoard[nIdx] = 0;
State next = new State(nextBoard, cur.g + 1, heuristic(nextBoard), cur, d[2]);
int bestG = dist.getOrDefault(next.key, Integer.MAX_VALUE);
if (next.g < bestG) {
dist.put(next.key, next.g);
open.offer(next);
}
}
}
return Collections.emptyList(); // 理论上不会发生（已判定有解）
}
/**
* 曼哈顿距离启发式：所有数字到目标位置的曼哈顿距离之和
*/
int heuristic(int[] board) {
int sum = 0;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) continue;
int targetR = (board[i] - 1) / N;
int targetC = (board[i] - 1) % N;
int curR = i / N, curC = i % N;
sum += Math.abs(curR - targetR) + Math.abs(curC - targetC);
}
return sum;
}
int findBlank(int[] board) {
for (int i = 0; i < board.length; i++) if (board[i] == 0) return i;
return -1;
}
List<String> reconstructPath(State goal) {
LinkedList<String> path = new LinkedList<>();
State cur = goal;
while (cur.move != null && !cur.move.isEmpty()) {
path.addFirst(cur.move);
cur = cur.parent;
}
return path;
}
/** 搜索状态 */
class State {
int[] board;
int g, h, f;
String key;
State parent;
String move; // 到达此状态的移动方向
State(int[] board, int g, int h, State parent, String move) {
this.board = board.clone();
this.g = g;
this.h = h;
this.f = g + h;
this.parent = parent;
this.move = move;
this.key = boardToKey(board);
}
}
String boardToKey(int[] board) {
StringBuilder sb = new StringBuilder();
for (int v : board) sb.append(v).append(',');
return sb.toString();
}
/** 打印棋盘 */
void printBoard(int[] board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int v = board[i * N + j];
System.out.printf(v == 0 ? " " : "%2d ", v);
}
System.out.println();
}
System.out.println();
}
}
复杂度分析
- 逆序数判定：展平数组后双重循环统计，时间复杂度
O(N²)，空间O(1)。这是判定拼图可解性的最优方法，无需实际搜索即可拒绝无解输入。 - A*搜索：状态空间为
(N²-1)!/2（考虑等价状态），对于4×4棋盘约为10¹³。但曼哈顿距离作为强启发式函数，实际搜索节点数远小于此。在最优情况下时间复杂度接近O(有效状态数)，空间复杂度O(队列最大长度)。
总结
本文实现了十五拼图的完整求解流程：先用逆序数 O(N²) 判定可解性，避免对无解状态做无效搜索；再用A搜索配合曼哈顿距离启发式寻找最优解。读者可以进一步尝试线性冲突（Linear Conflict）启发式以进一步减少搜索节点，或实现IDA算法以降低内存占用。
