Solutions for the 3*3 sliding block puzzle ("8-puzzle") for 3 different initial locations of the blank square. Author: Hugo Pfoertner http://www.pfoertner.org/ Date of last change: Nov 19, 2003 See also the corresponding entries in Neil Sloane's On-Line Encyclopedia of Integer Sequences: http://www.research.att.com/projects/OEIS?Anum=A089473 http://www.research.att.com/projects/OEIS?Anum=A089474 http://www.research.att.com/projects/OEIS?Anum=A089483 The following 1-d numbering is used: 123 456 789 Position | Number of targets | | Positions of | | targets 1 2 4 2 2 3 5 1 3 3 2 6 2 4 3 1 7 5 5 4 2 8 4 6 6 3 3 9 5 7 2 4 8 8 3 5 7 9 9 2 6 8 OEIS A089473 Init: 123 456 78 Move Total Configs Configs reachable in n-th move 1 3 2 2 7 4 3 15 8 4 31 16 5 51 20 6 90 39 7 152 62 8 268 116 9 420 152 10 706 286 11 1102 396 12 1850 748 13 2874 1024 14 4767 1893 15 7279 2512 16 11764 4485 17 17402 5638 18 26931 9529 19 37809 10878 20 54802 16993 21 71912 17110 22 95864 23952 23 116088 20224 24 140135 24047 25 155713 15578 26 170273 14560 27 176547 6274 28 180457 3910 29 181217 760 30 181438 221 31 181440 2 Shortest path 1 back to starting config 181439 8 6 7 2 5 4 3 9 1 181261 8 6 7 2 5 4 3 1 9 180564 8 6 7 2 5 9 3 1 4 176925 8 6 9 2 5 7 3 1 4 170752 8 9 6 2 5 7 3 1 4 156517 8 5 6 2 9 7 3 1 4 140838 8 5 6 2 1 7 3 9 4 117004 8 5 6 2 1 7 3 4 9 96561 8 5 6 2 1 9 3 4 7 72612 8 5 9 2 1 6 3 4 7 55271 8 9 5 2 1 6 3 4 7 38244 8 1 5 2 9 6 3 4 7 27186 8 1 5 9 2 6 3 4 7 17616 8 1 5 3 2 6 9 4 7 11884 8 1 5 3 2 6 4 9 7 7372 8 1 5 3 2 6 4 7 9 4817 8 1 5 3 2 9 4 7 6 2909 8 1 5 3 9 2 4 7 6 1868 8 1 5 9 3 2 4 7 6 1115 9 1 5 8 3 2 4 7 6 713 1 9 5 8 3 2 4 7 6 426 1 5 9 8 3 2 4 7 6 272 1 5 2 8 3 9 4 7 6 154 1 5 2 8 9 3 4 7 6 91 1 5 2 9 8 3 4 7 6 52 1 5 2 4 8 3 9 7 6 32 1 5 2 4 8 3 7 9 6 16 1 5 2 4 9 3 7 8 6 8 1 9 2 4 5 3 7 8 6 4 1 2 9 4 5 3 7 8 6 2 1 2 3 4 5 9 7 8 6 1 1 2 3 4 5 6 7 8 9 Shortest path 2 back to starting config 181440 6 4 7 8 5 9 3 2 1 181290 6 4 7 8 5 1 3 2 9 180632 6 4 7 8 5 1 3 9 2 177158 6 4 7 8 5 1 9 3 2 171036 6 4 7 9 5 1 8 3 2 157031 9 4 7 6 5 1 8 3 2 141291 4 9 7 6 5 1 8 3 2 117588 4 7 9 6 5 1 8 3 2 96996 4 7 1 6 5 9 8 3 2 73068 4 7 1 6 9 5 8 3 2 55566 4 9 1 6 7 5 8 3 2 38501 4 1 9 6 7 5 8 3 2 27339 4 1 5 6 7 9 8 3 2 17733 4 1 5 6 7 2 8 3 9 11951 4 1 5 6 7 2 8 9 3 7426 4 1 5 6 7 2 9 8 3 4848 4 1 5 9 7 2 6 8 3 2928 4 1 5 7 9 2 6 8 3 1879 4 1 5 7 8 2 6 9 3 1124 4 1 5 7 8 2 9 6 3 718 4 1 5 9 8 2 7 6 3 429 9 1 5 4 8 2 7 6 3 273 1 9 5 4 8 2 7 6 3 155 1 5 9 4 8 2 7 6 3 92 1 5 2 4 8 9 7 6 3 53 1 5 2 4 8 3 7 6 9 32 1 5 2 4 8 3 7 9 6 16 1 5 2 4 9 3 7 8 6 8 1 9 2 4 5 3 7 8 6 4 1 2 9 4 5 3 7 8 6 2 1 2 3 4 5 9 7 8 6 1 1 2 3 4 5 6 7 8 9 OEIS A089474 Init: 123 4 5 678 Move Total Configs Configs reachable in n-th move 1 5 4 2 13 8 3 21 8 4 37 16 5 69 32 6 129 60 7 201 72 8 337 136 9 537 200 10 913 376 11 1425 512 12 2389 964 13 3685 1296 14 6053 2368 15 9137 3084 16 14619 5482 17 21355 6736 18 32487 11132 19 44695 12208 20 63307 18612 21 81751 18444 22 106719 24968 23 126351 19632 24 148640 22289 25 162240 13600 26 174082 11842 27 178422 4340 28 180820 2398 29 181292 472 30 181440 148 Shortest path 1 back to starting config 181293 4 7 6 2 9 8 3 5 1 180821 4 7 6 2 5 8 3 9 1 178423 4 7 6 2 5 8 9 3 1 174083 4 7 6 9 5 8 2 3 1 162241 9 7 6 4 5 8 2 3 1 148641 7 9 6 4 5 8 2 3 1 126352 7 5 6 4 9 8 2 3 1 106721 7 5 6 4 3 8 2 9 1 81753 7 5 6 4 3 8 2 1 9 63309 7 5 6 4 3 9 2 1 8 44696 7 5 6 4 9 3 2 1 8 32488 7 9 6 4 5 3 2 1 8 21356 7 6 9 4 5 3 2 1 8 14620 7 6 3 4 5 9 2 1 8 9138 7 6 3 4 9 5 2 1 8 6054 7 6 3 9 4 5 2 1 8 3686 9 6 3 7 4 5 2 1 8 2390 6 9 3 7 4 5 2 1 8 1426 6 4 3 7 9 5 2 1 8 914 6 4 3 7 1 5 2 9 8 538 6 4 3 7 1 5 9 2 8 338 6 4 3 9 1 5 7 2 8 202 9 4 3 6 1 5 7 2 8 130 4 9 3 6 1 5 7 2 8 70 4 1 3 6 9 5 7 2 8 38 4 1 3 6 2 5 7 9 8 22 4 1 3 6 2 5 9 7 8 14 4 1 3 9 2 5 6 7 8 6 9 1 3 4 2 5 6 7 8 2 1 9 3 4 2 5 6 7 8 1 1 2 3 4 9 5 6 7 8 [... 146 paths ...] Shortest path 148 back to starting config 181440 9 8 6 7 2 4 3 5 1 181232 7 8 6 9 2 4 3 5 1 180378 7 8 6 3 2 4 9 5 1 177278 7 8 6 3 2 4 5 9 1 170039 7 8 6 3 2 4 5 1 9 156777 7 8 6 3 2 9 5 1 4 138787 7 8 9 3 2 6 5 1 4 117052 7 9 8 3 2 6 5 1 4 94172 7 2 8 3 9 6 5 1 4 71912 7 2 8 3 1 6 5 9 4 53114 7 2 8 3 1 6 5 4 9 37792 7 2 8 3 1 9 5 4 6 26031 7 2 9 3 1 8 5 4 6 17353 7 9 2 3 1 8 5 4 6 11293 7 1 2 3 9 8 5 4 6 7250 7 1 2 9 3 8 5 4 6 4580 7 1 2 5 3 8 9 4 6 2876 7 1 2 5 3 8 4 9 6 1781 7 1 2 5 3 8 4 6 9 1101 7 1 2 5 3 9 4 6 8 679 7 1 2 5 9 3 4 6 8 412 7 1 2 9 5 3 4 6 8 252 9 1 2 7 5 3 4 6 8 155 1 9 2 7 5 3 4 6 8 92 1 2 9 7 5 3 4 6 8 49 1 2 3 7 5 9 4 6 8 27 1 2 3 7 9 5 4 6 8 16 1 2 3 9 7 5 4 6 8 8 1 2 3 4 7 5 9 6 8 3 1 2 3 4 7 5 6 9 8 1 1 2 3 4 9 5 6 7 8 OEIS A089483 Init: 1 2 345 678 Move Total Configs Configs reachable in n-th move 1 4 3 2 9 5 3 19 10 4 33 14 5 61 28 6 103 42 7 183 80 8 291 108 9 493 202 10 771 278 11 1295 524 12 2021 726 13 3369 1348 14 5173 1804 15 8456 3283 16 12649 4193 17 19971 7322 18 28567 8596 19 42497 13930 20 57210 14713 21 78931 21721 22 98758 19827 23 123890 25132 24 142087 18197 25 161065 18978 26 170994 9929 27 178353 7359 28 180434 2081 29 181312 878 30 181438 126 31 181440 2 Shortest path 1 back to starting config 181439 8 6 9 5 4 7 2 3 1 181347 8 9 6 5 4 7 2 3 1 180587 9 8 6 5 4 7 2 3 1 178642 5 8 6 9 4 7 2 3 1 171749 5 8 6 2 4 7 9 3 1 161885 5 8 6 2 4 7 3 9 1 143401 5 8 6 2 4 7 3 1 9 125036 5 8 6 2 4 9 3 1 7 100026 5 8 9 2 4 6 3 1 7 79826 5 9 8 2 4 6 3 1 7 58065 9 5 8 2 4 6 3 1 7 43057 2 5 8 9 4 6 3 1 7 29044 2 5 8 4 9 6 3 1 7 20255 2 5 8 4 1 6 3 9 7 12873 2 5 8 4 1 6 3 7 9 8583 2 5 8 4 1 9 3 7 6 5264 2 5 9 4 1 8 3 7 6 3419 2 9 5 4 1 8 3 7 6 2061 9 2 5 4 1 8 3 7 6 1318 4 2 5 9 1 8 3 7 6 783 4 2 5 1 9 8 3 7 6 500 4 2 5 1 7 8 3 9 6 298 4 2 5 1 7 8 3 6 9 187 4 2 5 1 7 9 3 6 8 105 4 2 9 1 7 5 3 6 8 62 4 9 2 1 7 5 3 6 8 34 9 4 2 1 7 5 3 6 8 20 1 4 2 9 7 5 3 6 8 10 1 4 2 3 7 5 9 6 8 5 1 4 2 3 7 5 6 9 8 2 1 4 2 3 9 5 6 7 8 1 1 9 2 3 4 5 6 7 8 Shortest path 2 back to starting config 181440 9 8 6 7 4 3 2 5 1 181378 7 8 6 9 4 3 2 5 1 180724 7 8 6 2 4 3 9 5 1 178944 7 8 6 2 4 3 5 9 1 172644 7 8 6 2 4 3 5 1 9 162926 7 8 6 2 4 9 5 1 3 145063 7 8 9 2 4 6 5 1 3 126512 7 9 8 2 4 6 5 1 3 101883 7 4 8 2 9 6 5 1 3 81208 7 4 8 2 1 6 5 9 3 59442 7 4 8 2 1 6 5 3 9 43979 7 4 8 2 1 9 5 3 6 29854 7 4 9 2 1 8 5 3 6 20742 7 9 4 2 1 8 5 3 6 13256 7 1 4 2 9 8 5 3 6 8799 7 1 4 9 2 8 5 3 6 5434 7 1 4 5 2 8 9 3 6 3510 7 1 4 5 2 8 3 9 6 2127 7 1 4 5 2 8 3 6 9 1351 7 1 4 5 2 9 3 6 8 811 7 1 4 5 9 2 3 6 8 514 7 1 4 9 5 2 3 6 8 306 9 1 4 7 5 2 3 6 8 191 1 9 4 7 5 2 3 6 8 110 1 4 9 7 5 2 3 6 8 65 1 4 2 7 5 9 3 6 8 35 1 4 2 7 9 5 3 6 8 20 1 4 2 9 7 5 3 6 8 10 1 4 2 3 7 5 9 6 8 5 1 4 2 3 7 5 6 9 8 2 1 4 2 3 9 5 6 7 8 1 1 9 2 3 4 5 6 7 8