Walking Distance
02 / 19 / 2012
Intro
Walking Distance is a heuristic for solving Fifteen Puzzle with IDA* invented by Ken'ichiro Takahashi from Japan. This heuristic allows to determine good lower bound of the optimal solution length. In 4 × 4 Fifteen puzzle, maximum value that can give this heuristic is 70 moves. Compare this to 60 moves that can give wellknown Manhattan Distance.
I have implemented the same idea to the 5 × 5 TwentyFour puzzle and got lower bound of 140 single tile moves for the following configuration (goal configuration is classic, i.e. slotlast):
 24  23  22  21 
20  19  18  17  16 
15  14  13  12  11 
10  9  8  7  6 
5  4  3  2  1 
Tomas Rokicki, a programmer from Palo Alto, California, wrote optimal solver that uses WD heuristic. After about 10 days, his program has finished search at depth 150 but did not find solution. Thus, current lower bound on the 24puzzle in STM is 152. More about this you can read in [2].
There is solution in 156 single tile moves for the configuration above. This solution goes through intermediate configuration and is not proved to be optimal yet.
This page contains English translation of the original description of the Walking Distance.
This page contains my description of the 4 × 4 WD.
References / See also
 Ken'ichiro Takahashi's Computer & Puzzle page
 Domain of the Cube Forum
 Herbert Kociemba's Fifteen Puzzle Optimal Solver
– working Fifteen Puzzle optimal solver with heuristics MD, WD, PDB
