I have been trying to solve
15-Puzzles by using the
A* (A-star) search algorithm. The A* search algorithm use not only the cost to reach the node (usually denoted g(x)) but also an estimated cost (usually denoted h(x)) to get from the node the goal node to determine the order in which the search visits nodes.
The
heuristic function h(x) plays a vital role here, with a good heuristic function fewer nodes will be generated and ultimately leads to smaller costs both in time and space.
You can easily solve the
8-Puzzle with the
Manhattan distance (MD) as your h(x) function but for the 15-Puzzle MD as your h(x) function is sadly not good enough.
Below are some numbers I got when I run my A* algorithm with a h(x) function consisting of MD and
Linear Conflict (LC). LC improves the heuristic function a little but the search is still painfully slow and not viable for any real usage if the solution length are to "deep".
MD + HVC
solution length nodes generated
19 497
26 2696
34 122941
42 501595
46 979602
There is
better heuristic functions out there but then it is not "simple" anymore and will take some time and brain power to implement. You may consider one of these:
The Manhattan Pair Distance Heuristic by Bernard Bauer, use pattern databases or
Walking Distance by Ken'ichiro Takahashi.
UPDATE 2012-03-07
I did improve the heuristic function by also taking in account the vertical linear conflict (VLC).
Here are the new numbers.
MD + HVC + VLC
solution length nodes generated
19 342
26 1375
34 97894
42 104267
46 508080
