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












4












$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?










share|improve this question









New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Can you explain the puzzle?
    $endgroup$
    – Dr Xorile
    13 hours ago






  • 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
    13 hours ago










  • $begingroup$
    Indeed, @JaapScherphuis. I have taken some of your words to clarify the question.
    $endgroup$
    – Anaphory
    12 hours ago
















4












$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?










share|improve this question









New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Can you explain the puzzle?
    $endgroup$
    – Dr Xorile
    13 hours ago






  • 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
    13 hours ago










  • $begingroup$
    Indeed, @JaapScherphuis. I have taken some of your words to clarify the question.
    $endgroup$
    – Anaphory
    12 hours ago














4












4








4





$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?










share|improve this question









New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




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?







construction sliding-blocks






share|improve this question









New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 12 hours ago







Anaphory













New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 13 hours ago









AnaphoryAnaphory

1214




1214




New contributor




Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Anaphory is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    Can you explain the puzzle?
    $endgroup$
    – Dr Xorile
    13 hours ago






  • 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
    13 hours ago










  • $begingroup$
    Indeed, @JaapScherphuis. I have taken some of your words to clarify the question.
    $endgroup$
    – Anaphory
    12 hours ago


















  • $begingroup$
    Can you explain the puzzle?
    $endgroup$
    – Dr Xorile
    13 hours ago






  • 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
    13 hours ago










  • $begingroup$
    Indeed, @JaapScherphuis. I have taken some of your words to clarify the question.
    $endgroup$
    – Anaphory
    12 hours ago
















$begingroup$
Can you explain the puzzle?
$endgroup$
– Dr Xorile
13 hours ago




$begingroup$
Can you explain the puzzle?
$endgroup$
– Dr Xorile
13 hours ago




3




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
13 hours ago




$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
13 hours ago












$begingroup$
Indeed, @JaapScherphuis. I have taken some of your words to clarify the question.
$endgroup$
– Anaphory
12 hours ago




$begingroup$
Indeed, @JaapScherphuis. I have taken some of your words to clarify the question.
$endgroup$
– Anaphory
12 hours ago










1 Answer
1






active

oldest

votes


















12












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





share|improve this answer











$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "559"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    Anaphory is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f79908%2fis-there-a-configuration-of-the-8-puzzle-where-locking-a-tile-makes-it-harder%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    12












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





    share|improve this answer











    $endgroup$


















      12












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





      share|improve this answer











      $endgroup$
















        12












        12








        12





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





        share|improve this answer











        $endgroup$



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






        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited 11 hours ago

























        answered 11 hours ago









        Jaap ScherphuisJaap Scherphuis

        15.4k12569




        15.4k12569






















            Anaphory is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            Anaphory is a new contributor. Be nice, and check out our Code of Conduct.













            Anaphory is a new contributor. Be nice, and check out our Code of Conduct.












            Anaphory is a new contributor. Be nice, and check out our Code of Conduct.
















            Thanks for contributing an answer to Puzzling Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f79908%2fis-there-a-configuration-of-the-8-puzzle-where-locking-a-tile-makes-it-harder%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            How to label and detect the document text images

            Vallis Paradisi

            Tabula Rosettana