Different optimization methods for solving the rush hour puzzle
Loading...
Author (Corporation)
Publication date
2026
Type of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Editor (Corporation)
Supervisor
Parent work
2026 8th International Symposium on Computational and Business Intelligence (ISCBI)
Special issue
DOI of the original publication
Link
Related research data
Series
Series number
Volume
Issue / Number
Pages / Duration
333-337
Patent number
Publisher / Publishing institution
IEEE
Place of publication / Event location
Bali
Edition
Version
Programming language
Assignee
Practice partner / Client
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.
Keywords
Subject (DDC)
Event
2026 8th International Symposium on Computational and Business Intelligence (ISCBI)
Exhibition start date
Exhibition end date
Conference start date
06.02.2026
Conference end date
08.02.2026
Date of the last check
ISBN
979-8-3315-5080-6
979-8-3315-5079-0
979-8-3315-5081-3
979-8-3315-5079-0
979-8-3315-5081-3
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
peer-reviewed
Open access category
Closed
Citation
Gafirov, A., Dornberger, R., & Hanne, T. (2026). Different optimization methods for solving the rush hour puzzle. 2026 8th International Symposium on Computational and Business Intelligence (ISCBI), 333–337. https://doi.org/10.1109/iscbi69404.2026.11496271