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