每日算法 — 使用java实现15数码：IDA*搜索与逆序数可解性判定

游戏简介

15数码（15-puzzle）是Sam Loyd在19世纪末推广的经典滑块拼图游戏。游戏在一个4×4的格子中进行，包含15个编号方块和1个空白格。玩家通过上下左右移动空白格 adjacent 的数字方块，目标是将打乱的数字按顺序排列。本文将用Java实现完整的求解系统，重点讲解逆序数判定可解性、IDA*迭代加深搜索算法，以及曼哈顿距离启发式函数的设计。

核心规则与数据结构

游戏规则

• 4×4棋盘，包含数字1-15和一个空白格（用0表示）
• 每次移动将空白格相邻的数字滑入空白位置
• 目标状态：数字按1-15顺序排列，空白格在右下角

数据结构

使用一维数组int[16]表示棋盘状态，索引0-15对应棋盘位置。这种表示便于计算逆序数和曼哈顿距离。

public class Puzzle15 {
    private int[] board;
    private int blankPos; // 空白格位置（0-15）
    private static final int SIZE = 4;
    private static final int[] GOAL = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};

    public Puzzle15(int[] initial) {
        this.board = initial.clone();
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0) {
                this.blankPos = i;
                break;
            }
        }
    }

    /**
     * 将2D坐标转为一维索引
     */
    private static int index(int row, int col) {
        return row * SIZE + col;
    }

    /**
     * 将一维索引转为2D坐标
     */
    private static int[] coord(int idx) {
        return new int[]{idx / SIZE, idx % SIZE};
    }
}

逆序数可解性判定

并非所有初始状态都有解。判定15数码可解性的经典方法是计算逆序数（inversion count）。

逆序数定义

将棋盘状态按行优先展开为一维序列（去掉空白格），逆序数指序列中前面数字大于后面数字的数对个数。

可解性定理

对于4×4的15数码：
– 计算逆序数invCount
– 计算空白格所在行号blankRow（从底部数，第1-4行）
– 若空白格在底部行（从底部数为第1行）或第3行：逆序数为偶数时可解
– 若空白格在底部第2行或第4行：逆序数为奇数时可解

等价表述：设blankRowFromBottom为空白格从底部数的行号（1-based），则状态可解当且仅当 (invCount + blankRowFromBottom) % 2 == 1。

public class Puzzle15 {
    // ... 其他代码

    /**
     * 计算逆序数并判定当前状态是否可解
     */
    public boolean isSolvable() {
        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++;
                }
            }
        }

        // 空白格从底部数的行号（1-based）
        int blankRowFromBottom = SIZE - (blankPos / SIZE);

        // 可解性判定：(invCount + blankRowFromBottom) % 2 == 1
        return (inversions + blankRowFromBottom) % 2 == 1;
    }

    /**
     * 生成一个保证可解的随机初始状态
     */
    public static Puzzle15 generateSolvable() {
        Random rand = new Random();
        int[] board;
        Puzzle15 puzzle;

        do {
            board = new int[16];
            List<Integer> nums = new ArrayList<>();
            for (int i = 0; i <= 15; i++) nums.add(i);
            Collections.shuffle(nums, rand);
            for (int i = 0; i < 16; i++) board[i] = nums.get(i);
            puzzle = new Puzzle15(board);
        } while (!puzzle.isSolvable());

        return puzzle;
    }
}

曼哈顿距离启发式

A搜索需要启发式函数估计从当前状态到目标状态的代价。对于滑块拼图，曼哈顿距离*（Manhattan Distance）是最常用且有效的启发式。

定义

每个数字块到其目标位置的行距离与列距离之和：

h(n) = Σ |current_row - goal_row| + |current_col - goal_col|

曼哈顿距离满足可采纳性（admissible）：它永远不会高估实际代价，因此A*搜索保证能找到最优解。

public class Puzzle15 {
    // ... 其他代码

