Sokoban - The Challenge II
15-Puzzle
Rubik's Cube
Sokoban
Branching Factor
2-4
18
0-144
Solution Length
53 (1-80)
18 (1-20)
260 (97-674)
Search-Space Size
10**13
10**19
10**98
A*-Bound Complexity
O(n) -> O(1)
O(n) -> O(1)
O(n**3) -> O(n**2)
Underlying Graph
undirected
undirected
directed
The search-space size alone makes Sokoban hard, but...
The lower bound is expensive to compute, and...
Irreversible moves lead to deadlocks!
GPW'99, October 16, 1999.
Pushing the Limits: New Developments in Single-Agent Search