There’s an interesting article on Science News Online about puzzles and the mathematics behind solving them. The article looks specifically at two puzzles that are available from ThinkFun.
The first is TipOver, also sometimes known as crate puzzles. There’s a Java implemention that’s ready to play at PuzzleBeast. In the puzzle, there are stacks of crates of varying heights positioned around the room. You begin the puzzle on one stack of crates and the goal is to move to a crate that is marked as the goal. You may move from crate to crate, but you can’t touch the floor or jump over empty space. You may also knock over a stack of crates if there’s room. The article gets pretty serious into the math. Turns out the problem in NP-complete. You should check out the article if you want to know more.
The second puzzle is River Crossing, also sometimes known as plank puzzles. These puzzles were designed by Andrea Gilbert at clickmazes. In this puzzle, your goal is to cross a river gong from tree stump to tree stump using a limitted set of planks of varying length (again no jumping or swimming through the river.) This puzzle is PSPACE-complete.
Without getting too far into it here, the most interesting thing about NP-complete and PSPACE-complete problems is that there’s no known efficient algorithm for solving them. If you can one, you may win $1 million.
Tags: math,np-complete,pspace-complete,puzzles
