每日算法 — 使用java实现孔明棋：回溯搜索与对称性剪枝优化

引言

孔明棋（Peg Solitaire）是源自中国的经典单人棋类游戏，玩家在十字形棋盘上通过跳跃相邻棋子来吃掉被跳过的棋子，最终目标是让棋盘上只剩下一枚棋子并位于中心。本文用Java实现孔明棋的求解系统，重点讲解回溯搜索遍历状态空间、对称性剪枝减少重复搜索，以及启发式评估加速找到最优解路径。

核心算法设计

1. 状态压缩表示

孔明棋标准棋盘为十字形，共33个位置。使用64位长整型（long）进行状态压缩：

• 每位代表一个棋盘位置，1表示有棋子，0表示空位
• 中心位置初始为空，其余32个位置有棋子
• 状态转移：从位置A跳过相邻位置B到达空位C，消除B，移动A到C

2. 回溯搜索与状态转移

DFS递归探索所有可能的跳跃：

• 遍历所有有棋子的位置作为跳跃起点
• 检查四个方向是否有相邻棋子和目标空位
• 执行跳跃生成新状态，递归搜索
• 回溯恢复状态

3. 对称性剪枝

孔明棋棋盘具有旋转对称性和镜像对称性。使用规范化（canonical form）技术：

• 对每种状态生成其所有对称变体（旋转0°、90°、180°、270°和镜像）
• 取字典序最小的表示作为该状态的”规范形式”
• 仅搜索规范形式，遇到非规范形式直接剪枝
• 可进一步用HashSet记录已访问的规范状态，避免重复搜索

4. 启发式评估

用于评估当前状态距离终局的接近程度：

• 孤立棋子惩罚：无法被跳跃吃掉的棋子难以消除
• 中心聚集奖励：棋子越靠近中心，越容易参与后续跳跃
• 可行动作数量：可行动作越少，越接近终局或死局

完整Java实现

import java.util.*;

/**
 * 孔明棋核心算法实现
 * 包含状态压缩、回溯搜索、对称性剪枝与启发式评估
 */
public class PegSolitaire {

    // 标准英式孔明棋33孔位的坐标表示 (行, 列)
    // 棋盘布局：中心(3,3)为空，有效位置如下
    static final int[][] POSITIONS = {
        {0,2},{0,3},{0,4},
        {1,2},{1,3},{1,4},
        {2,0},{2,1},{2,2},{2,3},{2,4},{2,5},{2,6},
        {3,0},{3,1},{3,2},{3,3},{3,4},{3,5},{3,6},
        {4,0},{4,1},{4,2},{4,3},{4,4},{4,5},{4,6},
        {5,2},{5,3},{5,4},
        {6,2},{6,3},{6,4}
    };

    static final int N = 33; // 总孔位数
    static final int CENTER = 16; // 中心位置索引 (3,3)

    // 坐标到索引的映射
    static final Map<String, Integer> POS_TO_INDEX = new HashMap<>();
    static final int[][] INDEX_TO_POS = new int[N][2];

    // 每个位置在四个方向的邻居关系（跳跃方向）
    // jumpMoves[i][dir] = {中间位置索引, 目标位置索引}，-1表示不可跳
    static final int[][][] JUMP_MOVES = new int[N][4][2];

    static {
        for (int i = 0; i < N; i++) {
            POS_TO_INDEX.put(POSITIONS[i][0] + "," + POSITIONS[i][1], i);
            INDEX_TO_POS[i] = POSITIONS[i];
        }

        int[] dr = {-1, 1, 0, 0}; // 上、下、左、右
        int[] dc = {0, 0, -1, 1};

        for (int i = 0; i < N; i++) {
            int r = POSITIONS[i][0], c = POSITIONS[i][1];
            for (int d = 0; d < 4; d++) {
                int midR = r + dr[d], midC = c + dc[d];
                int endR = r + 2 * dr[d], endC = c + 2 * dc[d];

                String midKey = midR + "," + midC;
                String endKey = endR + "," + endC;

                if (POS_TO_INDEX.containsKey(midKey) && POS_TO_INDEX.containsKey(endKey)) {
                    JUMP_MOVES[i][d][0] = POS_TO_INDEX.get(midKey); // 被跳过的中间位置
                    JUMP_MOVES[i][d][1] = POS_TO_INDEX.get(endKey); // 落点位置
                } else {
                    JUMP_MOVES[i][d][0] = -1;
                    JUMP_MOVES[i][d][1] = -1;
                }
            }
        }
    }

    // 方向名称
    static final String[] DIR_NAME = {"上", "下", "左", "右"};

