Is Quzzle the hardest simple sliding-block puzzle?
By Tim Finin on Monday, September 25th, 2006 at 1:00 pm.
On Del.icio.us I noticed an article from the Economist on the World’s hardest simple sliding-block puzzle. As it happens, I’m teaching our AI class this semester and we’re right in the middle of discussion problem solving as search, so it’s very apropos.
The puzzle was invented by Jim Lewis who set out to develop a very hard sliding block puzzle. Using a program (Computer Assisted Puzzle Analyzer) written in Haskell, Lewis generated and evaluated the search spaces of puzzles with different sized blocks (1×1, 1×2, 2×2) in frames of various sizes where the goal is moving the largest block from one corner to another.
He found that puzzles with 3×4 or 4×4 frames turned out to be too easy, those bigger than 4×5 too hard and puzzles with blocks with a dimension larger than two tended to suffer from gridlock.
From the Economist story:
For each candidate puzzle, Mr Lewis’s program calculated all the possible moves from the initial configuration, and then all possible moves from the resulting positions, and so on. In this way, it constructed a “solution tree” for each puzzle. The taller the tree, the more moves are required to get to the solution. The broader the tree, the more dead ends there are along the way.Mr Lewis looked at the output of the program, and one puzzle leapt out: its solution tree was both tall and broad. At first, he found the puzzle insoluble, and assumed there was a bug in his program. But the program did work correctly, and the puzzle is indeed soluble.
You won’t find Quzzle in your local Wal-Mart just yet, but you can buy it online from Jim Lewis’s company Quirkle, which he describes as “dedicated to taking classic toys and gadgets and re-engineering them to the extreme”. You can also try this Quzzle Java Applet developed by Nick Baxter. P. Aylett and C. Prabhakar have also produced a visualization of the Quzzle search space.
Related posts: • AAAI-05 Word Search Puzzle; • The Dark Room; • Human agent swarm attempts Sudoku solution;
UMBC eBiquity Blog
