6
$\begingroup$

I am trying to find a starting configuration of the standard 3×3 8-tile sliding block puzzle that is harder to solve (i.e. takes more moves, but is still solvable) when one of the blocks is locked in place.

+-+-+-+
|1|2|3|
+-+-+-+
|4|5|6|
+-+-+-+
|7|8| |
+-+-+-+

Is there such a configuration? I am specifically looking for a solution configuration that has the gap in the middle, which is at most 2 moves from any other configuration, so it's not a very strong constraint. It also implies that the fixed block is not the middle block, which is not an interesting case anyway.

Obviously, locking an edge tile makes the adjacent corner tiles essentially immovable, which leaves a 2×3 sliding puzzle. (If the gap starts adjacent to the locked edge, the locked version of the puzzle is only solvable if it can be immediately filled by the right tile, reducing it to the 2×3 case immediately.)

The only interesting case is locking a corner tile, which does not change whether the puzzle is solvable. I imagine there could be arrangements where the optimal solution would be shorter if the corner were not locked. How do I find one?

$\endgroup$
  • $\begingroup$ Can you explain the puzzle? $\endgroup$ – Dr Xorile Feb 22 at 14:03
  • 3
    $\begingroup$ So you mean the standard 3x3 sliding puzzle with 8 square tiles and one blank? Locking the centre tile makes for a trivial puzzle - the 7 other tiles can't change places, only be cyclically shifted. Locking an edge tile makes the adjacent corner tiles essentially immovable, so you then just have a 2x3 sliding puzzle left. The only interesting case is locking a corner tile. It won't make it any more difficult to solve in practice, but there could well be arrangements where the optimal solution would be shorter if the corner were not locked. I'll see if I can find that out. $\endgroup$ – Jaap Scherphuis Feb 22 at 14:22
  • $\begingroup$ Indeed, @JaapScherphuis. I have taken some of your words to clarify the question. $\endgroup$ – Anaphory Feb 22 at 14:40
15
$\begingroup$

As far as I know, the only way to figure this out is by letting a computer run through all the possibilities. It is a small puzzle, so this does not take long.


First I will assume that you want the final solved position to have the blank in the bottom right corner, with the tiles in numerical order:

123
456
78.

(See further below for the results with the blank in the centre) The computer starts at this end position, and works backwards to see how many moves it takes to get there from any other position. This takes at most 31 moves:

  0: 1             16: 4485
  1: 2             17: 5638
  2: 4             18: 9529
  3: 8             19: 10878
  4: 16            20: 16993
  5: 20            21: 17110
  6: 39            22: 23952
  7: 62            23: 20224
  8: 116           24: 24047
  9: 152           25: 15578
  10: 286          26: 14560
  11: 396          27: 6274
  12: 748          28: 3910
  13: 1024         29: 760
  14: 1893         30: 221
  15: 2512         31: 2

Then we have to do the same with one of the corner tiles locked. Let's lock tile 1, the tile diagonally opposite the blank space in the final solved arrangement.

Lock Tile 1

  0: 1             18: 1099
  1: 2             19: 1364
  2: 4             20: 1593
  3: 8             21: 1834
  4: 10            22: 2031
  5: 14            23: 2088
  6: 23            24: 1953
  7: 34            25: 1640
  8: 48            26: 1288
  9: 70            27: 924
  10: 94           28: 574
  11: 124          29: 268
  12: 175          30: 122
  13: 268          31: 58
  14: 373          32: 23
  15: 512          33: 4
  16: 667          34: 2
  17: 868

As you can see, there clearly are some arrangements that take longer to solve, as now some need 34 moves. I had the computer compare the results, and it found:

  • 3971 arrangments that take 2 more moves
  • 2176 arrangments that take 4 more moves
  • 1045 arrangments that take 6 more moves
  • 254 arrangments that take 8 more moves
  • 102 arrangments that take 10 more moves

The rest need the same amount. Of those that need 10 more moves, there are 11 that have the space in the centre. They are:

  24/14: 125  132
         7 3  4 6
         486  578

  26/16: 125  128  132
         7 6  7 3  4 7
         438  465  865

         126  132  132
         7 8  4 7  4 8
         435  586  675

  28/18: 132  132
         7 5  7 6
         486  458

  30/20: 132
         7 8
         465

The numbers on the left are the number of moves in the optimal solution.

Lock Tile 3

One could instead lock the corner tile 3. Locking corner 7 is equivalent to locking 3, just reflected in the diagonal.

  0: 1            18: 1047
  1: 2            19: 1317
  2: 3            20: 1568
  3: 7            21: 1821
  4: 11           22: 2014
  5: 13           23: 2102
  6: 19           24: 1997
  7: 35           25: 1688
  8: 46           26: 1317
  9: 58           27: 939
  10: 86          28: 624
  11: 127         29: 343
  12: 174         30: 169
  13: 247         31: 59
  14: 344         32: 20
  15: 480         33: 9
  16: 637         34: 3
  17: 833

