Different optimization methods for solving the rush hour puzzle

Abstract

The rush hour puzzle is a widely recognized benchmark problem used to evaluate search algorithms in artificial intelligence. It presents a constrained, grid-based planning task that is known to be PSPACE-complete and serves as a useful model for studying computational complexity, heuristic search, and constraint satisfaction. This paper compares three optimization methods: Breadth-First Search (BFS), A*, and Greedy Best-First Search (GBFS) in their ability to solve rush hour puzzles efficiently. A Python-based prototype was developed to perform 100 benchmark runs on 6 × 6 and 9 × 9 grid configurations at hard difficulty. The analysis focuses on the solver success rate, timeouts, and normalized efficiency metrics, including time per step and nodes per step. The results show that GBFS consistently achieves the fastest performance with the highest solve rate, while $\mathbf{A}^{*}$ offers a balance between solution quality and runtime. BFS, although complete, struggles with scalability. These findings provide practical insights into the trade-offs between completeness, optimality, and computational efficiency in pathfinding under constraints.