Consider the problem of moving $k$ knights from $k$ starting squares $s_1,\ldots,s_k$ to $k$ goal squares $g_1,\ldots,g_k$, on an unbounded chessboard, subject to the rule that no two knights can land on the same square at the same time. Each action consists of moving up to $k$ knights simultaneously. We would like to complete the maneuver in the smallest number of actions.
-
What is the maximum branching factor in this state space, expressed as a function of $k$?
-
Suppose $h_i$ is an admissible heuristic for the problem of moving knight $i$ to goal $g_i$ by itself. Which of the following heuristics are admissible for the $k$-knight problem? Of those, which is the best?
-
$\min{h_1,\ldots,h_k}$.
-
$\max{h_1,\ldots,h_k}$.
-
$\sum_{i= 1}^{k} h_i$.
-
-
Repeat (b) for the case where you are allowed to move only one knight at a time.