    long initialState;    // 初始状态（只有中心为空）
    long targetState;     // 目标状态（只有中心有棋子）
    int bestMovesCount = Integer.MAX_VALUE;
    List<Move> bestSolution = null;
    Set<Long> visited = new HashSet<>();

    public PegSolitaire() {
        // 初始状态：除中心外所有位置有棋子
        initialState = (1L << N) - 1; // 33位全1
        initialState &= ~(1L << CENTER); // 中心位置清空

        // 目标状态：只有中心有棋子
        targetState = 1L << CENTER;
    }

    /**
     * 检查某位置是否有棋子
     */
    boolean hasPeg(long state, int pos) {
        return (state & (1L << pos)) != 0;
    }

    /**
     * 执行跳跃动作，返回新状态
     */
    long applyMove(long state, int from, int mid, int to) {
        // 清除起点，清除中间被吃的棋子，设置落点
        return (state & ~(1L << from) & ~(1L << mid)) | (1L << to);
    }

    /**
     * 生成所有可能的跳跃动作
     */
    List<Move> generateMoves(long state) {
        List<Move> moves = new ArrayList<>();
        for (int from = 0; from < N; from++) {
            if (!hasPeg(state, from)) continue;
            for (int d = 0; d < 4; d++) {
                int mid = JUMP_MOVES[from][d][0];
                int to = JUMP_MOVES[from][d][1];
                if (mid < 0) continue;
                // 需要：起点有棋，中间有棋，落点为空
                if (hasPeg(state, mid) && !hasPeg(state, to)) {
                    moves.add(new Move(from, mid, to, d));
                }
            }
        }
        return moves;
    }

    static class Move {
        int from, mid, to, dir;
        Move(int f, int m, int t, int d) { from = f; mid = m; to = t; dir = d; }
        public String toString() {
            return String.format("(%d,%d) %s 跳至 (%d,%d)，吃掉 (%d,%d)",
                INDEX_TO_POS[from][0], INDEX_TO_POS[from][1], DIR_NAME[dir],
                INDEX_TO_POS[to][0], INDEX_TO_POS[to][1],
                INDEX_TO_POS[mid][0], INDEX_TO_POS[mid][1]);
        }
    }

    /**
     * 对称性变换：生成状态的所有对称变体
     * 英式孔明棋有旋转对称（90°、180°、270°）和镜像对称
     * 为简化，这里实现90°旋转和水平镜像
     */
    List<Long> symmetries(long state) {
        List<Long> result = new ArrayList<>();
        result.add(state);

        // 90°顺时针旋转 (r,c) -> (c, 6-r)
        result.add(rotate(state));
        // 180°旋转 = 90°旋转两次
        result.add(rotate(rotate(state)));
        // 270°旋转
        result.add(rotate(rotate(rotate(state))));
        // 水平镜像 (r,c) -> (r, 6-c)
        result.add(mirror(state));
        // 镜像后再旋转
        long mirrored = mirror(state);
        result.add(rotate(mirrored));
        result.add(rotate(rotate(mirrored)));
        result.add(rotate(rotate(rotate(mirrored))));

        return result;
    }

    /**
     * 90°顺时针旋转棋盘状态
     */
    long rotate(long state) {
        long newState = 0;
        for (int i = 0; i < N; i++) {
            if (!hasPeg(state, i)) continue;
            int r = INDEX_TO_POS[i][0], c = INDEX_TO_POS[i][1];
            int nr = c, nc = 6 - r;
            String key = nr + "," + nc;
            if (POS_TO_INDEX.containsKey(key)) {
                newState |= 1L << POS_TO_INDEX.get(key);
            }
        }
        return newState;
    }

    /**
     * 水平镜像棋盘状态
     */
    long mirror(long state) {
        long newState = 0;
        for (int i = 0; i < N; i++) {
            if (!hasPeg(state, i)) continue;
            int r = INDEX_TO_POS[i][0], c = INDEX_TO_POS[i][1];
            int nr = r, nc = 6 - c;
            String key = nr + "," + nc;
            if (POS_TO_INDEX.containsKey(key)) {
                newState |= 1L << POS_TO_INDEX.get(key);
            }
        }
        return newState;
    }

    /**
     * 获取状态的规范形式（所有对称中最小值）
     * 用于剪枝：等价的对称状态只搜索一次
     */
    long canonical(long state) {
        long min = state;
        for (long sym : symmetries(state)) {
            if (sym < min) min = sym;
        }
        return min;
    }