    /**
     * 计算曼哈顿距离启发值
     */
    public int manhattanDistance() {
        int distance = 0;
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0) continue;
            int targetPos = board[i] - 1; // 数字k的目标位置是k-1
            distance += Math.abs(i / SIZE - targetPos / SIZE) 
                      + Math.abs(i % SIZE - targetPos % SIZE);
        }
        return distance;
    }

    /**
     * 线性冲突（Linear Conflict）增强启发式
     * 当同一行/列的两个块目标也在同一行/列，且互相阻挡时，额外+2
     */
    public int linearConflict() {
        int conflict = 0;

        // 行冲突
        for (int row = 0; row < SIZE; row++) {
            for (int i = 0; i < SIZE; i++) {
                int pos1 = index(row, i);
                if (board[pos1] == 0) continue;
                int targetRow1 = (board[pos1] - 1) / SIZE;
                if (targetRow1 != row) continue;

                for (int j = i + 1; j < SIZE; j++) {
                    int pos2 = index(row, j);
                    if (board[pos2] == 0) continue;
                    int targetRow2 = (board[pos2] - 1) / SIZE;
                    if (targetRow2 != row) continue;

                    // 如果目标列顺序与当前相反，则产生冲突
                    if ((board[pos1] - 1) % SIZE > (board[pos2] - 1) % SIZE) {
                        conflict += 2;
                    }
                }
            }
        }

        // 列冲突（类似逻辑）
        for (int col = 0; col < SIZE; col++) {
            for (int i = 0; i < SIZE; i++) {
                int pos1 = index(i, col);
                if (board[pos1] == 0) continue;
                int targetCol1 = (board[pos1] - 1) % SIZE;
                if (targetCol1 != col) continue;

                for (int j = i + 1; j < SIZE; j++) {
                    int pos2 = index(j, col);
                    if (board[pos2] == 0) continue;
                    int targetCol2 = (board[pos2] - 1) % SIZE;
                    if (targetCol2 != col) continue;

                    if ((board[pos1] - 1) / SIZE > (board[pos2] - 1) / SIZE) {
                        conflict += 2;
                    }
                }
            }
        }

        return manhattanDistance() + conflict;
    }
}

IDA*迭代加深搜索

A搜索在15数码中可能面临内存爆炸问题。IDA（Iterative Deepening A*）通过迭代加深的方式控制内存使用，同时利用启发式函数剪枝，是解决15数码最优解的高效算法。

算法思想

1. 设置初始阈值threshold = h(start)
2. 执行深度优先搜索，只扩展f = g + h ≤ threshold的节点
3. 若未找到解，将阈值更新为本次搜索中超出阈值的最小f值
4. 重复直到找到解

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[] DIR_NAME = {"UP", "DOWN", "LEFT", "RIGHT"};

    private int nodesExpanded;
    private int threshold;
    private boolean found;
    private List<String> solution;

    /**
     * IDA*主入口
     */
    public List<String> solve(Puzzle15 puzzle) {
        if (!puzzle.isSolvable()) {
            return null; // 不可解
        }

        if (puzzle.isGoal()) {
            return new ArrayList<>();
        }

        nodesExpanded = 0;
        threshold = puzzle.linearConflict();
        solution = new ArrayList<>();

        while (true) {
            found = false;
            int nextThreshold = Integer.MAX_VALUE;

            int result = search(puzzle, 0, -1, nextThreshold);

            if (found) {
                return solution;
            }

            if (result == Integer.MAX_VALUE) {
                return null; // 无解（理论上不会发生，因为已判定可解）
            }

            threshold = result;
        }
    }

    /**
     * 深度优先搜索
     * @param puzzle 当前状态
     * @param g 已走步数
     * @param lastDir 上次移动方向（避免回退）
     * @param nextThreshold 下一次迭代的阈值候选
     * @return 下一次迭代的阈值
     */
    private int search(Puzzle15 puzzle, int g, int lastDir, int nextThreshold) {
        int h = puzzle.linearConflict();
        int f = g + h;

        if (f > threshold) {
            return f; // 超出当前阈值，返回f作为候选
        }

        if (puzzle.isGoal()) {
            found = true;
            return f;
        }

        int minExceed = nextThreshold;
        nodesExpanded++;

        int blankRow = puzzle.getBlankPos() / 4;
        int blankCol = puzzle.getBlankPos() % 4;

        for (int dir = 0; dir < 4; dir++) {
            // 避免回退到上一步
            if (lastDir != -1 && isOpposite(dir, lastDir)) continue;

            int newRow = blankRow + DR[dir];
            int newCol = blankCol + DC[dir];

            if (newRow < 0 || newRow >= 4 || newCol < 0 || newCol >= 4) continue;

            // 执行移动
            puzzle.moveBlank(dir);
            solution.add(DIR_NAME[dir]);

            int result = search(puzzle, g + 1, dir, minExceed);

            if (found) {
                return result;
            }

            if (result < minExceed) {
                minExceed = result;
            }

            // 回溯
            solution.remove(solution.size() - 1);
            puzzle.undoMove(dir);
        }

        return minExceed;
    }

    private boolean isOpposite(int dir1, int dir2) {
        return (dir1 == 0 && dir2 == 1) || (dir1 == 1 && dir2 == 0) ||
               (dir1 == 2 && dir2 == 3) || (dir1 == 3 && dir2 == 2);
    }

    public int getNodesExpanded() {
        return nodesExpanded;
    }
}

