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 well-known Manhattan Distance.

I have implemented the same idea to the 5 × 5 Twenty-Four puzzle and got lower bound of 140 single tile moves for the following configuration (goal configuration is classic, i.e. slot-last):

24232221
2019181716
1514131211
109876
54321

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 24-puzzle 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.

Translation

This page contains English translation of the original description of the Walking Distance.

4 × 4 puzzle

This page contains my description of the 4 × 4 WD.

References / See also

  1. Ken'ichiro Takahashi's Computer & Puzzle page
  2. Domain of the Cube Forum
  3. Herbert Kociemba's Fifteen Puzzle Optimal Solver
    – working Fifteen Puzzle optimal solver with heuristics MD, WD, PDB