Michael Fogleman


Rush Hour June 2018

173 Go C++ Game AI

I solved the Rush Hour puzzle game and created a database of every interesting starting position.

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.

I did more than write a simple puzzle solver. I ended up computing every possible puzzle and built a complete database of every "interesting" starting position. It was quite challenging (and exciting!) so I wrote a whole article about it. Check it out!