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.
1. What is the maximum branching factor in this state space, expressed as a function of $k$?
2. 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?
1. $\min\{h_1,\ldots,h_k\}$.
2. $\max\{h_1,\ldots,h_k\}$.
3. $\sum_{i= 1}^{k} h_i$.
3. Repeat (b) for the case where you are allowed to move only one knight at a time.