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.