It's Not You, It's the Puzzle

By Ivars Peterson

Muse, March 2003, p. 21.

Have you ever been stuck in a waiting room with nothing but your boredom and a Rush Hour puzzle? You know, the plastic tray of colorful cars and trucks that are stuck in a traffic jam. The goal is to clear a path for a car to the only exit on the grid. Chances are you tried the puzzle. Chances are so did the person before you. And the person after you. Rush Hour looks easy, but it is hard. We're not just saying that because we couldn't solve it. We have mathematical proof.

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.

Puzzle Archive

Submit your own puzzle
E-mail your puzzle to puzzles@snkids.com

Other interesting stuff
GameZone
MatheMUSEments
Puzzle team