每日算法 — 使用java实现数字华容道：A星搜索与曼哈顿距离启发式

数字华容道（N-Puzzle）是中国传统益智玩具的现代数学版本，在4×4的棋盘上摆放着15个带有数字的滑块和一个空格，目标是通过上下左右滑动，将棋盘恢复到1~15从左到右、从上到下的有序状态。这个看似简单的游戏背后，隐藏着丰富的算法知识——A*搜索、启发式函数设计、状态空间理论与可解性判定。本文将带你用Java实现一个带AI求解能力的数字华容道程序，核心讲解A*搜索如何在庞大的状态空间中高效找到最优解。

一、问题建模与状态表示

数字华容道的状态空间极其庞大：15个数字块加一个空格，共16个位置的全排列有16! ≈ 2×10¹³种状态。如果盲目搜索，计算量是不可接受的。因此，高效的状态表示与智能的搜索策略是解决问题的关键。

1.1 一维数组压缩状态

将二维棋盘按行优先展开为一维数组，每个状态用一个int[]表示，空格用0表示：

/**
 * 数字华容道状态类
 * 使用一维数组表示4x4棋盘，0代表空格
 */
public class PuzzleState {
    public static final int SIZE = 4;          // 棋盘边长
    public static final int TOTAL = SIZE * SIZE; // 总格子数

    private final int[] board;                  // 棋盘状态，长度16
    private final int blankIndex;               // 空格当前位置（0~15）
    private final int gScore;                   // 从初始状态到当前状态的步数
    private final int hScore;                   // 启发式估计值
    private final PuzzleState parent;           // 父状态，用于路径回溯

    // 缓存哈希值，提升哈希表性能
    private final int hashCode;

    public PuzzleState(int[] board, int gScore, PuzzleState parent) {
        this.board = board.clone();
        this.gScore = gScore;
        this.parent = parent;

        // 找到空格位置
        int blank = -1;
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0) {
                blank = i;
                break;
            }
        }
        this.blankIndex = blank;

        // 计算曼哈顿距离作为启发式值
        this.hScore = computeManhattanDistance();
        this.hashCode = Arrays.hashCode(board);
    }

    /**
     * 计算曼哈顿距离：每个数字块到目标位置的距离之和
     * 这是A*搜索中最经典、最有效的启发式函数之一
     */
    private int computeManhattanDistance() {
        int distance = 0;
        for (int i = 0; i < board.length; i++) {
            int value = board[i];
            if (value == 0) continue; // 空格不计入

            // 当前位置 (行, 列)
            int currentRow = i / SIZE;
            int currentCol = i % SIZE;

            // 目标位置：数字value应该在(value-1)的位置
            int targetRow = (value - 1) / SIZE;
            int targetCol = (value - 1) % SIZE;

            distance += Math.abs(currentRow - targetRow) + Math.abs(currentCol - targetCol);
        }
        return distance;
    }

    /**
     * 获取f值 = g + h，A*搜索的优先级依据
     */
    public int getFScore() {
        return gScore + hScore;
    }

    public int getGScore() { return gScore; }
    public int getHScore() { return hScore; }
    public PuzzleState getParent() { return parent; }
    public int getBlankIndex() { return blankIndex; }
    public int[] getBoard() { return board.clone(); }

    /**
     * 判断是否为目标状态
     */
    public boolean isGoal() {
        for (int i = 0; i < TOTAL - 1; i++) {
            if (board[i] != i + 1) return false;
        }
        return board[TOTAL - 1] == 0;
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof PuzzleState)) return false;
        PuzzleState other = (PuzzleState) obj;
        return Arrays.equals(this.board, other.board);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                int val = board[i * SIZE + j];
                sb.append(val == 0 ? "  ." : String.format("%3d", val));
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

1.2 移动方向枚举

空格可以向上下左右四个方向移动，对应数字块滑入空格：

/**
 * 移动方向枚举
 * dx/dy表示空格移动的方向（从棋盘角度）
 */
public enum Move {
    UP(-1, 0, "上"),
    DOWN(1, 0, "下"),
    LEFT(0, -1, "左"),
    RIGHT(0, 1, "右");

    public final int dx;       // 行偏移
    public final int dy;       // 列偏移
    public final String label; // 中文描述

