Interesting Esoterica

Solving Rush Hour, the Puzzle

Article by Michael Fogleman
  • Published in 2018
  • Added on
Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. I played a clone of this game on my first iPhone several years ago. Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles. After writing a solver, I wrote a puzzle generator that would create more starting positions for us to try (the game comes with 40 levels printed on playing cards). The generator used simulated annealing to try to maximize the number of moves required to solve the puzzle. Unsatisfied with the results, I then decided to try generating all possible puzzles. Ultimately I ended up with a complete database of every "interesting" starting position. It was quite challenging (and exciting!) and that's what I want to talk about in this article. My code is open source with a permissive license and the resulting database is available for download.

Links

Other information

key
SolvingRushHour
type
article
date_added
2023-03-22
date_published
2018-03-14

BibTeX entry

@article{SolvingRushHour,
	key = {SolvingRushHour},
	type = {article},
	title = {Solving Rush Hour, the Puzzle},
	author = {Michael Fogleman},
	abstract = {

Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996.

I played a clone of this game on my first iPhone several years ago. Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles.

After writing a solver, I wrote a puzzle generator that would create more starting positions for us to try (the game comes with 40 levels printed on playing cards). The generator used simulated annealing to try to maximize the number of moves required to solve the puzzle.

Unsatisfied with the results, I then decided to try generating all possible puzzles. Ultimately I ended up with a complete database of every "interesting" starting position. It was quite challenging (and exciting!) and that's what I want to talk about in this article. My code is open source with a permissive license and the resulting database is available for download.},
	comment = {},
	date_added = {2023-03-22},
	date_published = {2018-03-14},
	urls = {https://www.michaelfogleman.com/rush/},
	collections = {basically-computer-science,combinatorics,puzzles},
	url = {https://www.michaelfogleman.com/rush/},
	year = 2018,
	urldate = {2023-03-22}
}