Swapping rooks in a 4x4 board

Question

You have a 4x4 chessboard with four black rooks on the top and four white rooks in the bottom.

Your goal is to swap these rooks using the minimum number of steps. It does not matter which rook is which, as long as there are four white rooks on the top and four black rooks in the bottom.

Chess rules apply: rooks can move any number of squares, horizontally (left and right) or vertically (up and down), as long as there is not another piece on the way. White starts. You must alternate black and white moves.

Answer 1

I wrote a computer program and it showed that $18$ moves is the optimum.

Here is one such solution:

    bbbb   bbbb   .bbb   .bbb   .bb.   .bb.
    ....   ....   b...   bw..   bw..   b..w
    ....   w...   w...   w...   w..b   w..b
    wwww   .www   .www   ..ww   ..ww   ..ww


    ..b.   ..bw   .b.w   .bww   .bww   .bww
    b..w   b...   b...   b...   b...   b...
    w..b   w..b   w..b   w..b   w..b   w..b
    .bww   .bww   .bww   .b.w   b..w   b.w.


    ..ww   .w.w   .w.w   .www   .www   wwww   wwww
    b...   b...   b...   b...   ..b.   ..b.   ....
    w..b   w..b   w...   w...   w...   ....   ....
    bbw.   bbw.   bbwb   bb.b   bb.b   bb.b   bbbb

Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.

For $3\times3$ the optimal number of moves is $16$.

   bbb   bbb   bb.   bb.   .b.   .b.   ...   w..
   ...   w..   w.b   .wb   .wb   w.b   wbb   .bb
   www   .ww   .ww   .ww   bww   bww   bww   bww


   w..   ww.   ww.   www   www   ww.   ww.   www   www
   b.b   b.b   bb.   bb.   bb.   bbw   b.w   b..   ...
   bww   b.w   b.w   b..   ..b   ..b   .bb   .bb   bbb

Without the need to alternate moves the optimum is $14$ moves, for example just by doing the above solution excluding white's last two moves.

Here is the C# source code that I wrote.

using System;
using System.Collections.Generic;
namespace test
{
   class Rooks
   {
      static void Main()
      {
         Calc(true,4);
      }
      static void Calc(bool alternateMoves, int n )
      {
         int[] dirs = {0, 1, 0, -1, 1, 0, -1, 0};
         List<String> list = new List<String>();
         Dictionary<String, String> dict = new Dictionary<String, String>();

         string start = new string('b', n) + new string('.', n * (n - 2)) + new string('w', n);
         if (alternateMoves) start += '0';
         string goal = new string('w', n) + new string('.', n * (n - 2)) + new string('b', n);

         list.Add(start);
         dict.Add(start, "");
         int n1 = list.Count;
         int n2 = 0;
         int len = 0;

         while (list.Count > 0)
         {
            String p = list[0];
            list.RemoveAt(0);
            n1--;
            String gen = dict[p];
            char player = alternateMoves  ? (p[n * n] == '0' ? 'w' : 'b') : '.';
            for (int y = 0; y < n; y++)
            {
               for (int x = 0; x < n; x++)
               {
                  if (!alternateMoves ^ p[y * n + x] == player)
                  {
                     for (int d = 0; d < 4; d++)
                     {
                        int dx = dirs[d + d];
                        int dy = dirs[d + d + 1];
                        int x2 = x;
                        int y2 = y;
                        while (true)
                        {
                           x2 += dx;
                           y2 += dy;
                           if (y2 < 0 || x2 < 0 || y2 >= n || x2 >= n || p[y2 * n + x2] != '.') break;
                           string q = SwapPieces(p, y * n + x, y2 * n + x2);
                           if(alternateMoves) q = q.Substring(0, n * n) + (char) (q[n * n] ^ 1);
                           if (!dict.ContainsKey(q))
                           {
                              list.Add(q);
                              string gen2 = gen + " " + (char)('A' + x) + (char)('1' + y) + (char)('A' + x2) + (char)('1' + y2);
                              dict.Add(q, gen2);
                              if (q.StartsWith(goal))
                              {
                                 Console.WriteLine(q + "  " + gen2);
                              }
                              n2++;
                           }
                        }
                     }
                  }
               }
            }
            if (n1 == 0)
            {
               len++;
               Console.WriteLine("{0}: {1}",len,n2);
               n1 = n2;
               n2 = 0;
            }
         }
      }
      static String SwapPieces(String input, int i1, int i2)
      {
         if (i1 > i2) return SwapPieces(input, i2, i1);
         return input.Substring(0, i1) + input.Substring(i2, 1) + input.Substring(i1 + 1, i2 - i1 - 1) + input.Substring(i1, 1) + input.Substring(i2 + 1);
      }
   }
}