    Move(int dx, int dy, String label) {
        this.dx = dx;
        this.dy = dy;
        this.label = label;
    }

    /**
     * 获取反方向，用于避免"走一步又退一步"的回溯
     */
    public Move opposite() {
        return switch (this) {
            case UP -> DOWN;
            case DOWN -> UP;
            case LEFT -> RIGHT;
            case RIGHT -> LEFT;
        };
    }
}

二、可解性判定：逆序数奇偶性

并非所有随机打乱的数字华容道都有解。在4×4棋盘上，状态可解的充要条件与逆序数的奇偶性有关，这也是状态空间被分成两个互不连通的等价类的数学原因。

2.1 逆序数计算

将棋盘（不含0）按行优先展开为一维序列，逆序数定义为：前面比后面大的数字对的总数。

/**
 * 可解性判定工具类
 */
public class SolvabilityChecker {

    /**
     * 判断当前状态是否可解
     * 
     * 对于4x4棋盘（偶数边长），可解条件为：
     * 逆序数 + 空格所在行号（从底部数起）= 偶数
     * 
     * 原理：每次移动会改变逆序数奇偶性，或保持奇偶性同时改变空格行号，
     *      因此这两个量的和的奇偶性在移动过程中保持不变。
     */
    public static boolean isSolvable(int[] board) {
        int inversions = countInversions(board);
        int blankRowFromBottom = PuzzleState.SIZE - (findBlankIndex(board) / PuzzleState.SIZE);

        return (inversions + blankRowFromBottom) % 2 == 0;
    }

    /**
     * 计算逆序数（排除空格0）
     */
    private static int countInversions(int[] board) {
        int inversions = 0;
        int n = board.length;

        for (int i = 0; i < n; i++) {
            if (board[i] == 0) continue;
            for (int j = i + 1; j < n; j++) {
                if (board[j] == 0) continue;
                if (board[i] > board[j]) {
                    inversions++;
                }
            }
        }
        return inversions;
    }

    private static int findBlankIndex(int[] board) {
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0) return i;
        }
        throw new IllegalArgumentException("棋盘中没有找到空格");
    }
}

2.2 可解性判定的重要性

如果对一个无解的状态启动搜索，A*算法将遍历整个可达状态空间（约16!/2 ≈ 10¹³个状态）后才会”发现”无解。因此，在搜索前先进行可解性判定，可以立即拒绝无解输入，避免资源浪费。

三、A*搜索算法核心

A*（A-Star）搜索是一种最佳优先搜索算法，通过维护一个优先级队列，每次扩展f值最小的节点。在可采纳的启发式函数（如曼哈顿距离）下，A*能保证找到步数最少的最优解。

3.1 算法流程

1. 将初始状态加入开放列表（优先级队列）
2. 将初始状态加入已访问集合
3. while 开放列表不为空:
   a. 取出f值最小的状态current
   b. 如果current是目标状态，返回路径
   c. 对current的每个合法移动生成后继状态next
   d. 如果next未被访问过:
      - 将next加入开放列表
      - 将next加入已访问集合
4. 开放列表为空但未找到目标 → 无解（在已判定可解的情况下不会发生）

3.2 A*搜索实现

import java.util.*;

/**
 * A*搜索求解器
 */
public class AStarSolver {

    private int nodesExplored = 0;    // 搜索节点计数
    private int maxQueueSize = 0;     // 开放列表最大长度

    /**
     * 求解数字华容道
     * @param initialBoard 初始棋盘状态
     * @return 移动序列，若不可解返回空列表
     */
    public List<Move> solve(int[] initialBoard) {
        // 第一步：可解性判定
        if (!SolvabilityChecker.isSolvable(initialBoard)) {
            System.out.println("该状态无解！");
            return Collections.emptyList();
        }

        // 初始化
        PuzzleState initial = new PuzzleState(initialBoard, 0, null);

        // 开放列表：按f值排序的优先级队列
        PriorityQueue<PuzzleState> openSet = new PriorityQueue<>();
        openSet.add(initial);

        // 已访问集合：避免重复扩展同一状态
        Set<PuzzleState> visited = new HashSet<>();
        visited.add(initial);

        while (!openSet.isEmpty()) {
            maxQueueSize = Math.max(maxQueueSize, openSet.size());
            PuzzleState current = openSet.poll();
            nodesExplored++;

            // 找到目标
            if (current.isGoal()) {
                return reconstructPath(current);
            }

            // 扩展后继状态
            for (PuzzleState next : generateSuccessors(current)) {
                if (!visited.contains(next)) {
                    visited.add(next);
                    openSet.add(next);
                }
            }
        }

        // 理论上不会到达此处（已判定可解）
        return Collections.emptyList();
    }

