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
You need at least 16 Moves.
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
- 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.
- 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.
No comments:
Post a Comment