Japanese puzzle designer Nob Yoshigahara invented Rush Hour in the late 1970s. For the U.S. edition of the game, Nob and his team developed several sets of puzzles that offer challenges rated from beginner to expert. For some initial arrangements of blocks, it takes only a few moves to free the designated car. In the most challenging cases, it can take as many as 50 moves to free it.
Mathematicians and computer scientists are interested in sliding-block puzzles like Rush Hour because they resemble real-world motion-planning problems. In some parking lots, for example, attendants cram cars together as tightly as possible. When a patron shows up to retrieve his or her car, the attendant must figure out which other vehicles to move to get the required one out as quickly as possible. (In Japan, Rush Hour is called Tokyo Parking Lot.) Engineers face a similar problem when they have to program a robot to shift bulky crates in a crowded obstacle-strewn maze.
By having computers solve the puzzle, researchers showed Rush Hour really is tough. It takes computers a surprisingly long time to find the best possible solution to a Rush Hour setup. And the more vehicles and the larger the grid, the longer it takes. Analysis puts Rush Hour on the same level of difficulty as such demanding games as Othello, although below that of Chess or Go.
So don't feel bad about being stumped. And consider this: Your parents had it worse. They had to wrestle with the fiendish "14-15" puzzle. You know the one. It consists of 15 tiles numbered from 1 to 15 in a square tray large enough to hold 16 tiles. Tiles 14 and 15 start out switched, and the player has to restore all the tiles to numerical order. No one could solve it, and mathematicians soon proved it could not be solved! Doubtless many trusting young minds were warped for life by the experience of trying.