    /**
     * 生成当前状态的所有合法后继状态
     */
    private List<PuzzleState> generateSuccessors(PuzzleState current) {
        List<PuzzleState> successors = new ArrayList<>();
        int blank = current.getBlankIndex();
        int blankRow = blank / PuzzleState.SIZE;
        int blankCol = blank % PuzzleState.SIZE;

        for (Move move : Move.values()) {
            int newRow = blankRow + move.dx;
            int newCol = blankCol + move.dy;

            // 边界检查
            if (newRow < 0 || newRow >= PuzzleState.SIZE || 
                newCol < 0 || newCol >= PuzzleState.SIZE) {
                continue;
            }

            // 避免"走一步又退一步"的回溯（可选优化）
            if (current.getParent() != null) {
                int parentBlank = current.getParent().getBlankIndex();
                int newBlankIndex = newRow * PuzzleState.SIZE + newCol;
                if (newBlankIndex == parentBlank) {
                    continue; // 这是回到父状态的方向，跳过
                }
            }

            // 交换空格与相邻数字
            int[] newBoard = current.getBoard();
            int newBlankIndex = newRow * PuzzleState.SIZE + newCol;
            swap(newBoard, blank, newBlankIndex);

            PuzzleState next = new PuzzleState(newBoard, current.getGScore() + 1, current);
            successors.add(next);
        }

        return successors;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 从目标状态回溯到初始状态，重建移动路径
     */
    private List<Move> reconstructPath(PuzzleState goal) {
        LinkedList<Move> path = new LinkedList<>();
        PuzzleState current = goal;

        while (current.getParent() != null) {
            // 根据空格位置变化推断移动方向
            int currentBlank = current.getBlankIndex();
            int parentBlank = current.getParent().getBlankIndex();

            int dRow = (currentBlank / PuzzleState.SIZE) - (parentBlank / PuzzleState.SIZE);
            int dCol = (currentBlank % PuzzleState.SIZE) - (parentBlank % PuzzleState.SIZE);

            for (Move move : Move.values()) {
                if (move.dx == dRow && move.dy == dCol) {
                    path.addFirst(move);
                    break;
                }
            }

            current = current.getParent();
        }

        return path;
    }

    public int getNodesExplored() { return nodesExplored; }
    public int getMaxQueueSize() { return maxQueueSize; }
}

四、曼哈顿距离：为什么它是优秀的启发式

曼哈顿距离之所以成为数字华容道的首选启发式，是因为它具有三个关键性质：

4.1 可采纳性（Admissible）

曼哈顿距离永远不高估实际代价。每个数字块每次移动最多向目标位置靠近一步，因此将每个块的距离相加，得到的总距离是实际步数的下界。

4.2 一致性（Consistent）

对于任意状态s和它的后继s’，满足：h(s) ≤ c(s, s') + h(s')，其中c(s,s’)=1是单步代价。这意味着A*不需要重复扩展已访问节点。

4.3 信息丰富度

相比简单的”错位块数”（Misplaced Tiles），曼哈顿距离提供了更精确的估计值，能显著减少搜索空间。例如：

五、完整可运行程序

import java.util.*;

/**
 * 数字华容道主程序
 * 演示A*搜索求解过程
 */
public class SlidingPuzzleApp {

