Switch The Knights

Question

On a small $ 4 \times 3$ chessboard, the top row is filled with black knights and the bottom row with white knights. On each move, you may move one knight (as it moves in chess) to an unoccupied square.

How many moves does it take to switch the white knights with the black knights?
Why can't it be done in fewer?

Source: Algorithmic Puzzles, Anany and Maria Levitin

Answer 1

You need at least 16 Moves.

1. Let's make the task visually more simple. The initial board is:

   a4 b4 c4  
   a3 b3 c3  
   a2 b2 c2  
   a1 b1 c1  
   

We cut it into 12 cells and connect only those, which are separated exactly by one move of a knight. Easy to check that the result is the following:

    c4 - a3 - c2 - a1  
     |    |   |    |
    b2   b1   b4   b3 
     |    |   |    | 
    a4 - c3 - a2 - c1 

So the knights are placed like this now:

    B1 -  . - .  - W1 
     |    |   |    |
     .   W2   B2   .
     |    |   |    | 
    B3 -  . - .  - W3 

2. Now it is quite easy to find a strategy for quick switch of the knights.

In 2+2+2+3=9 moves we have:

    W2 -  . - B1 - W1 
     |    |   |    |
     .   B3   B2   .
     |    |   |    | 
    W3 -  . - .  - . 

In 9+1+2+2=14 moves we have:

    W2 - B1 - .  - . 
     |    |   |    |
     .   B3   W1   .
     |    |   |    | 
    W3 -  . - .  - B2 

And in 14+2=16 moves we have the final position:

    W2 -  . - .  - B1 
     |    |   |    |
     .   B3   W1   .
     |    |   |    | 
    W3 -  . - .  - B2 

The actual chess moves have been perfectly illustrated by GOTO 0.

3. It is also easy to show that you can't perform the task faster. Indeed, imagine there is only black knights. It will take 2 moves for B2 to reach a closest final position, and at least 2 and 3 moves for B1 and B3, since they can't go both to the same cell. This makes 7 moves in total, furthermore there is only one way (up to the symmetry) you can move them. Similarly, you need at least 7 for moving the white knights.
   And, finally, since black and white are on the board at the same time and their paths are crossed, you will need at least 2 additional moves to make them pass each other.

Answer 2

I found a solution that uses 16 moves.

After exhaustively checking that there is no solution in 14 moves, I conclude that 16 moves is optimal, because after any odd number of moves the number of white and black squares occupied by knights cannot be equal.

Answer 3

Edit: Now that @GOTO 0 got it in 16, I can at least prove that his solution is optimal.

Proof:

The minimum possible number of moves if we could move through pieces would be seven per side. This is a total of 14 moves.

Proof that this is ideal: no piece can make it to the other side in one move because the positions are three squares apart. If every piece could make it to the other side in just two moves then each piece would have to end on the same color it started as - but that's not possible, because the top and bottom starting places don't have the same number of black/white squares. Thus it must take at least seven total moves, and seven is possible. It involves (for Black where D = down, R = right, L = left) moving the Top Left knight DRR > DDL, moving the Top Middle knight DDL > DRR, and moving the Top Right knight DLL > DRR > DLL. This can be mirrored on the other side for a total of 14 moves.

But, it cannot be done in 14 moves, because there will be a conflict!

Proof of conflict: In order to move across in seven moves, one of each side's corner knights and both middle knights have to make it across in just two. Let's assume without loss of generality that the Top Left knight does so. This means the Top Right knight must take three moves - and also means that the Bottom Right knight must take three moves (if the two knights taking three moves are on opposite corners, they take the same path as each other). Now, when can the Top Right knight move?

If the Top Right knight ever moves: then he occupies the square DLL of his start. However, the Bottom Middle knight needs to go through there, so TR will have to move again before the Bottom Middle knight does. Our stack is now TR > BM. But the TR knight can't move again (DRR) without getting into a permanent block with BL, who wants to move to that same square. So we have a stack of BL > TR > BM. If BL has to move first, he'll have to get out of the way entirely, which requires TM to move to make room, giving us a stack of TM > BL > TR > BM. If TM moves at least once (remember, he'll go DLL because middles swap with three-move knights), then he's in a permanent block with BR, so BR better move first. This gives BR > TM > BL > TR > BM. But then BR needs to get out of the way entirely, resulting in him moving ULL > URR... and getting into a permanent block with TL. TL better avoid that by moving first, giving us TL > BR > TM > BL > TR > BM. But in order for TL to move and get out of the way, they'll need to take the spot of BM, which means... uh oh, our stack is circular now, which is a contradiction. BM > TL > BR > TM > BL > TR > BM can't be done. But our assumption was only that TR moves, and negating that is also contradictory. Thus the 14 move solution is not possible.

If this was done in 15 moves, then the combination of all six knights would be on at least one square of a different color from when they started, since only even numbers of moves can maintain color. However, since the knights start and end in the same combined positions, they start and end on the same combined colors. Thus, this cannot be done in 15 moves.

Therefor, the minimum possible is 16, and @GOTO 0 proved by example that this can be done.

My best was:

20 Moves, in a variety of possible ways - here's one:

Answer 4

Maybe only a basic hint for a proof, but here are my thoughts.

Here is the playing area, where an X represents a cell in the playing area.

X X X
X X X
X X X
X X X

Note that the two centre cells are connected to only two cells each. So we can change the playing area to the one given below, without changing the problem in any way

  X  

X X X
X   X
X   X
X X X

  X  

Now the four corners are also connected two only two cells each, and not to each other. Hence we can change the playing area to

    X    
X       X
    X    
  X   X  
  X   X  
    X    
X       X
    X    

Adding the playing pieces makes the grid as follows:

    X    
B       B
    B    
  X   X  
  X   X  
    W    
W       W
    X    

This representation is equivalent to the original puzzle; any solution that works here also works there and vice versa. It is only that it is easier to see which cell is connected to which, in the figure given above.

I have no idea how to prove an optimal solution, though.

Answer 5

I can switch the black knights with the white knights in just 1 move:

rotate the board 180 degrees!