Exercise 6.2

Consider the problem of placing $k$ knights on an $n\times n$ chessboard such that no two knights are attacking each other, where $k$ is given and $k\leq n^2$.

  1. Choose a CSP formulation. In your formulation, what are the variables?

  2. What are the possible values of each variable?

  3. What sets of variables are constrained, and how?

  4. Now consider the problem of putting as many knights as possible on the board without any attacks. Explain how to solve this with local search by defining appropriate ACTIONS and RESULT functions and a sensible objective function.

View Answer