Answer 2

Got 19 by moving around... might be possible to do better:

1) a1-a3
2) d4-d2
3) b1-b3
4) d2-a2
5) d1-d4
6) a2-a1
7) c1-d1
8) c4-c1
9) b3-c3
10) b4-b1
11) a3-b3
12) a4-a2
13) d4-a4
14) a2-c2
15) d1-d4
16) c2-d2
17) b3-b4
18) d2-d1
19) c3-c4

Answer 3

This is not a (new) answer to the original question, but I don't have enough reputation to comment. I tried to address the call for generalization using a similar technique as Jaap. Below the results for the board sizes that fit in my main memory. Unfortunately, 6 x 6 does not fit.

size    # configs  w   b
=========================
3 x 2         180  12  13
3 x 3        3360  16  17
3 x 4       69300  20  19
3 x 5     1513512  24  23
3 x 6    34306272  26  27
3 x 7   798145920  30  31

4 x 2         840  10  11
4 x 3       36960  14  15
4 x 4     1801800  18  19
4 x 5    93117024  22  23
4 x 6  4997280288  26  27

5 x 2        2520  10  11
5 x 3      200200  14  13
5 x 4    17635800  18  17
5 x 5  1647455040  22  21

6 x 2        5940  10  11
6 x 3      742560  14  13
6 x 4   102965940  18  17

7 x 2       12012  10  11
7 x 3     2170560  14  13
7 x 4   435134700  18  17

8 x 2       21840  10  11
8 x 3     5383840  14  13
8 x 4  1472562000  18  17

The last two columns give the minimal number of steps (ply) to the final position with either white (w) or black (b) to play.

The number of configurations is given by: $2 \cdot {n \cdot m \choose m} \cdot {n \cdot m - m \choose m}$, with $n$ the number of rows and $m$ the number of columns.

Answer 4

Found a solution in 20, though I have no idea if it's optimal. One of my assumptions was that "Chess rules apply" meant I had to alternate black and white moves.

Answer 5

Found a 19 move solution, but no idea about optimum.

a1-a3
a3-d3
b1-b2
b2-d2
a4-a1
b4-b1
c1-c2
c2-a2
a2-a4
c4-c1
d4-c4
c4-c3
d3-d4
d4-b4
d2-d4
d4-c4
d1-d4
c3-d3
d3-d1

Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.

Answer 6

EDIT: As @greenturtle pointed out in a comment, it seems that everyone else is doing the count by ply, and not the whole moves. The question is unclear to me about this on how the count is done. So thus my count is wrong by the majority's decision.

As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below answer.

$1.$ Rh2 Rg3 $2.$ Rff2 Ree3 $3.$ Re2 Rh3 $4.$ Rg1 Rf4 $5.$ Rhf2 Reg3 $6.$ Rff1 Rgg4 $7.$ Ree1 Rhh4 $8.$ R4e2 R1h3 $9.$ Rh2 Re3 $10.$ Rhh1 Ree4

I found a solution in 12 moves. Here is a link to a GIF using Apronus. I'm using an 8 x 8 board for convenience in the gif, but I'm treating it as 4 x 4.

The following notation for my solution assumes that the files used are e through h and the ranks are 1 through 4, with the board being as it is from White's view on a normal chess board.

My Solution:

$1.$ Rg3 Rh2 $2.$ Rh3 Rhg2 $3.$ Rh4 Rg1 $4.$ R1h3 R4g2 $5.$ Rg3 Rh2 $6.$ Rgg4 Rhh1 $7.$ Re3 Rf2 $8.$ Rf3 Rfe2 $9.$ Rff4 Re1 $10.$ R1f3 R4e2 $11.$ Re3 Rf2 $12.$ Ree4 Rff1

I'm fairly sure that this is optimal due to how each rook moves a minimum of three times.