我正试图将以下代码转换为使用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,INITIAL_BOARD_STRING,VALID_BOARD_CELLS_STRING及其相应的BitSetter方法bitsetFromString()的方式
我不知道问题到底出在哪里。
您正在破坏您的数据。
让我们假设您的代码正在运行for (BitSet[] move : moves)的第一次迭代，以便BitSet[] move = moves[0];.
当你写
BitSet move0 = move[0];
move0.and(board);
你实际上是在moves[0][0]修改BitSet，如果在递归调用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的副本——它只是创建对board引用的BitSet的另一个引用，因此
newBoard.xor(move2);
改变了newBoard引用的BitSet，这也是board引用的BitSet，这进一步混淆了数据。
您需要通过写入
来创建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)) {