cube files
Indexed Cube Lovers Archive
5x5 sliding puzzle can be solved in 205 moves
Submitted by Ben Whitmore on Fri, 01/26/2018 - 17:46.
Consider a 5x5 sliding puzzle with the solved state
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24We can solve the puzzle in three steps. First solve 1,2,3,4,5,6,7, then solve 8,9,10,11,12,16,17,21,22, and finally solve the 8 puzzle in the bottom right corner. Step 1 requires 91 moves:
depth new total 0 18 18 1 6 24 2 13 37 3 27 64 4 54 118 5 117 235 6 231 466 7 443 909 8 786 1695 9 1448 3143 10 2597 5740 11 4816 10556 12 8532 19088 13 15472 34560 14 26748 61308 15 47183 108491 16 79496 187987 17 136672 324659 18 224636 549295 19 376088 925383 20 600761 1526144 21 977539 2503683 22 1515075 4018758 23 2393571 6412329 24 3601325 10013654 25 5527589 15541243 26 8069297 23610540 27 12022277 35632817 28 17021031 52653848 29 24627525 77281373 30 33844614 111125987 31 47586505 158712492 32 63514288 222226780 33 86887502 309114282 34 112774814 421889096 35 150314361 572203457 36 189957201 762160658 37 246973888 1009134546 38 304170270 1313304816 39 386085891 1699390707 40 463529743 2162920450 41 574570371 2737490821 42 672500485 3409991306 43 813816527 4223807833 44 928097024 5151904857 45 1095799490 6247704347 46 1216751429 7464455776 47 1400776123 8865231899 48 1513349352 10378581251 49 1697763464 12076344715 50 1783569892 13859914607 51 1948622983 15808537590 52 1989357113 17797894703 53 2115033986 19912928689 54 2096685318 22009614007 55 2167372761 24176986768 56 2084209967 26261196735 57 2092375966 28353572701 58 1949444991 30303017692 59 1898272010 32201289702 60 1711178109 33912467811 61 1613791967 35526259778 62 1405324573 36931584351 63 1281373441 38212957792 64 1075889326 39288847118 65 946422379 40235269497 66 764388688 40999658185 67 647094763 41646752948 68 501331438 42148084386 69 407273182 42555357568 70 301651766 42857009334 71 234365835 43091375169 72 165264320 43256639489 73 122305698 43378945187 74 81667733 43460612920 75 57231802 43517844722 76 35912967 43553757689 77 23653330 43577411019 78 13820185 43591231204 79 8478741 43599709945 80 4550561 43604260506 81 2555472 43606815978 82 1235541 43608051519 83 621129 43608672648 84 262060 43608934708 85 112429 43609047137 86 39245 43609086382 87 13409 43609099791 88 3407 43609103198 89 706 43609103904 90 87 43609103991 91 9 43609104000 92 0 43609104000Step 2 requires 84 moves:
depth new total 0 9 9 1 6 15 2 11 26 3 20 46 4 40 86 5 85 171 6 159 330 7 299 629 8 545 1174 9 1001 2175 10 1830 4005 11 3324 7329 12 5953 13282 13 10669 23951 14 18987 42938 15 33495 76433 16 58330 134763 17 101083 235846 18 173039 408885 19 294498 703383 20 494067 1197450 21 823164 2020614 22 1353950 3374564 23 2214163 5588727 24 3573928 9162655 25 5733208 14895863 26 9069793 23965656 27 14247674 38213330 28 22071656 60284986 29 33889391 94174377 30 51266714 145441091 31 76735420 222176511 32 113083778 335260289 33 164597031 499857320 34 235684483 735541803 35 332870380 1068412183 36 462213490 1530625673 37 632425747 2163051420 38 850238821 3013290241 39 1125671656 4138961897 40 1463511574 5602473471 41 1873186675 7475660146 42 2353402676 9829062822 43 2909790637 12738853459 44 3530532007 16269385466 45 4213385459 20482770925 46 4933988628 25416759553 47 5678800914 31095560467 48 6413837131 37509397598 49 7113857320 44623254918 50 7743843883 52367098801 51 8270017065 60637115866 52 8670245074 69307360940 53 8907608786 78214969726 54 8986369519 87201339245 55 8872198502 96073537747 56 8603675858 104677213605 57 8153719906 112830933511 58 7590423939 120421357450 59 6895662414 127317019864 60 6151170762 133468190626 61 5346220516 138814411142 62 4557885007 143372296149 63 3779181153 147151477302 64 3067889459 150219366761 65 2417318650 152636685411 66 1858658948 154495344359 67 1384259292 155879603651 68 1000825045 156880428696 69 699567548 157579996244 70 471239409 158051235653 71 306330726 158357566379 72 190084789 158547651168 73 113468754 158661119922 74 63857593 158724977515 75 34265655 158759243170 76 17003083 158776246253 77 7866868 158784113121 78 3246307 158787359428 79 1194858 158788554286 80 363662 158788917948 81 93145 158789011093 82 16830 158789027923 83 2380 158789030303 84 97 158789030400 85 0 158789030400Step 3 requires 30 moves. The distribution of 8 puzzle is well known and it shows that the puzzle can be solved in 31 moves. However, after we finish step 2, the empty space will be in either position 13, 14, 15, 18, or 23. There are only 2 positions on 8 puzzle that require 31 moves and neither of them have the empty space in any of these positions, so stage 3 can be solved in 30 moves for a total of 91+84+30=205 moves.
