Home »

Regularities in maximum WD values

Submitted by stannic on Sat, 01/14/2012 - 15:26.
Regularities in maximum WD values

This post is about any mathematical laws inside the Walking Distance heuristic. It seems like WD is not just puzzle to be computed. Maybe the whole WD heuristic is some math structure.

First, some conventions.
W×H puzzle is sliding-tile puzzle of width W and height H.
W×H WD pattern is relabeled W×H puzzle configuration with letters A, B, C etc. on tiles instead of numbers (although letters are numbers and used only for evidence: A = 0, B = 1, C = 2 etc.)
Horizontal W×H WD pattern can be obtained by relabeling (i → i % W). Vertical W×H WD pattern can be obtained through relabeling (i → i / W) where / is integer division.
WD matrix is, well, matrix L×L where L is the number of distinct letters in WD pattern.
Horizontal W×H WD matrix is square matrix of order W; in row r and column c of this matrix is the number of repetitions of letter c in column r in horizontal WD pattern.
Vertical WD matrix is square matrix of order H; in row r and column c is the number of repetitions of letter c in row r in vertical WD pattern.
WD matrix can be obtained from corresponding WD pattern.
Set of all horizontal (vertical) WD matrices has the same cardinality as set of all horizontal (vertical) WD patterns. Horizontal (vertical) WD patterns that differ only by rearranging tiles in the same column (row) are considered equal.
The following scheme shows possible relabelings.

   vertical       vertical    4x3 puzzle    horizontal   horizontal
  WD matrix      WD pattern  configuration  WD pattern   WD matrix

    A B C                                   [0|1|2|3]    A B C D
    -----         -------     ----------     -------     -------
[0] 3 1 0     [0] A B A A     1  5  2  3     B B C D     2 1 0 0 [0]
[1] 0 2 2 <-> [1] B C B C <-- 4  9  7 11 --> A B D D <-> 0 2 1 0 [1]
[2] 0 1 2     [2] C C . B     8 10  .  6     A C . C     0 0 1 1 [2]
                                                         0 0 1 2 [3]
    -----         -------     ----------     -------     -------
Vertical relabeling:    1,2,3 -> A   4,5,6,7 -> B   8,9,10,11 -> C
Horizontal relabeling:  4,8 -> A  1,5,9 -> B  2,6,10 -> C  3,7,11 -> D

I'll mainly use WD matrices instead of WD patterns. All WD matrices and WD patterns are vertical unless other specified explicitly.

  6x2 walking distance puzzle
  single antipode at depth 11
   A B
   0 6     B B B B B B
   5 0     A A A A A .

Now to business.

Maximum WD values
   W   2    3    4    5    6    7    8    9   10   11   12
 H  ------------------------------------------------------
 2 |   3    5    7    9   11   13   15   17   19   21   23
 3 |  10   14   18   22   26   30   34   38   42   46   50
 4 |  21   29   35   43   51   59   67   75   83   91   99
 5 |  36   46   58   70   80    -    -    -    -    -    -
 6 |  55   69    -    -    -    -    -    -    -    -    -
 7 |  78    -    -    -    -    -    -    -    -    -    -

This table is mainly extract from Rokicki's table.

In n × 2 case, max. WD value is 2n - 1. There are exactly 2n WD patterns; there is Hamiltonian path through all WD patterns. Goal and antipode patterns in general case shown below, as well as the example.

  Goal    Antipode  Example (n = 6)
 ------    ------   ---------------------------------------------------------------------
 n-1  0     0   n   5 0   5 1   4 1   4 2   3 2   3 3   2 3   2 4   1 4   1 5   0 5   0 6
  0   n    n-1  0   0 6   0 5   1 5   1 4   2 4   2 3   3 3   3 2   4 2   4 1   5 1   5 0
 ------    ------   ---------------------------------------------------------------------
  A   B     A   B     0     1     2     3     4     5     6     7     8     9    10    11

In n × 3 case, max. WD value is 4n + 2 for all n from 2 to 63. I am sure this will be true for all n ≥ 2, but didn't prove this yet.

