# 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