(2018) How I created a database of all interesting Rush Hour configurations
12 days ago
- #puzzle-solving
- #bitboards
- #combinatorial-explosion
- Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s.
- The author created a solver and puzzle generator for Rush Hour, using simulated annealing to maximize difficulty.
- A complete database of 'interesting' Rush Hour configurations was generated, with rules to filter out trivial puzzles.
- Bitboards were used for efficient representation and manipulation of puzzle states.
- The enumeration of states was optimized using lexicographical ordering to avoid redundant processing.
- Cluster analysis was performed to identify solvable, unsolved, and minimal puzzles.
- The hardest 6x6 puzzles were identified, with some requiring up to 60 moves to solve.
- The database includes 2,577,412 puzzles, covering 9,698,093,879 reachable states.
- Utilities were developed for rendering, solving, and analyzing puzzles.
- An online version of the game was created using p5.js, allowing users to play random puzzles from the database.