The table below compares truncated distance distributions for various n × 3 WD puzzles. There are many strange things; for example, for n ≥ 3 there are exactly n configurations at depth 4n + 2, n configurations at depth 4n + 1 and 2n + 1 configurations at depth 4n.

 --------------------------------------------------------------------------
 2x3         3x3            4x3          13x3             63x3
 ---------  ------------   ---------    --------------   ------------------
 d   +   =   d    +    =    d  +   =     d    +      =     d     +        =
 ---------  ------------   ---------    --------------   ------------------
 1   1   2   1    1    2    1  1   2     1    1      2     1     1        2
 2   2   4   2    2    4    2  2   4     2    2      4     2     2        4
 3   2   6   3    2    6    3  2   6     3    2      6     3     2        6
 4   4  10   4    5   11    4  5  11     4    5     11     4     5       11
 5   3  13   5    6   17    5  6  17     5    6     17     5     6       17
 6   7  20   6   15   32    6 16  33     6   16     33     6    16       33
 7   3  23   7    8   40    7 12  45     7   12     45     7    12       45
 8   6  29   8   17   57    8 28  73     8   29     74     8    29       74
 9   2  31   9    9   66    9 16  89    ..  ...  .....   ... .....  .......
10   2  33  10   20   86   10 38 127    46  534  13862   246 12134  6330887
            11    6   92   11 17 144    47  233  14095   247  5858  6336745
            12    7   99   12 35 179    48  358  14453   248  8058  6344803
            13    3  102   13 17 196    49  179  14632   249  4029  6348832
            14    3  105   14 32 228    50  239  14871   250  4339  6353171
                           15 10 238    51   91  14962   251  2016  6355187
                           16  9 247    52   27  14989   252   127  6355314
                           17  4 251    53   13  15002   253    63  6355377
                           18  4 255    54   13  15015   254    63  6355440
 ---------  ------------   ---------    --------------   ------------------
 d   depth
 +     new
 =   total
 --------------------------------------------------------------------------

In n × 4 case, progression slightly breaks. For 2 ≤ n ≤ 3, max. WD value is 8n + 5. For 4 ≤ n ≤ 12 (maybe up to infinity), max. WD value is 8n + 3.

In 2 × n case, maximum WD value is (n - 1)×(2n - 1) for 2 ≤ n ≤ 7. There are two antipodes; below is the example for n = 5.

    A B C D E   A B C D E
    - - - - -   - - - - -
0   0 0 0 0 2   0 0 0 0 2
1   0 0 0 2 0   0 0 0 2 0
2   0 0 2 0 0   0 0 2 0 0
3   0 2 0 0 0   1 1 0 0 0
4   1 0 0 0 0   0 1 0 0 0

In n × 5 and other cases, I cannot see simple enough sequence. Maybe there are some formulas, but to discover these, probably more data are needed. Unfortunately the number of WD patterns quickly grows with W and H. For example, the number of 3 × 3 WD patterns is 105, in 4 × 4 case there are 24,964 patterns; in 5 × 5 case there are 65,650,495 patterns; in 6 × 6 case, there are 2,096,380,208,796 patterns.

There is something similar to pattern in table. Move along diagonals of the table listing maximum WD values. You'll see the following:

  3
  5 10
  7 14 21
  9 18 29 36
 11 22 35 46 55
 13 26 43 58 69 78
 ...

Ideal pattern would be the following:

  3
  5 10
  7 14 21
  9 18 27 36
 11 22 33 44 55
 13 26 39 52 65 78
 ...

Below are links to some previous WD-related posts:

1. Walking Distance
2. More walking distance values
3. 24 puzzle new lower bound: 152
4. Kociemba's optimal solver program

- Bulat
stannic at ymail point com

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Sliding Tile Puzzle Corner

Submitted by stannic on Tue, 02/07/2012 - 23:26.

All information about sliding tile puzzles will be placed under this link. In particular, see sections "Results" and "Walking Distance".

Feel free to comment.

Edit: parallel thread on the speedsolving.com is opened.

Edit (20 Apr 2017): replaced dead links with archive copies.

» login or register to post comments

Computing large WD databases

Submitted by stannic on Sat, 01/21/2012 - 04:10.

Walking distance is always greater than Manhattan Distance, so it is possible to store difference WD - MD instead of WD. Moreover, it seems like difference WD - MD can only take even values. Below are distributions for 3x3, 4x4 and 5x5 puzzles.

  3x3 puzzle     4x4 puzzle        5x5 puzzle
WD-MD  count   WD-MD  count   WD-MD     count
------------   ------------   ---------------
    0     54       0   8549       0  21236245
    2     42       2  11646       2  30506790
    4      9       4   4017       4  11490434
------------       6    626       6   2009020
total    105       8    109       8    336521
                  10     15      10     57194
                  12      2      12     11672
               ------------      14      2201
               total  24964      16       369
                                 18        45
                                 20         4
                              ---------------
                              total  65650495

This paper lists also some other techniques for compression.

