31
$\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 '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 '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 '19 at 0:16
  • 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 '19 at 0:02
  • $\begingroup$ @RewanDemontay: seems clearer to use a-c files rather than f-h. Or just use Long algebraic notation (origin, dest) since with so many rooks of same color, move notation could get ambiguous. $\endgroup$ – smci Jun 21 '19 at 0:04
36
$\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);
      }
   }
}
| improve this answer | |
$\endgroup$
  • $\begingroup$ Clever! How did you write this program? Was there some logic or just brute force? $\endgroup$ – shoopi Jun 20 '19 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 '19 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 '19 at 11:25
  • 3
    $\begingroup$ @Kebabman I have added the C# source code to my answer. $\endgroup$ – Jaap Scherphuis Jun 20 '19 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 '19 at 14:23
10
$\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

| improve this answer | |
$\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 '19 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 '19 at 11:55
  • 2
    $\begingroup$ Ah I totally forgot about alternating moves... $\endgroup$ – James Coyle Jun 20 '19 at 12:02
5
$\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.

| improve this answer | |
$\endgroup$
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

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have 2 that are different and 20 and I am not sure either. $\endgroup$ – Duck Jun 19 '19 at 22:06
  • $\begingroup$ Thanks, I've added the clarification. $\endgroup$ – Chaotic Jun 19 '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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ OP made an edit - moves must alternate between White and Black. $\endgroup$ – shoopi Jun 19 '19 at 23:11
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.

| improve this answer | |
$\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 '19 at 2:06

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.