    public static void main(String[] args) {
        // 一个中等难度的初始状态（约20步最优解）
        int[] initial = {
            1,  2,  3,  4,
            5,  6,  0,  8,
            9, 10,  7, 11,
           13, 14, 15, 12
        };

        System.out.println("=== 数字华容道 A* 求解器 ===\n");
        System.out.println("初始状态：");
        printBoard(initial);

        // 可解性检查
        if (!SolvabilityChecker.isSolvable(initial)) {
            System.out.println("❌ 该状态无解！");
            return;
        }
        System.out.println("✅ 可解性检查通过\n");

        // 执行A*搜索
        AStarSolver solver = new AStarSolver();
        long startTime = System.currentTimeMillis();
        List<Move> solution = solver.solve(initial);
        long endTime = System.currentTimeMillis();

        if (solution.isEmpty()) {
            System.out.println("未能找到解（理论上不应发生）");
            return;
        }

        // 输出结果
        System.out.println("=== 求解结果 ===");
        System.out.printf("最优步数: %d%n", solution.size());
        System.out.printf("搜索节点: %d%n", solver.getNodesExplored());
        System.out.printf("队列峰值: %d%n", solver.getMaxQueueSize());
        System.out.printf("耗时: %.3f 秒%n%n", (endTime - startTime) / 1000.0);

        // 逐步演示
        System.out.println("=== 移动步骤 ===");
        demonstrateSolution(initial, solution);
    }

    /**
     * 逐步演示求解过程
     */
    private static void demonstrateSolution(int[] board, List<Move> moves) {
        int[] current = board.clone();
        int step = 0;

        System.out.printf("第 %2d 步: (初始)%n", step);
        printBoard(current);

        for (Move move : moves) {
            step++;

            // 找到空格
            int blank = -1;
            for (int i = 0; i < current.length; i++) {
                if (current[i] == 0) { blank = i; break; }
            }

            int blankRow = blank / PuzzleState.SIZE;
            int blankCol = blank % PuzzleState.SIZE;
            int newRow = blankRow + move.dx;
            int newCol = blankCol + move.dy;
            int newBlank = newRow * PuzzleState.SIZE + newCol;

            // 执行移动
            int temp = current[blank];
            current[blank] = current[newBlank];
            current[newBlank] = temp;

            System.out.printf("第 %2d 步: 向%s移动%n", step, move.label);
            printBoard(current);
        }

        System.out.println("🎉 达成目标状态！");
    }

    private static void printBoard(int[] board) {
        for (int i = 0; i < PuzzleState.SIZE; i++) {
            System.out.print("  ");
            for (int j = 0; j < PuzzleState.SIZE; j++) {
                int val = board[i * PuzzleState.SIZE + j];
                System.out.print(val == 0 ? "  ." : String.format("%3d", val));
            }
            System.out.println();
        }
        System.out.println();
    }
}

六、复杂度分析与优化方向

6.1 理论复杂度

• 时间复杂度：O(b^d)，其中b为分支因子（最大4），d为最优解深度。在曼哈顿距离启发式下，有效分支因子通常远小于4。
• 空间复杂度：O(b^d)，主要来自开放列表和已访问集合。

6.2 实际表现

以4×4的15-Puzzle为例，曼哈顿距离A*的典型表现：

6.3 进阶优化

1. IDA*（迭代加深A*）：用递归+剪枝替代优先级队列，大幅降低内存占用，适合深度较大的问题。
2. 线性冲突（Linear Conflict）：在曼哈顿距离基础上，额外惩罚同一行/列中”互相挡路”的块对，使启发式更精确。
3. 模式数据库（Pattern Database）：预计算部分数字块的子问题最优解，构建更强大的启发式查找表。
4. 位运算压缩：将状态压缩为64位整数，使用数组替代HashSet进行访问标记，提升常数性能。

七、总结

数字华容道是理解A*搜索与启发式设计的绝佳案例。本文实现的Java程序涵盖了三大核心知识点：

• 可解性判定：通过逆序数奇偶性，在搜索前过滤无解状态，避免无效计算。
• A*搜索：利用优先级队列与f = g + h的策略，在庞大状态空间中有序地逼近最优解。
• 曼哈顿距离：作为可采纳且信息丰富的启发式函数，为搜索提供”导航信号”，将盲目遍历转化为有目标的方向性探索。

读者可以在此基础上尝试：为程序添加图形界面、实现IDA*降低内存开销、或引入线性冲突启发式挑战更复杂的打乱状态。算法之美，正在于用理性的结构解开看似混沌的难题。