Update: Indeed, the difference WD - MD can take only even values. In goal matrix, WD = MD = 0, so WD - MD = 0 is even. Any valid move changes both WD and MD by ±1, therefore WD - MD is always even. So we can store in database (WD - MD)/2.

» login or register to post comments

Antipodes in Nx3 case (still not proved)

Submitted by stannic on Sun, 01/15/2012 - 19:21.

N antipodes at depth 4N + 2 in N × 3 case (N ≥ 3) can be obtained by the following "parametric equation":

     A     B     C   Example (17x3, antipode #3)
-------------------
     0     0     N         0  0 17
     z   N-z     0         3 14  0
 N-1-z     z     0        13  3  0
-------------------
 z = 0,1,...,N-1

N sub-antipodes at depth 4N + 1 can be expressed as the following:

     A     B     C
-------------------
     0     0     N
     z N-1-z     0
 N-1-z   1+z     0
-------------------
z = 0,1,...,N-1

2N + 1 configurations at depth 4N are the following four classes:

(1)                  (2)                (3)              (4)
     A     B     C      A     B     C      A    B    C      A     B     C
-------------------  -----------------  ---------------  -----------------
     0     0   N-1      0     z N-1-z      0    1  N-1      0     0   N-1
     z N-1-z     1      0 N-1-z   1+z      0  N-1    1      0     N     0
 N-1-z   1+z     0    N-1     1     0    N-1    0    0    N-1     0     1
-------------------  -----------------  ---------------  -----------------
z = 0,1,...,N-1      z = 0,1,...,N-1

Classes (1) and (2) contains N configurations each, one of which is both in (1) and (2); so the number of configurations in (1) and (2) is 2N-1. Classes (3) and (4) are single configurations.

Goal is the following:

   A  B  C
----------
 N-1  0  0
   0  N  0
   0  0  N
----------
» login or register to post comments

Lower bound for Nx3 is 4N-2

Submitted by stannic on Thu, 01/19/2012 - 18:13.

The N × 3 "parametric" antipode shown in previous post cannot be solved in less than 4N - 2 moves. This can be shown using WD matrices of this and goal cofigurations. Manhattan distance between these configurations is z + 2(N-1-z) + z + 2N = 4N - 2.

  Nx3 supposed antipode        Goal configuration
-------------------------   ------------------------
     A     B     C   slot        A     B     C  slot
-------------------------   ------------------------
     0     0     N      0      N-1     0     0     1
     z   N-z     0      0        0     N     0     0
 N-1-z     z     0      1        0     0     N     0
-------------------------   ------------------------

Using the same idea, the following lower bounds can be obtained in general w × h case. h is the order of WD matrix.

"All-flipped" w x h WD puzzle antipode
Vertical pattern          Vertical matrix
----------------  -----------------------
     ZZZZ...ZZZZ    0   0   0 ...   0   w
     YYYY...YYYY    0   0   0 ...   w   0
         ...      ... ... ... ... ... ...
     BBBB...BBBB    0   w   0 ...   0   0
      AAA...AAAA  w-1   0   0 ...   0   0
----------------  -----------------------

Even case: h = 2k
MD = 2w(1+3+5+...+(2k-1))-(2k-1) = 0.5 w h2 - h + 1

Odd case: h = 2k+1
MD = 2w(2+4+6+...+2k)-2k = 0.5 w h2 - h + 1 - 0.5 w

Manhattan lower bound for the w × h WD puzzle
h234567891011
MD(h) 2w - 1 4w - 2 8w - 3 12w - 4 18w - 5 24w - 6 32w - 7 40w - 8 50w - 9 60w - 10
» login or register to post comments

Contingency tables

Submitted by stannic on Sun, 01/15/2012 - 17:41.

It turns out that for given W × H puzzle, WD matrices are contingency tables. A contingency table is a non-negative integer matrix with given row and column sums.

     WD     Contingency
   matrix      table
[0] 3 1 0   3 1 0 0 = 4
[1] 0 2 2   0 2 2 0 = 4
[2] 0 1 2   0 1 2 1 = 4
    A B C   = = = =
            3 4 4 1

Additional column is due to variable slot. In general, for W × H puzzle, vertical WD matrices correspond to contingency tables of width H + 1 and height H, with row sums (W, W, W, ..., W) and column sums (W - 1, W, W, ..., W, W, 1).

I am not very familiar with contingency tables but maybe they can help in counting or indexing WD patterns?

Update: counting the number of contingency tables with m rows and n columns is #P-complete, even when m or n (but not both) is 2 (Martin Dyer, Ravi Kannan, and John Mount. 1997. Sampling contingency tables)

» login or register to post comments