java - 将代码从 long 转换为 BitSet - 它运行但不能正确解决
问题描述
我正在尝试将以下代码转换为使用BitSet而不是long用于超过 64 个单元的板：
import java.util.*;
public class Solver {
// list of seen boards - this is used to prevent rechecking of paths
private static final HashSet<Long> seenBoards = new HashSet<Long>();
// list of solution boards in ascending order - filled in once the solution is found
private static final ArrayList<Long> solution = new ArrayList<Long>();
// -------
// goal board (one marble in center)
private static final long GOAL_BOARD = 16777216L;
// initial board (one marble free in center)
private static final long INITIAL_BOARD = 124141717933596L;
// board that contains a ball in every available slot, i.e. GOAL_BOARD | INITIAL_BOARD
private static final long VALID_BOARD_CELLS = 124141734710812L;
// holds all 76 moves that are possible
// the inner array is structures as following:
// - first entry holds the peg that is added by the move
// - second entry holds the two pegs that are removed by the move
// - third entry holds all three involved pegs
private static final long[][] moves = new long[76][];
// -------
// print the board
private static void printBoard(long board) {
// loop over all cells (the board is 7 x 7)
for (int i = 0; i < 49; i++) {
boolean validCell = ((1L << i) & VALID_BOARD_CELLS) != 0L;
System.out.print(validCell ? (((1L << i) & board) != 0L ? "X " : "O ") : " ");
if (i % 7 == 6) System.out.println();
}
System.out.println("-------------");
}
// create the two possible moves for the three added pegs
// (this function assumes that the pegs are in one continuous line)
private static void createMoves(int bit1, int bit2, int bit3, ArrayList<long[]> moves) {
moves.add(new long[]{(1L << bit1), (1L << bit2) | (1L << bit3),
(1L << bit1) | (1L << bit2) | (1L << bit3)});
moves.add(new long[]{(1L << bit3), (1L << bit2) | (1L << bit1),
(1L << bit1) | (1L << bit2) | (1L << bit3)});
}
// do the calculation recursively by starting from
// the "GOAL_BOARD" and doing moves in reverse
private static boolean search(long board) {
// for all possible moves
for (long[] move : moves) {
// check if the move is valid
// Note: we place "two ball" check first since it is more
// likely to fail. This saves about 20% in run time (!)
if ((move[1] & board) == 0L && (move[0] & board) != 0L) {
// calculate the board after this move was applied
long newBoard = board ^ move[2];
// only continue processing if we have not seen this board before
if (!seenBoards.contains(newBoard)) {
seenBoards.add(newBoard);
// check if the initial board is reached
if (newBoard == INITIAL_BOARD || search(newBoard)) {
solution.add(board);
return true;
}
}
}
}
return false;
}
// the main method
public static void main(String[] args) {
// to measure the overall runtime of the program
long time = System.currentTimeMillis();
// add starting board (as this board is not added by the recursive function)
solution.add(INITIAL_BOARD);
// generate all possible moves
ArrayList<long[]> moves = new ArrayList<long[]>();
// holds all starting positions in west-east direction
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);
}
// holds all starting positions in north-south direction
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);
}
// randomize the order of the moves (this highly influences the resulting runtime)
Collections.shuffle(moves);
// fill in the global moves variable that is used by the solver
moves.toArray(Solver.moves);
// start recursively search for the initial board from the goal (reverse direction!)
search(GOAL_BOARD);
// print required time
System.out.println("Completed in " + (System.currentTimeMillis() - time) + " ms.");
// print the found solution
for (long step : solution) {
printBoard(step);
}
}
}
这是我现在的代码，它运行但没有解决：
import java.util.*;
public class BitSetEnglishPegSolitaire {
// list of seen boards - this is used to prevent rechecking of paths
private static final HashSet<BitSet> seenBoards = new HashSet<BitSet>();
// list of solution boards in ascending order - filled in once the solution is found
private static final ArrayList<BitSet> solution = new ArrayList<BitSet>();
// -------
//private static final long GOAL_BOARD = 16777216L;
private static String GOAL_BOARD_STRING = "0000000000000000000000001000000000000000000000000";
private static BitSet GOAL_BOARD = bitsetFromString(GOAL_BOARD_STRING);
//private static final long INITIAL_BOARD = 124141717933596L;
private static String INITIAL_BOARD_STRING = "0011100001110011111111110111111111100111000011100";
private static BitSet INITIAL_BOARD = bitsetFromString(INITIAL_BOARD_STRING);
//private static final long VALID_BOARD_CELLS = 124141734710812L;
private static String VALID_BOARD_CELLS_STRING = "0011100001110011111111111111111111100111000011100";
private static BitSet VALID_BOARD_CELLS = bitsetFromString(VALID_BOARD_CELLS_STRING);
// holds all 76 moves that are possible
// the inner array is structures as following:
// - first entry holds the peg that is added by the move
// - second entry holds the two pegs that are removed by the move
// - third entry holds all three involved pegs
private static final BitSet[][] moves = new BitSet[76][];
// -------
// print the board
private static void printBoard(BitSet board) {
// loop over all cells (the board is 7 x 7)
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("-------------");
}
// create the two possible moves for the three added pegs
// (this function assumes that the pegs are in one continuous line)
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)});
}
// do the calculation recursively by starting from
// the "GOAL_BOARD" and doing moves in reverse
private static boolean search(BitSet board) {
// for all possible moves
for (BitSet[] move : moves) {
BitSet move0 = move[0];
BitSet move1 = move[1];
BitSet move2 = move[2];
BitSet newBoard = board;
move0.and(board);
move1.and(board);
// check if the move is valid
// Note: we place "two ball" check first since it is more
// likely to fail. This saves about 20% in run time (!)
if (move1.isEmpty() && !move0.isEmpty()) {
// calculate the board after this move was applied
//BitSet newBoard = board ^ move[2];
newBoard.xor(move2);
// only continue processing if we have not seen this board before
if (!seenBoards.contains(newBoard)) {
seenBoards.add(newBoard);
// check if the initial board is reached
if (newBoard == INITIAL_BOARD || search(newBoard)) {
solution.add(board);
return true;
}
}
}
}
return false;
}
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;
}
// the main method
public static void main(String[] args) {
// to measure the overall runtime of the program
long time = System.currentTimeMillis();
// add starting board (as this board is not added by the recursive function)
solution.add(INITIAL_BOARD);
// generate all possible moves
ArrayList<BitSet[]> moves = new ArrayList<BitSet[]>();
// holds all starting positions in west-east direction
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);
}
// holds all starting positions in north-south direction
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);
}
// randomize the order of the moves (this highly influences the resulting runtime)
Collections.shuffle(moves);
// fill in the global moves variable that is used by the solver
moves.toArray(BitSetEnglishPegSolitaire.moves);
// start recursively search for the initial board from the goal (reverse direction!)
search(GOAL_BOARD);
// print required time
System.out.println("Completed in " + (System.currentTimeMillis() - time) + " ms.");
// print the found solution
for (BitSet step : solution) {
printBoard(step);
}
}
}
我认为我的问题在于search()方法（将按位逻辑转换为） ，BitSet以及我定义的方式GOAL_BOARD_STRING ，以及它们对应的 BitSetter 方法INITIAL_BOARD_STRING VALID_BOARD_CELLS_STRING bitsetFromString()
我无法找出问题到底出在哪里。
解决方案
你正在破坏你的数据。
让我们假设您的代码正在运行for (BitSet[] move : moves)so that的第一次迭代BitSet[] move = moves[0];。
现在当你写
BitSet move0 = move[0];
move0.and(board);
您实际上正在修改BitSetat moves[0][0]，如果在递归调用期间boolean search(BitSet board) 您无法再访问原始文件moves[0][0]- 但moves[0][0]递归工作需要原始文件。
该部分的解决方法是不使用move0.and(board);，move1.and(board);而是将以下条件替换if为非破坏性
if (!move1.intersects(board) && move0.intersects(board)) {
第二个问题是线路
BitSet newBoard = board;
不会创建的副本board- 它只是创建对所引用的 BitSet 的另一个引用board，因此该行
newBoard.xor(move2);
更改所BitSet引用的newBoard也是 BitSet 所引用的board进一步混淆数据。
您需要board通过编写创建副本而不是该行
BitSet newBoard = (BitSet) board.clone();
第三个问题是行中的比较
if (newBoard == INITIAL_BOARD || search(newBoard)) {
newBoard == INITIAL_BOARD比较对 BitSet 的引用newBoard，INITIAL_BOARD但是因为作为不同的对象开始，所以这个条件永远不会成立。
而不是你需要写
if (newBoard.equals(INITIAL_BOARD) || search(newBoard)) {
推荐阅读
- c++ - 在为该超类的子类制作的数组中使用超类对象时出错
- javascript - 如何使用单个导出从 React 中的 JS 文件中导出所有导入的图像？
- javascript - res.send 在将响应发送到我的 Express 服务器应用程序上的前端之前没有等待我的异步函数完成
- amazon-web-services - 无法在 EC2 Ubuntu 上提取 tar.gz wordpress
- algorithm - 如何找到大θ？
- python - 使用正则表达式匹配 json 格式的文本文件
- php - 如何使用 paypal/checkout-php-sdk 执行付款？
- redis - Redis超时，数据库中几乎没有数据，使用.NET客户端
- powershell - 在 Powershell 上访问 Selenium 中的本地存储
- postgresql - postgres 表中的 createdAt 在 SELECT 中变为“不存在”