    /**
     * 启发式评估函数：评估状态距离终局的优劣
     * 值越小越好（剩余棋子数少 + 中心聚集 + 可行动作多）
     */
    int heuristic(long state) {
        int pegCount = Long.bitCount(state);
        int centerBonus = hasPeg(state, CENTER) ? 0 : 5; // 中心有棋更好

        // 孤立棋子惩罚：无法被跳过的棋子
        int isolated = 0;
        for (int i = 0; i < N; i++) {
            if (!hasPeg(state, i)) continue;
            boolean canMove = false;
            for (int d = 0; d < 4; d++) {
                int mid = JUMP_MOVES[i][d][0];
                int to = JUMP_MOVES[i][d][1];
                if (mid >= 0 && hasPeg(state, mid) && !hasPeg(state, to)) {
                    canMove = true; break;
                }
            }
            if (!canMove) isolated += 3;
        }

        return pegCount * 10 + centerBonus + isolated;
    }

    /**
     * 回溯搜索主函数
     * @param state 当前棋盘状态
     * @param moves 已执行的动作序列
     * @param depth 搜索深度（已走步数）
     */
    void dfs(long state, List<Move> moves, int depth) {
        // 找到更优解（剩余棋子更少）
        int pegCount = Long.bitCount(state);
        if (pegCount < bestMovesCount) {
            bestMovesCount = pegCount;
            bestSolution = new ArrayList<>(moves);
            System.out.println("发现更优解：剩余 " + pegCount + " 枚棋子");
        }

        // 剪枝1：到达目标
        if (state == targetState) {
            return;
        }

        // 剪枝2：对称性检查 + 访问集合
        long canon = canonical(state);
        if (visited.contains(canon)) return;
        visited.add(canon);

        // 剪枝3：深度限制（可选，用于限制搜索范围）
        if (depth >= 31) return; // 最多31步（33-2个棋子被吃，每步吃1个）

        // 生成所有合法动作，按启发式排序（更可能到达终局的动作优先）
        List<Move> legalMoves = generateMoves(state);
        legalMoves.sort((a, b) -> {
            long sa = applyMove(state, a.from, a.mid, a.to);
            long sb = applyMove(state, b.from, b.mid, b.to);
            return Integer.compare(heuristic(sa), heuristic(sb));
        });

        for (Move move : legalMoves) {
            long newState = applyMove(state, move.from, move.mid, move.to);
            moves.add(move);
            dfs(newState, moves, depth + 1);
            moves.remove(moves.size() - 1); // 回溯
        }
    }

    /**
     * 求解孔明棋：从初始状态搜索到只剩1枚棋子的最优路径
     */
    public List<Move> solve() {
        visited.clear();
        bestMovesCount = Integer.MAX_VALUE;
        bestSolution = null;
        dfs(initialState, new ArrayList<>(), 0);
        return bestSolution;
    }

    /**
     * 打印棋盘状态
     */
    public void printBoard(long state) {
        char[][] display = new char[7][7];
        for (char[] row : display) Arrays.fill(row, ' ');
        for (int i = 0; i < N; i++) {
            int r = INDEX_TO_POS[i][0], c = INDEX_TO_POS[i][1];
            display[r][c] = hasPeg(state, i) ? '●' : '○';
        }
        for (int r = 0; r < 7; r++) {
            for (int c = 0; c < 7; c++) {
                System.out.print(display[r][c] + " ");
            }
            System.out.println();
        }
    }

    // 演示入口
    public static void main(String[] args) {
        PegSolitaire game = new PegSolitaire();

        System.out.println("=== 孔明棋 初始布局 ===");
        game.printBoard(game.initialState);

        System.out.println("\n开始回溯搜索...");
        long start = System.currentTimeMillis();
        List<Move> solution = game.solve();
        long elapsed = System.currentTimeMillis() - start;

        System.out.println("\n搜索耗时: " + elapsed + "ms");
        System.out.println("最优解剩余棋子: " + game.bestMovesCount);

        if (solution != null) {
            System.out.println("\n最优解路径（前10步）：");
            for (int i = 0; i < Math.min(10, solution.size()); i++) {
                System.out.println((i + 1) + ". " + solution.get(i));
            }
        }
    }
}

复杂度分析

算法亮点总结

• 64位状态压缩：用单个long表示整个棋盘，状态转移仅需3次位运算，内存占用极低。
• 对称性剪枝：8种对称变体取规范形式，等效状态空间缩减约8倍，配合访问集合避免大量重复搜索。
• 启发式排序：每次按评估函数排序候选动作，优先探索更可能接近终局的分支，显著加速找到优质解。
• 增量更新最优解：搜索过程中持续记录当前最佳结果，即使未找到完美解也能输出局部最优路径。

这套算法可进一步扩展为支持不同棋盘变体（欧式37孔、三角形）、逆向求解（从终局反推初始布局）、以及基于A*搜索的带权最优路径求解等高级功能。