Inverting a $n \times n$ board filled with knights

Question

I am facing the following problem:

Suppose we have a board of size $n \times n$ (in my case, it doesn't go above $n=5$). One diagonal of the board is empty, and the two sides it delimits are filled with black only, and white only, knights. There are only $n$ empty cases available at all times to move them. The goal is to swap all of them in the least possible amount of moves (only the color, a particuliar knight does not have to be exactly on the symmetrically opposed case).

With $n=3$ matrices, we want to go from:

$$ \begin{matrix} -1 & 1 & 1 \\ 0 & -1 & 1 \\ 0 & 0 & -1 \\ \end{matrix} $$

to:

$$ \begin{matrix} -1 & 0 & 0 \\ 1 & -1 & 0 \\ 1 & 1 & -1 \\ \end{matrix} $$

where $-1$ is an empty case and $0, 1$ are white and black knights. Also, we can't move one color twice in a row: one white should be moved, then one black, etc.

My first approach to solve this problem was to perform "intelligent bruteforce": by computing rewards for each move, I randomly selected one among the bests and looped until the board was solved. However, I made a fatal mistake by assuming that for each white move, the next black one should be the same, but reversed. It will inevitably produces a collision at some point. And when removing this false hypothesis, in addition to the search space becoming too large (even for $n = 5$), the amount of moves to solve the board became too huge.

I have never really studied graphs or game theories, so I don't really know how to approach this problem using "cleaner maths". Could you set me on the right track?

Answer 1

Here is an initial idea for how to solve the problem (but which might not be optimal in terms of moves).

The $3\times 3$ board

The $3 \times 3$ board has a similar solution to the four knight problem already mentioned in the comments. Draw an $8$-step loop through all the squares:

Along the loop (if we pick an arbitrary starting point and direction), the sequence of knights is $(♞,♘,♞,-,♘,♞,♘,-)$. There is one black knight and one white knight which can move "forward". If we move both of them forward, then after one move from each side, there is again one black knight and one one knight which can move forward. This situation repeats after one move from each side. After $4$ moves from each side, we will end up in the position $(♘,♞,♘,-,♞,♘,♞,-)$: the knights have swapped colors.

Unlike larger board, this solution is essentially unique, because knights are very limited in what they can do.

The $4\times 4$ board

For the $4\times 4$ board, a single loop is not enough. We can draw the following two loops:

The red loop has length $12$; it has the pattern $(♞,♞,♘,♞,♞,-,♘,♘,♞,♘,♘,-)$. We can make moves along it in the same way. After $6$ moves from each side, the empty spaces are in the same position, but the knights have shifted: we have $(♘,♞,♞,♘,♞,-,♞,♘,♘,♞,♘,-)$. Unlike the $3\times 3$ case, this is not enough for a solution, but if it repeats four more times (for a total of $30$ moves from each side, we end up in $(♘,♘,♞,♘,♘,-,♞,♞,♘,♞,♞,-)$: the knights have switched places.

Then we finish the job with $2$ moves from each side along the blue loop, which contains $1$ black knight and one white knight. (In total, each side has made $32$ moves.)

It is not a problem that the two loops share two diagonal squares, if we first complete the first loop before we start the second. When the knights along a loop are swapped, the diagonal squares used by the loop are empty again, so other loops can use them.

The $5\times 5$ board

There is a $5\times 5$ solution of the same type as the $4\times 4$ solution:

The red loop has the pattern $(♞,♞,♘,♘,♘,♞,♞,-,♘,♘,♞,♞,♞,♘,♘,-)$. It takes $8$ moves from both sides for the empty spaces to return to where they were, and $56$ moves from both sides for the knights to swap colors.

The blue loop has $3$ black knights, $3$ white knights, and two empty spaces. Unfortunately, it has a different pattern from the $3\times 3$ example: $(♘,♘,♘,-,♞,♞,♞,-)$. This pattern takes $12$ moves for the knights to swap colors, so the solution takes $68$ moves altogether.

We can now think about how this strategy works in general:

• To make it work, we have to find one or more diagonally symmetric loops that each contain at least two diagonal squares. The first condition is required for us to end up swapping knights of opposite colors by making moves along the loop; the second condition is necessary for us to be able to make moves along the loop at all.
• Ideally, each knight is on exactly one loop. It's technically okay for some knights to be on an odd number of loops that's more than one; then some black and white knights swap places multiple times. But this seems wasteful, and you have to be careful that colors still work out...
• A loop with $k$ knights of each color and $2t$ empty squares requires $k(k+t)$ moves from each side to complete in the worst case; sometimes if the patterns are symmetric enough, we can do better. So all else being equal, it's better to find more shorter loops.

It is not guaranteed that the optimal strategy for solving the problem is a "loop strategy". For one thing, all these loop strategies swap each knight with the corresponding knight of the other color, which was not required by the puzzle.

A faster $5\times5$ solution

Here is an ad-hoc attempt to make the $5\times5$ solution faster, in five steps inspired by the "loop strategy" above.

Begin with two short loops that swap two pairs of knights on either side ($4$ moves from both sides total):

With $2$ more moves from either side ($6$ total), get the knights on b3, c2, c4, and d3 out of the way. Then, we are free to do two more off-center loops ($4$ more moves from both sides, $10$ total). Finally, bring the knights that were moved onto the diagonal back to their initial positions ($2$ more moves from both sides, $12$ total, but see note at the end).

What's left is two instances of the $3\times 3$ puzzle, which we can solve in $4$ moves each from both sides. So we get a solution for the whole $5\times 5$ problem where each side makes $20$ moves.

We can cut this down to $18$ moves from each side if we observe that one of the white moves and one of the black moves in the next-to-last diagram is immediately undone in the last diagram, so we can simply skip those steps. Here is a complete solution:

1. Nab4 Ndc3 2. Nd5 Na2 3. Nbc3 Ned2 4. Ne4 Nb1 5. Na5 Ne1 6. Ncb4 Ncd2 7. Nbc4 Ne5d3 8. Ne5 Nb2 9. Na1b3 Ndc2 10. Nd4 Na1 11. Nbc2 Ndc4 12. N1c3 Ned1 13. Ncd3 Nec1 14. Nce3 Nec2 15. Nce2 N5c3 16. Nab5 N5b3 17. Nac5 N4a3 18. Nac4 Nca4