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).