Interchange, in the least posible number of moves, the positions of the the two black knights and black rook with those of the two white knights and white rook. Movements allowed are those of the corresponding pieces in the game of chess within the portion of the board available. White and black moves need not alternate.

enter image description here

  • Are the knights required to exchange places with the knights, and the rook with the rook? Or do we just have to exchange white pieces with black pieces? (If it's the former, I think the puzzle is unsolvable ...) – Rand al'Thor May 24 at 0:30
  • Yes, knights with knights, rook with rook. – Bernardo Recamán Santos May 24 at 0:33
  • Right, I was missing a trick :-) My answer is now complete. – Rand al'Thor May 24 at 1:02
up vote 7 down vote accepted

Just like Rand al'Thor and phenomist, i started looking at the movement of the knights to find a more optimal solution.

Turns out that if you ignore the rooks you need at least 40 moves to interchange the knights. Obviously you need at least 4 moves to interchange the rooks, so 44 is the hard minimum.

The main idea

is to move the rooks out of the way (a1 & b3), move the knights almost to their place and try to move the rooks in their final places when they no longer inconvenience the knights.

Using the same notation Rand al'Thor proposed for the board with BK - black knight, WK - white knight, BR - black rook, WR - white rook:

d3-----b2-----a4-----c3-----b1-----a3-----c2-----a1-----b3
                     |
                     a2

Here is how 44 moves can be achieved:

Starting position

BK-----BK-----WK-----c3-----BR-----WR-----c2-----a1-----b3
                     |
                     WK

2 moves to get rooks out of the way

BK-----BK-----WK-----c3-----b1-----a3-----c2-----BR-----WR
                     |
                     WK

12 moves to get BKs out of the way of the WK at a2

d3-----b2-----a4-----c3-----BK-----BK-----WK-----BR-----WR
                     |
                     WK

4 moves to get first WK into place at d3

WK-----b2-----a4-----c3-----BK-----BK-----WK-----BR-----WR
                     |
                     a2

9 moves to get second WK close to a2

WK-----BK-----BK-----WK-----b1-----a3-----c2-----BR-----WR
                     |
                     a2

1+6 moves to get second WK to a2 and the BKs out of the way

WK-----b2-----a4-----c3-----BK-----BK-----c2-----BR-----WR
                     |
                     WK

2+1+1 moves to get second WK close to b2 and the BKs close to their spot

WK-----b2-----WK-----BK-----BK-----a3-----c2-----BR-----WR
                     |
                     a2

1 move to get BR into position

WK-----b2-----WK-----BK-----BK-----BR-----c2-----a1-----WR
                     |
                     a2

1+1 move to get first BK into position at a2 and second BK close, at c3

WK-----b2-----WK-----BK-----b1-----BR-----c2-----a1-----WR
                     |
                     BK

1 move to get WR into position

WK-----b2-----WK-----BK-----WR-----BR-----c2-----a1-----b3
                     |
                     BK

2 moves to get the last WK and BK into position

WK-----WK-----BK-----c3-----WR-----BR-----c2-----a1-----b3
                     |
                     BK

Total moves 44 = 2 + 12 + 4 + 9 + 1+6 + 2+1+1 + 1 + 1+1 + 1 + 2

Analysing the setup

Using the following labelling of squares:

labelled grid

We find that the squares are all joined by knight moves as follows:

d3-----b2-----a4-----c3-----b1-----a3-----c2-----a1-----b3
                      |
                      |
                      |
                     a2

So the initial position is as follows (where red = white, blue = black, square = knight, circle = rook):

setup

In order to exchange the knights, we will need to move at least some of them out to the right on this diagram, which means getting the rooks out of the way. The initial setup has both black (blue) knights on the far left, so we want to end up with both white (red) knights on the far left.

The step-by-step solution

  1. We start by stowing the rooks at a1 (black) and b3 (white), out to the right of the above diagram, so that the knights have room to manoeuvre. (2 moves.)

  2. Then we move the white knights out to b1 and a3, to give the black knights some room to move into position. (5 moves.)

  3. Then we move one black knight down to a2. (3 moves.) Now the state of play is:

    new state of play

  4. Look at that leeway at c2! We move the white knights BACK to b2 and a4, then the black knight from a2 out to c2. (10 moves.) Then we move the white knights to b1 and a3 AGAIN, and the black knight from d3 down to a2. (10 moves.) And finally we're in good shape:

    looking good!

  5. Move the white knight from b1 out to d3, where it can stay, and move the white and black knights from a3 and c2 to a4 and c3 - we'll see in a minute why not all the way to b2 and a4. (10 moves.) Now we have an opportunity to move the white rook from b3, through b2 which is conveniently empty, to its final home in b1, and THEN to move the white and black knights from a4 and c3 to their final homes in b2 and a4. (3 moves.) Finally, move the other black knight from a2 to c3, giving the black rook room to move from a1 to its final home in a3, before moving that black knight back to a2. (3 moves.)

Total: $2+5+3+10+10+10+3+3=46$ moves. We did it!

Label the squares as follows:
enter image description here
The following move sequence should solve the puzzle in 49 moves, if I recorded things correctly. It may be possible to solve the puzzle in one or two moves shorter though, but I think this is pretty close to optimal:

 a2-c3
 b1-a1
 c3-b1
 a4-c1
 a3-b3
 b1-a3
 c3-b1
 b2-a4
 a4-c3
 c3-a2
 b1-c3
 c3-a4
 a4-b2
 a3-b1
 b1-c3
 c3-a4
 a2-c3
 c3-b1
 b1-a3
 a3-c2
 a4-c3
 a1-a4
 b3-a3
 a3-a1
 a4-a3
 a3-b3
 c3-b1
 b1-a3
 b2-a4
 a4-c3
 c3-b1
 d3-b2
 b2-a4
 a4-c3
 c3-a2
 b1-c3
 c3-a4
 a4-b2
 b2-d3
 a3-b1
 b1-c3
 c3-a4
 a4-b2
 c2-a3
 a3-b1
 b1-c3
 c3-a4
 b3-a3
 a1-b1

Some analysis:

As with Rand al'Thor, I also considered the movement of the knights, and indeed this is the bulk of the problem.
enter image description here
Two moves are needed to push the two starting rooks into the two end spots that are unused in our diagram, five moves to swap their positions, and two more moves are needed to push the two rooks back.

  • Nice! You found a correct answer first :-) Unless I've miscounted, though, 49 isn't optimal. – Rand al'Thor May 24 at 1:01
  • Ah, you moved the rooks in a smarter way. That was definitely something I did consider to be a potential improvement. – phenomist May 24 at 1:12

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.