完整可运行代码

import java.util.*;

public class Puzzle15 {
    private int[] board;
    private int blankPos;
    private static final int SIZE = 4;

    public Puzzle15(int[] initial) {
        this.board = initial.clone();
        for (int i = 0; i < board.length; i++) {
            if (board[i] == 0) {
                this.blankPos = i;
                break;
            }
        }
    }

    public boolean isGoal() {
        for (int i = 0; i < 15; i++) {
            if (board[i] != i + 1) return false;
        }
        return board[15] == 0;
    }

    public int getBlankPos() {
        return blankPos;
    }

    /**
     * 将空白格向指定方向移动
     */
    public void moveBlank(int dir) {
        int[] DR = {-1, 1, 0, 0};
        int[] DC = {0, 0, -1, 1};
        int row = blankPos / SIZE;
        int col = blankPos % SIZE;
        int newRow = row + DR[dir];
        int newCol = col + DC[dir];
        int newPos = newRow * SIZE + newCol;

        // 交换
        board[blankPos] = board[newPos];
        board[newPos] = 0;
        blankPos = newPos;
    }

    /**
     * 撤销移动
     */
    public void undoMove(int dir) {
        // 撤销方向即原方向的反方向
        int[] OPP = {1, 0, 3, 2};
        moveBlank(OPP[dir]);
    }

    public void print() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                int val = board[i * SIZE + j];
                System.out.printf(val == 0 ? "    " : "%4d", val);
            }
            System.out.println();
        }
        System.out.println();
    }

    // 逆序数、曼哈顿距离、线性冲突等方法的完整实现见上文
    // ...

    public static void main(String[] args) {
        // 一个简单的可解初始状态（需要6步）
        int[] init = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15};
        Puzzle15 puzzle = new Puzzle15(init);

        System.out.println("初始状态：");
        puzzle.print();

        if (!puzzle.isSolvable()) {
            System.out.println("该状态不可解！");
            return;
        }

        IDAStarSolver solver = new IDAStarSolver();
        List<String> solution = solver.solve(puzzle);

        if (solution == null) {
            System.out.println("无解！");
        } else {
            System.out.println("最优解步数：" + solution.size());
            System.out.println("搜索扩展节点数：" + solver.getNodesExpanded());
            System.out.println("操作序列：" + String.join(" -> ", solution));
        }
    }
}

复杂度分析

15数码的最优解深度平均约52步，最坏可达80步。IDA*配合线性冲突启发式可以在毫秒级求解大多数实例。

总结

本文实现了15数码的完整Java求解系统，核心亮点包括：

• 逆序数可解性判定：O(n²)时间快速判断任意状态是否可解，避免在不可解状态上浪费搜索资源
• 曼哈顿距离启发式：满足可采纳性的经典启发式，为A和IDA提供高效的估价函数
• 线性冲突增强：在曼哈顿距离基础上检测同行/同列的阻挡冲突，进一步提升启发式精度
• IDA*迭代加深：以O(d)空间复杂度实现最优解搜索，完美解决了15数码的状态空间爆炸问题

读者可以尝试实现更多高级技巧，如模式数据库（Pattern Database）、 disjoint pattern databases 等，进一步将求解速度提升数个数量级。