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.
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
Using the following labelling of squares:
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):
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.
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.)
Then we move the white knights out to b1 and a3, to give the black knights some room to move into position. (5 moves.)
Then we move one black knight down to a2. (3 moves.) Now the state of play is:
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:
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:
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.
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.
