Htydjtk

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?

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);

    }

  }

}