# Boolean formula over 64 Boolean variables X

This question comes from this homework assignment from ECS20 at UC Davis.

Chess is played on an 8 x 8 board. A knight placed on one square can move to any unoccupied square that is at a distance of two squares horizontally and one square vertically, or else two squares vertically and one square horizontally. The complete move therefore looks like the letter L (in some orientation). A knight cannot move off the board. Unlike other chess pieces, the knight can jump over" other pieces in going to its destination.

Consider a chess board on which we place any number $m \in$ {0,1,...,64} of knights, at most one knight on each square. Call the configuration of knights valid if no knight can move to a square occupied by another knight.

Carefully specify a Boolean formula over 64 Boolean variables $X$ where the number of truth assignments to $\phi$ is exactly the number of valid knight configurations.

This question has left me baffled. How could one solve this?

Your formula has a variable $K_{i,j}$ for $1 \le i, j \le 8$. $K_{i,j}$ is intended to mean that there is a knight on square $(i, j)$. You use implications to represent the constraints: if putting a knight on square $(i, j)$ means you can't put a knight on square $(m, n)$, then you represent that constraint by an implication $K_{i,j} \implies \lnot K_{m, n}$. The resulting formula is a conjunction of implications $K_{i,j} \implies \lnot K_{i\pm2,j\pm1}$ and $K_{i,j} \implies \lnot K_{i\pm1,j\pm2}$ (where you discard any implication where one of the subscripts is not between $1$ and $8$, i.e., you ignore constraints on knights that are not on the chessboard).
• There are $8 \times 8 = 64$ pairs of integers $(i, j)$ with $1 \le i, j \le 8$. The $K_{i, j}$ for these pairs will all appear somewhere in the formula I described. As I have said, you should discard implications involving $K_{i, j}$ where $i$ or $j$ is not between $1$ and $8$, so you will get a formula with exactly $64$ variables. (Write it out for a $3 \times 3$ chess board if you don't believe me. You will get $9$ variables.) – Rob Arthan Oct 16 '13 at 21:06