TAOCP 7.1.3 Exercise 143

Represent the 8×8 board as a 64-bit word, where each bit corresponds to a square.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 143. [20] [20] Let x be a 64-bit number that represents an 8 × 8 chessboard, with a 1 bit in every position where a knight is present. Find a formula for the 64-bit number f(x) that has a 1 in every position reachable in one move by a knight of x. For example, the white knights at the start of a game correspond to x = #42; then f(x) = #a51800.

Verified: yes
Solve time: 1m16s

Solution

Represent the 8×8 board as a 64-bit word, where each bit corresponds to a square. Let bit shifts correspond to vertical movement by multiples of $8$ and horizontal movement by multiples of $1$ within each rank.

Define file masks $A, B, G, H$ as 64-bit constants whose 1-bits mark squares on the corresponding file.

A knight move from a square consists of the displacements

$(2,1), (2,-1), (1,2), (1,-2), (-1,2), (-1,-2), (-2,1), (-2,-1).$

These correspond to bit shifts:

$+17, +15, +10, +6, -6, -10, -15, -17,$

since vertical movement by $k$ ranks contributes $8k$ and horizontal movement by $h$ files contributes $h$.

Each shift must be restricted to prevent wraparound across files.

For a move $(+2,+1)$, the target square is obtained by shifting $17$ bits upward and rightward. A rightward shift by $1$ requires that the original square is not on file $H$. Thus the valid contribution is

$((x ,&, \overline{H}) \ll 17).$

For $(+2,-1)$, leftward shift by $1$ requires exclusion of file $A$, giving

$((x ,&, \overline{A}) \ll 15).$

For $(+1,+2)$, two steps right require exclusion of files $G$ and $H$, since any square on either would overflow after two right shifts. Thus

$((x ,&, \overline{G \mid H}) \ll 10).$

For $(+1,-2)$, two steps left require exclusion of files $A$ and $B$, giving

$((x ,&, \overline{A \mid B}) \ll 6).$

The remaining four moves are obtained by symmetry using right shifts.

For $( -1,+2 )$,

$((x ,&, \overline{G \mid H}) \gg 6).$

For $( -1,-2 )$,

$((x ,&, \overline{A \mid B}) \gg 10).$

For $( -2,+1 )$,

$((x ,&, \overline{H}) \gg 15).$

For $( -2,-1 )$,

$((x ,&, \overline{A}) \gg 17).$

Summing all contributions gives the full reachable set:

$$ f(x) = ((x ,&, \overline{H}) \ll 17) \mid ((x ,&, \overline{A}) \ll 15) \mid ((x ,&, \overline{G \mid H}) \ll 10) \mid ((x ,&, \overline{A \mid B}) \ll 6) $$

$$ \mid ((x ,&, \overline{G \mid H}) \gg 6) \mid ((x ,&, \overline{A \mid B}) \gg 10) \mid ((x ,&, \overline{H}) \gg 15) \mid ((x ,&, \overline{A}) \gg 17). $$

Each term contributes exactly the squares reached by one of the eight knight moves without overlap from illegal wraparound positions, since every horizontal shift is guarded by exclusion of the boundary files that would cause cyclic carry into adjacent ranks. This completes the construction of $f(x)$ as required. ∎