| |
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!
|
