-1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Would this formula cover the requirement of having 64 Boolean variables? $\endgroup$ – user27546 Oct 16 '13 at 19:57
  • $\begingroup$ Rob's answer makes sense. However, I'm also not quite sure if it covers the requirement of 64 variables. I believe it does since he does consider the subscripts 1 through 8 for both variables i and j so I 'm assuming it does indeed use 64 variables. Response or and other input would be appreciated. $\endgroup$ – TheDifficultyOfAlgortihms Oct 16 '13 at 20:06
  • $\begingroup$ 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.) $\endgroup$ – Rob Arthan Oct 16 '13 at 21:06
  • 2
    $\begingroup$ @user98289: why did you trash the question? $\endgroup$ – Rob Arthan Oct 16 '13 at 22:05
  • 4
    $\begingroup$ Also relevant, why did user2461496 approve the edits? $\endgroup$ – Joel Reyes Noche Oct 16 '13 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.