Camelot is a combinatory problem conceived to test bottom-up structuring techniques to avoid repetitive computations. To avoid the state space explosion that occurs with a naïve search algorithm, the contestants should develop a disciplined way of performing the required calculations by using, for instance, tabulation techniques.

Overall description

The general idea can be described as follows.

For each board position ~(h, v)~, an ~8 \times 8~ cost matrix ~CK_{h,v}~ is computed. This cost matrix reflects the minimal number of moves required for a knight, at ~(h, v)~, to reach each square of the board. Among them, there are the ~NK~ cost matrices ~MK_i~ for the knights mentioned in the source problem.

For the King, the corresponding cost matrix ~CKK~ is also computed.

If no encounters were allowed, by summing up all these ~NK+1~ matrices, a global matrix is obtained. The minima of the global matrix will define the gathering points of minimal cost.

In our case, we also need to consider, for each knight ~K_i~, the possibility of an encounter with the King.

Therefore, each cell ~(X, Y)~ of the matrix ~C = K_i+CKK~ contains the minimum cost of joining ~K_i~ with the King at ~(X, Y)~. We then consider, for each possible final gathering point ~(A, B)~ the minimum cost of knight travelling from each such ~(X, Y)~ to ~(A, B)~ plus the cost recorded at ~(X, Y)~ in ~C~.

By this, we obtain a combined cost matrix ~MCM_i~ for the situation where each knight ~K_i~ meets the King. By adding each of these matrices with those of the remaining knights, we obtain the minima for the case where the chosen Knight meets the King. We then take the global minimum over all possible Knight-King matings.

Complexity

The complexity of the solution is linear in the number of knights.