29
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • 4
    $\begingroup$ This is the type of question which might make a good secondary puzzle along the lines of "how many steps does it take to swap rooks on an nxn board"! (+1) $\endgroup$ – Adam Jun 19 at 22:25
  • 2
    $\begingroup$ Yes, I thought about that. In a 3x3 board I was able to do in 14 moves, but I'm not sure if it is the optimal solution. I also don't think it would be a good idea to open a new question for a 3x3, 5x5, 8x8, etc. $\endgroup$ – Chaotic Jun 19 at 22:33
  • $\begingroup$ Not necessarily, but the generalization is a worthy question to ask, though perhaps not by itself not that you've asked the instance for n = 4. Still, I do believe this should generalize quite nicely. $\endgroup$ – greenturtle3141 Jun 20 at 0:16
  • 1
    $\begingroup$ I'm fairly sure that for a 3*3, 9 is optimal. Set up the rooks on the f-h files and ranks 1-3 and follow these moves: 1. Rh2 Rg2 2. Rgh3 Rg3 3. Rff2 Rhg1 4. Rh1 R1g2 5. Rg1 Rh2 6. Rfg2 Rff3 7. Rf2 Rhg2 8. Rhh1 Rh2 9. Rff1 Rhh3. $\endgroup$ – Rewan Demontay Jun 20 at 1:52
  • 4
    $\begingroup$ @Adam: the sequence {R(n)} of minimum rook moves R(n) for an n x n board swapping n rooks on top/bottom rows would make a great series in OEIS. I just checked and it doesn't exist. $\endgroup$ – smci Jun 21 at 0:02
35
$\begingroup$

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);
      }
   }
}
$\endgroup$
  • $\begingroup$ Clever! How did you write this program? Was there some logic or just brute force? $\endgroup$ – shoopi Jun 20 at 10:10
  • $\begingroup$ I'd be curious to the results for 3x3, 5x5, 6x6, etc. Is your program flexible enough to find the answers with little effort? I wonder if the answer appears in oeis.org $\endgroup$ – David Dubois Jun 20 at 10:36
  • 3
    $\begingroup$ My program was brute force, simply a breadth first search. There are fewer than a million possible positions (twice that if you include whose turn it is to move) so it can be done in memory. I have added the $3\times3$ results to my answer. $5\times5$ is theoretically feasible by the same method but my program would require a rewrite to be much more memory efficient. Larger boards need a very different method because the number of positions is too great. $\endgroup$ – Jaap Scherphuis Jun 20 at 11:25
  • 3
    $\begingroup$ @Kebabman I have added the C# source code to my answer. $\endgroup$ – Jaap Scherphuis Jun 20 at 13:11
  • 2
    $\begingroup$ @MikeTheLiar I know, and I think that is only possible if you allow consecutive moves to use the same colour pieces, and not possible if you strictly alternate the colours of the moved pieces. $\endgroup$ – Jaap Scherphuis Jun 21 at 14:23
9
$\begingroup$

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

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Step 14 seems to be a pointless move. Just do step 15 first and then a2-d2. $\endgroup$ – James Coyle Jun 20 at 11:19
  • 1
    $\begingroup$ @JamesCoyle Step 14 is indeed a pointless move just to pass the turn. But I can't play move 15 (d1-d4) before I play move 13 (d4-a4) because the square is occupied. This is why I suspected a more optimal solution exists, as proven in Jaap's solution. $\endgroup$ – shoopi Jun 20 at 11:55
  • 2
    $\begingroup$ Ah I totally forgot about alternating moves... $\endgroup$ – James Coyle Jun 20 at 12:02
4
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ I have 2 that are different and 20 and I am not sure either. $\endgroup$ – Duck Jun 19 at 22:06
  • $\begingroup$ Thanks, I've added the clarification. $\endgroup$ – Chaotic Jun 19 at 22:15
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ OP made an edit - moves must alternate between White and Black. $\endgroup$ – shoopi Jun 19 at 23:11
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Seems like the metric everyone else has adopted is total number of rook moves, in which case you'd have 24. I think people are reducing this to 20 by cleverly getting some rooks to the other side in one move. $\endgroup$ – greenturtle3141 Jun 20 at 2:06
  • 1
    $\begingroup$ Oh. Well than the question should speifcy that the count is in ply, not in whole moves as I thought. $\endgroup$ – Rewan Demontay Jun 20 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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