Configuration counts for n*n sliding block puzzles. Results for start with blank square at corner (n,n) Author: Hugo Pfoertner http://www.pfoertner.org/ Version history: Nov 27, 2003 typos corrected Nov 26, 2003 n=2 added Nov 20, 2003 Initial version Results for n=2 =============== The following 1-d numbering is used: 12 34 Neighbor relations: Position | Number of targets | | Positions of | | targets 1 2 3 2 2 2 4 1 3 2 1 4 4 2 2 3 Start: _______ | 1 | 2 | |___|___| | 3 | | |___|___| Move Total Configs Configs reachable in n-th move 1 3 2 2 5 2 3 7 2 4 9 2 5 11 2 6 12 1 Most distant position: _______ | | 3 | |___|___| | 2 | 1 | |___|___| reached by moves 12 4 3 2 1 10 3 4 2 1 8 3 1 2 4 6 3 1 4 2 4 4 1 3 2 2 1 4 3 2 1 1 2 3 4 Results for n=3 =============== OEIS: http://www.research.att.com/projects/OEIS?Anum=A089473 The following 1-d numbering is used: 123 456 789 Initial position of blank square: Row 3, Column 3 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 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 N=4 === OEIS: http://www.research.att.com/projects/OEIS?Anum=A089484 Numbering: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Position | Number of targets | | Positions of | | targets 1 2 5 2 2 3 6 1 3 3 3 7 2 4 4 2 8 3 5 3 1 9 6 6 4 2 10 5 7 7 4 3 11 6 8 8 3 4 12 7 9 3 5 13 10 10 4 6 14 9 11 11 4 7 15 10 12 12 3 8 16 11 13 2 9 14 14 3 10 13 15 15 3 11 14 16 16 2 12 15 Init blank square: Row 4 Column 4 Move Total Configs Configs reachable in n-th move 1 3 2 2 7 4 3 17 10 4 41 24 5 95 54 6 202 107 7 414 212 8 860 446 9 1806 946 10 3754 1948 11 7692 3938 12 15500 7808 13 31044 15544 14 61865 30821 15 122707 60842 16 241707 119000 17 473551 231844 18 920893 447342 19 1780637 859744 N=5 === OEIS: http://www.research.att.com/projects/OEIS?Anum=A090031 Init blank square: Row 5 Column 5 Move Total Configs Configs reachable in n-th move 1 3 2 2 7 4 3 17 10 4 43 26 5 107 64 6 266 159 7 632 366 8 1494 862 9 3398 1904 10 7936 4538 11 18174 10238 12 42272 24098 13 95458 53186 14 218893 123435 15 487309 268416 16 1103683 616374 N=6 === OEIS: http://www.research.att.com/projects/OEIS?Anum=A090032 Init blank square: Row 6 Column 6 Move Total Configs Configs reachable in n-th move 1 3 2 2 7 4 3 17 10 4 43 26 5 109 66 6 280 171 7 720 440 8 1832 1112 9 4618 2786 10 11438 6820 11 28158 16720 12 69264 41106 13 170120 100856 14 415913 245793 15 1012943 597030 16 2454235 1441292