# Is there a configuration of the 8-puzzle where locking a tile makes it harder?

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?

• Can you explain the puzzle? – Dr Xorile Feb 22 '19 at 14:03
• 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. – Jaap Scherphuis Feb 22 '19 at 14:22
• Indeed, @JaapScherphuis. I have taken some of your words to clarify the question. – Anaphory Feb 22 '19 at 14:40

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--;
// 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))
{
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);
}
}
}