Again, some arrangements that take 34 moves. Compared to the standard puzzle, there are:

  • 3821 arrangments that take 2 more moves
  • 2628 arrangments that take 4 more moves
  • 1069 arrangments that take 6 more moves
  • 326 arrangments that take 8 more moves
  • 97 arrangments that take 10 more moves

Of those that need 10 more moves, there are once again 11 that have the space in the centre. They are:

  22/12: 523
         1 8
         476

  26/16: 213  213  213
         4 6  7 5  8 6
         785  864  475

         213  213  483
         5 8  7 6  5 1
         476  584  762

  28/18: 213  423  583
         4 5  1 8  1 4
         768  756  762

  30/20: 213
         4 8
         756

Now I'll assume you want the solved position to have the space in the centre, like this:

123
4 5
678

This can be solved in at most 30 moves, slightly less than the standard solved position.

  0: 1          16: 5482
  1: 4          17: 6736
  2: 8          18: 11132
  3: 8          19: 12208
  4: 16         20: 18612
  5: 32         21: 18444
  6: 60         22: 24968
  7: 72         23: 19632
  8: 136        24: 22289
  9: 200        25: 13600
  10: 376       26: 11842
  11: 512       27: 4340
  12: 964       28: 2398
  13: 1296      29: 472
  14: 2368      30: 148
  15: 3084

Because of the symmetry, we can assume that the locked corner is tile 1. This can be solved in at most 34 moves:

  0: 1           18: 1171
  1: 4           19: 1410
  2: 6           20: 1655
  3: 6           21: 1922
  4: 10          22: 2064
  5: 22          23: 2036
  6: 29          24: 1839
  7: 34          25: 1502
  8: 50          26: 1181
  9: 78          27: 792
  10: 106        28: 499
  11: 148        29: 280
  12: 211        30: 113
  13: 300        31: 38
  14: 409        32: 21
  15: 546        33: 10
  16: 713        34: 2
  17: 952

When the computer compared the above results, it turns out that there are:

  • 3792 arrangments that take 2 more moves
  • 2399 arrangments that take 4 more moves
  • 1221 arrangments that take 6 more moves
  • 320 arrangments that take 8 more moves
  • 94 arrangments that take 10 more moves

Of those 94 that need 10 more moves, there are 9 with the blank in the centre:

  24/14: 125  132  127  132
         6 8  4 6  6 3  4 8
         437  785  485  567

  26,16: 125  132
         6 3  4 5
         478  768

  28,18: 132  132  132
         6 5  6 7  6 8
         478  485  457

Here is the program I slapped together for this. It is written in C#.

using System;
using System.Collections.Generic;
namespace test
{
  class PSESlide8
  {
    static void Main()
    {
      var locked = CalcGodsAlgorithm('3'); // or ('1');
      var free = CalcGodsAlgorithm('z');
      foreach (var pair in locked)
      {
        var pos = pair.Key;
        var lnlocked = pair.Value;
        var lnfree = free[pos];
        if (lnlocked > lnfree)
        {
          Console.WriteLine("{0},{1},{2} : {3}", lnlocked-lnfree, lnlocked, lnfree, pos);
        }
      }
    }
    static Dictionary<string, int> CalcGodsAlgorithm(char fixedtile)
    {
      Dictionary<string,int> visited = new Dictionary<string, int>();
      List<string> todo = new List<string>{"12345678 "};
      int n1 = 1;
      int n2 = 0;
      int ln = 0;
      while (todo.Count > 0)
      {
        string pos = todo[0];
        todo.RemoveAt(0);
        n1--;
        visited.Add(pos,ln);
        // add all neighbours to to-do list
        for (int m = 0; m < 4; m++)
        {
          string pos2 = DoMove(pos, m, fixedtile);
          if (pos2 != null && !visited.ContainsKey(pos2) && !todo.Contains(pos2))
          {
            todo.Add(pos2);
            n2++;
          }
        }
        if (n1 == 0)
        {
          n1 = n2;
          n2 = 0;
          ln++;
          Console.WriteLine("{0}: {1}", ln, n1);
        }
      }
      return visited;
    }
    static string DoMove(string input, int mv, char fixedtile)
    {
      int b = input.IndexOf(" ", StringComparison.Ordinal);
      if (mv == 0 && b >= 3)
      {
        return Swap(input, b, b - 3, fixedtile);
      }
      if (mv == 1 && b < 6)
      {
        return Swap(input, b, b + 3, fixedtile);
      }
      if (mv == 2 && b % 3 != 0)
      {
        return Swap(input, b, b - 1, fixedtile);
      }
      if (mv == 3 && b % 3 != 2)
      {
        return Swap(input, b, b + 1, fixedtile);
      }
      return null;
    }
    static string Swap(string input, int i, int j, char fixedtile)
    {
      if (input[j] == fixedtile) return null;
      if (i > j) return Swap(input, j, i, fixedtile);
      if (i == j) return input;
      return input.Substring(0, i) + input.Substring(j, 1) + input.Substring(i + 1, j - i - 1) +
           input.Substring(i, 1) + input.Substring(j + 1);
    }
  }
}
$\endgroup$

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.