The same laws must hold for sequences of bits since the bit operators \(\AND \) and \(\OR \) operate element-wise.
Solution to Exercise 6.3
b)With the numbering scheme shown in Fig. C.9, the offsets between neighboring cells are constant and it becomes possible to use bitboards and the techniques discussed in the text to compute possible jumps.
Figure C.9 Numbering scheme for triangular peg solitaire.
Solution to Exercise 6.4
The problem can be represented using one bitboard for each player. Some bit operations become easier if we add an empty column to the board, so we will use bitboards of size \(8\times 6\), which easily fit into long integers. The variable BOARD_MASK in Listing C.41 selects the bits of the board proper, without the empty column on the left.
Listing C.41ch6 / Connect4
static int WIDTH = 7, HEIGHT = 6;
// Bit board of size (WIDTH + 1) x HEIGHT
static long BOARD_MASK
= 0b01111111_01111111_01111111_01111111_01111111_01111111L;
// row 1 row 2 row 3 row 4 row 5 row 6
// bits: 47..40 39..32 31..24 23..16 15..8 7..0
Adjacent squares on the board are separated by a constant offset on the bitboard:
.
direction
left
right
down
up
up+left
up+right
offset
\(+1\)
\(-1\)
\(+8\)
\(-8\)
\(+9\)
\(+7\)
We can therefore use bit shifts to move the entire board in a certain direction. The added empty column serves as a buffer that prevents bit shifts from moving tokens to the opposite side of the board.
The fourBitsSet() function in Listing C.42 checks whether there are four bits with a certain offset from each other on a given board; notice
how BOARD_MASK is used to clear the extra column after every shift. The checkWin() method in the same listing now identifies a winning
position by checking for a line of four tokens in all four directions: horizontal, vertical, and the two diagonals.
Listing C.42ch6 / Connect4
// Check whether the board contains a sequence of four bits at a
// certain offset.
static boolean fourBitsSet(long board, int offset) {
long step1 = (board >>> offset) & BOARD_MASK;
long step2 = (step1 >>> offset) & BOARD_MASK;
long step3 = (step2 >>> offset) & BOARD_MASK;
return (board & step1 & step2 & step3) != 0;
}
// Check whether there is a line of four adjacent tokens
// anywhere on the bitboard.
static boolean checkWin(long board) {
int leftOffset = 1;
int upOffset = WIDTH + 1;
int upLeftOffset = WIDTH + 1 + 1;
int upRightOffset = WIDTH + 1 - 1;
return fourBitsSet(board, leftOffset)
|| fourBitsSet(board, upOffset)
|| fourBitsSet(board, upLeftOffset)
|| fourBitsSet(board, upRightOffset);
}
We can obtain a rough estimate by timing how long it takes the program in Listing 6.5 to generate a few thousand solutions and then extrapolating the result to 41 quadrillion possible solutions. On the author’s machine, generating
10 000 solutions without printing them takes 27 seconds, which gives us an estimate of
After the algorithm has completed, there are 23 475 687 entries in numSolutions, which is the number of visited boards. Only 1 679 071 of those entries have a
nonzero count associated with them, so only approximately 7 % of all reachable boards are actually solvable. This explains why humans find peg solitaire moderately difficult, despite there being quadrillions of possible solutions.
Solution to Exercise 6.7
The implementation in Listing C.43 stores previously computed values of the Fibonacci sequence in an array fibArray. The value 0 indicates an unknown value.
Listing C.43ch6 / FibMemoize
private static int[] fibArray = {1, 1};
public static int fib(int n) {
if (n >= fibArray.length)
fibArray = Arrays.copyOf(fibArray, n + 1);
if (fibArray[n] == 0)
fibArray[n] = fib(n - 1) + fib(n - 2);
return fibArray[n];
}
The Memoizer class shown in Listing C.44 implements the same interface as the function func it wraps. To cache previous return values of func, we use a hash table that is
queried and updated every time the apply() method is called.
Listing C.44ch6 / Memoizer
public class Memoizer<T, R> implements Function<T, R> {
private final Function<T, R> func;
private final HashMap<T, R> cache = new HashMap<>();
public Memoizer(Function<T, R> func) {
this.func = func;
}
public R apply(T t) {
return cache.computeIfAbsent(t, func);
}
}
a)The outcomes for a few small values of \(n\) and \(m\) are shown in Table C.1. For \(1,1\)-Nim, the first player always loses. For \(1,m\)-Nim with \(m>1\), the first player wins by removing \(m-1\) coins from the second
pile. For \(2,2\)-Nim, the first player loses since all moves lead to a winning state for the opponent, but for \(2,m\)-Nim with \(m>2\) the first player wins by taking \(m-2\) coins from the second pile. The same pattern repeats for \(n,m\)-Nim in general: The first player wins if \(n\ne m\) but loses if
\(n=m\), because in this case every possible move leads to a winning position for the opponent.
Table C.1
Winning strategies for \(n,m\)-Nim
.
\(n\)
\(m\)
Outcome
Winning move
1
1
loss
–
1
\(> 1\)
win
Take \(m-1\) coins
2
2
loss
–
2
\(>2\)
win
Take \(m-2\) coins
3
3
loss
–
3
\(>3\)
win
Take \(m-3\) coins
b)The detailed evaluation is fairly complex, but we can use the symmetry of \(W\) and a few logical shortcuts to simplify the computation:
\(\seteqnumber{0}{C.}{5}\)
\begin{align*}
W(1,1,2) &= \neg W(0,1,2) \lor \neg W(1,0,2) \lor \neg W(1,1,1) \lor \neg W(1,1,0)\\ &= \neg W(0,1,2) \lor \neg W(1,1,1) \lor \neg W(1,1,0) \tag {1}\\ &= \neg W(0,1,2) \lor W(1,1,0) \lor \neg W(1,1,0) \tag {2}\\ &= \mathsf {T} \tag {3}
\end{align*}
(1) follows from the fact that \(W\) is symmetric, so \(W(1,0,2) = W(0,1,2)\); (2) from \(W(1,1,1)=\neg W(1,1,0)\); and (3) from the fact that \(\neg X\lor X=\mathsf {T}\) for all \(X\).
c)We can represent each position as a list of integers that holds the number of coins in each pile. The goal is to implement a program that maps such a list to a Boolean value that indicates whether the corresponding position is winnable.
We use memoization to remember all previously computed values of this mapping in a hash table called winningCache; see Listing C.45. The constructor NimMemoize() initializes this table by mapping the empty list to false: The state with no coins left is by definition a losing position.
Listing C.45ch6 / NimMemoize
public class NimMemoize {
private final Map<List<Integer>, Boolean> winningCache;
public NimMemoize() {
winningCache = new HashMap<>();
// The empty list (no coins) is a losing position
winningCache.put(List.of(), false);
}
public static List<Integer> normalize(List<Integer> piles) {
var newPiles = new ArrayList<>(piles);
newPiles.sort(Integer::compare);
newPiles.removeIf(k -> k == 0);
return newPiles;
}
// Determine whether 'piles' is a winning position.
public boolean isWinning(List<Integer> piles) {
piles = normalize(piles);
if (winningCache.containsKey(piles))
return winningCache.get(piles);
for (int h = 0; h < piles.size(); h++) {
for (int n = 1; n <= piles.get(h); n++) {
var newPiles = new ArrayList<>(piles);
newPiles.set(h, piles.get(h) - n);
if (!isWinning(newPiles)) {
winningCache.put(piles, true);
return true;
}
}
}
winningCache.put(piles, false);
return false;
}
}
The normalize() method is used to map all equivalent positions to a single unique representative. Since empty piles can be ignored and the order of piles doesn’t matter, we can normalize a game
state by sorting the piles by size and keeping only nonzero entries. The function isWinning() in Listing C.45 checks whether removing
\(n\) coins from the \(k\)th pile produces a position that is unwinnable for the opponent. We memoize previous results in the hash table winningCache.
Calling this function tells us that the position \(10,5,4,3\) is winnable.
The result is nonzero, so this is a winning position. Only the last bit changes for \((2,5,7)\), which is therefore a losing position.
e)To find all possible winning moves, we first compute the Nim sum of the position. We then check for each pile of coins whether there is a positive number of coins n whose removal would reduce the Nim sum to zero, which indicates a losing
position for the opponent. The printWinningMoves() function in Listing C.46 implements this algorithm. The winning moves for \((3,6,6)\)
are:
- take 3 coin(s) from pile 0
- take 1 coin(s) from pile 1
- take 1 coin(s) from pile 2
Listing C.46ch6 / Nim
static void printWinningMoves(List<Integer> piles) {
int nimSum = 0;
for (int pile : piles)
nimSum ^= pile;
System.out.printf("Winning moves for %s:%n", piles);
for (int pile = 0; pile < piles.size(); pile++) {
int n = piles.get(pile) - (piles.get(pile) ^ nimSum);
if (n > 0) {
System.out.printf(
"- take %d coin(s) from pile %d%n", n, pile);
}
}
}
b)To represent the Sudoku board, we use an array of \(9\times 9\) integers in which empty squares are marked using the number 0 (Listing C.47). In addition, we use a handful of bit sets to keep track of
which digits can still be placed in each of the 9 rows (rowOptions), columns (colOptions), and \(3\times 3\) blocks (boxOptions). (The bit sets are stored in integers of type long instead of int to
make it easier to use the utility functions we defined in Chapter 5.) The putDigit() method writes a digit to the specified square on the
board and then removes it from the pool of available digits by modifying the corresponding bit sets. The removeDigit() method undoes this action.
Listing C.47ch6 / Sudoku
public class Sudoku {
private int[][] board = new int[9][9];
private long[] rowOptions = new long[9];
private long[] colOptions = new long[9];
private long[] boxOptions = new long[9];
static int blockIndex(int row, int col) {
return 3 * (row / 3) + col / 3;
}
void putDigit(int row, int col, int digit) {
this.board[row][col] = digit;
rowOptions[row] &= ~Bits.bit(digit);
colOptions[col] &= ~Bits.bit(digit);
boxOptions[blockIndex(row, col)] &= ~Bits.bit(digit);
}
void removeDigit(int row, int col, int digit) {
board[row][col] = 0;
rowOptions[row] |= Bits.bit(digit);
colOptions[col] |= Bits.bit(digit);
boxOptions[blockIndex(row, col)] |= Bits.bit(digit);
}
public Sudoku(String[] board) {
long ALL_DIGITS = Bits.bits(1, 2, 3, 4, 5, 6, 7, 8, 9);
Arrays.fill(rowOptions, ALL_DIGITS);
Arrays.fill(colOptions, ALL_DIGITS);
Arrays.fill(boxOptions, ALL_DIGITS);
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (!Character.isDigit(board[row].charAt(col)))
continue;
int digit = board[row].charAt(col) - '0';
if (digit != 0)
putDigit(row, col, digit);
}
}
}
// ...
}
The final method in Listing C.47 is the constructor Sudoku(), which uses an array of Strings to
initialize the board. Each entry of board describes one row of the board. For example, the board in Fig. 6.7 is encoded as follows:
The solve() method in Listing C.48 attempts to solve a given board using backtracking. The function first
searches for the next empty square on the board (row and col) and then tries all valid digits for this square; the set of valid digits is obtained by intersecting the corresponding bit sets in rowOptions, colOptions, and boxOptions. For each
possible digit, solve() calls itself recursively to complete the solution.
Listing C.48ch6 / Sudoku
public String solve() {
// Find first row with empty squares
int row = 0;
while (row < 9 && rowOptions[row] == 0)
row++;
if (row >= 9) {
// Solution found
var sb = new StringBuilder();
for (int[] r : board)
sb.append(Arrays.toString(r)).append('\n');
return sb.toString();
} else {
// Find first empty column
int col = 0;
while (col < 9 && board[row][col] != 0)
col++;
// Recursively try all allowed digits.
long validDigits = rowOptions[row] & colOptions[col]
& boxOptions[blockIndex(row, col)];
for (int digit : Bits.iterate(validDigits)) {
putDigit(row, col, digit);
var solution = solve();
if (solution != null)
return solution;
removeDigit(row, col, digit);
}
}
return null;
}