CST $411$: Intelligent Systems

Fall $2024$

Problem Set $2-1$

Consider the problem of placing $k$ knights on an $nn$ chessboard such that no two knights are attacking each other, where $k$ is given and $kn$ :

$($a$)$ Choose a CSP formulation. In your formulation, what are the variables?

$($b$)$ What are the possible values of each variable?

$($c$)$ What sets of variables are constrained, and how?

$($d$)$ 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 a sensible objective function.