Solving Rush Hour, the Puzzle

• Published in 2018
• Added on 2023-03-22

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

• https://www.michaelfogleman.com/rush/

Other information

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-12-07},
	urls = {https://www.michaelfogleman.com/rush/},
	collections = {basically-computer-science,combinatorics,puzzles},
	url = {https://www.michaelfogleman.com/rush/},
	year = 2018,
	urldate = {2023-03-22}
}