Java孔明棋解谜代码从long改用BitSet后无法正常求解问题排查

以下是你代码中的所有错误点及修正方法：

核心错误点 #

• 直接修改全局移动常量：BitSet是可变对象，你在search方法中直接调用move0.and(board)、move1.and(board)会修改moves全局数组里存储的移动规则，导致后续循环的规则全部错误。所有位运算判断都需要先拷贝BitSet副本再操作。
• 直接修改递归参数的棋盘对象：你直接将newBoard赋值为入参board的引用，调用newBoard.xor(move2)会直接修改当前递归层级的入参棋盘，导致上层递归的棋盘状态被破坏，必须每次操作前拷贝棋盘副本。
• 对象相等性判断错误：用==比较两个BitSet对象是判断内存地址是否相同，而非内容是否相等，必须使用BitSet重写的equals()方法判断棋盘状态是否一致。
• 存入HashSet的对象后续被修改：BitSet作为HashSet的键时如果后续被修改，会导致哈希值变化，无法正确去重，存入前必须确保是不会被后续修改的独立副本。

修正后的完整代码 #

import java.util.*;

public class BitSetEnglishPegSolitaire {
 
    // 已访问棋盘集合，避免重复搜索
    private static final HashSet<BitSet> seenBoards = new HashSet<>();
 
    // 解路径存储
    private static final ArrayList<BitSet> solution = new ArrayList<>();
 
    // -------
    // 常量定义，和原long版本语义完全一致
    private static String GOAL_BOARD_STRING = "0000000000000000000000001000000000000000000000000";
    private static BitSet GOAL_BOARD = bitsetFromString(GOAL_BOARD_STRING);
    
    private static String INITIAL_BOARD_STRING = "0011100001110011111111110111111111100111000011100";
    private static BitSet INITIAL_BOARD = bitsetFromString(INITIAL_BOARD_STRING);
    
    private static String VALID_BOARD_CELLS_STRING = "0011100001110011111111111111111111100111000011100";
    private static BitSet VALID_BOARD_CELLS = bitsetFromString(VALID_BOARD_CELLS_STRING);
 
    // 所有合法移动规则
    private static final BitSet[][] moves = new BitSet[76][];
 
    // -------
    // 打印棋盘
    private static void printBoard(BitSet board) {
        for (int i = 0; i < 49; i++) {
            boolean validCell = VALID_BOARD_CELLS.get(i);
            System.out.print(validCell ? (board.get(i) ? "X " : "O ") : "  ");
            if (i % 7 == 6) System.out.println();
        }
        System.out.println("-------------");
    }
 
    // 快速创建指定位为1的BitSet
    private static BitSet bitset(int... bits) {
        BitSet result = new BitSet();
        for (int i : bits)
            result.set(i);
        return result;
    }

    // 生成两个方向的移动规则
    private static void createMoves(int bit1, int bit2, int bit3, ArrayList<BitSet[]> moves) {
        moves.add(new BitSet[] {bitset(bit1), bitset(bit2, bit3), bitset(bit1, bit2, bit3)});
        moves.add(new BitSet[] {bitset(bit3), bitset(bit2, bit1), bitset(bit1, bit2, bit3)});
    }
 
    // 反向递归搜索（从目标棋盘回溯到初始棋盘）
    private static boolean search(BitSet board) {
        for (BitSet[] move : moves) {
            // 拷贝移动规则副本做运算，不修改全局常量
            BitSet tempMove0 = (BitSet) move[0].clone();
            BitSet tempMove1 = (BitSet) move[1].clone();
            tempMove0.and(board);
            tempMove1.and(board);               
            
            // 移动合法性判断，和原long版本逻辑完全一致
            if (tempMove1.isEmpty() && !tempMove0.isEmpty()) {
                // 拷贝棋盘副本做修改，不影响原递归参数
                BitSet newBoard = (BitSet) board.clone();
                newBoard.xor(move[2]);
                // 去重判断
                if (!seenBoards.contains(newBoard)) {
                    seenBoards.add((BitSet)newBoard.clone());
                    // 用equals判断棋盘内容是否相等
                    if (newBoard.equals(INITIAL_BOARD) || search(newBoard)) {
                        solution.add((BitSet)board.clone());
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    // 二进制字符串转BitSet，经校验和原long版本位定义完全一致
    private static BitSet bitsetFromString(String binary) {
        BitSet bitset = new BitSet(binary.length());
        int len = binary.length();
        for (int i = len-1; i >= 0; i--) {
            if (binary.charAt(i) == '1') {
                bitset.set(len-i-1);
            }
        }
        return bitset;
    }
 
    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        solution.add((BitSet)INITIAL_BOARD.clone());
 
        // 生成所有合法移动
        ArrayList<BitSet[]> moves = new ArrayList<>();
        int[] startsX = new int[] {2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44};
        for (int x : startsX) {
            createMoves(x, x + 1, x + 2, moves);
        }
        int[] startsY = new int[] {2,3,4,9,10,11,14,15,16,17,18,19,20,23,24,25,30,31,32};
        for (int y : startsY) {
            createMoves(y, y + 7, y + 14, moves);
        }
        Collections.shuffle(moves);
        moves.toArray(BitSetEnglishPegSolitaire.moves);
 
        // 启动搜索
        search(GOAL_BOARD);
 
        System.out.println("Completed in " + (System.currentTimeMillis() - time) + " ms.");
        // 打印解路径
        for (BitSet step : solution) {
            printBoard(step);
        }
    }
}

内容的提问来源于stack exchange，提问作者pileup