## Hardest Simple Sliding-Block Puzzle

You can try this puzzle online.

From *The Economist*, December 4-10, 2004

Section: Science and technology Puzzles A hard, simple problem Has an inventor found the hardest possible simple sliding-block puzzle? SLIDING-BLOCK puzzles look easy, but they can be tricky to solve. The best known is the "15 Puzzle", which became hugely popular in the late 1870s. This involves square tiles labelled with the numbers 1 to 15, which must be arranged in the correct order inside a four-by-four frame. Another popular one, called "Dad's Puzzle", involves moving a large square tile from one corner to another, by rearranging other, smaller tiles around it--akin to moving a piano across a cluttered room. The best such puzzles are easy to explain, yet difficult to solve. Historically, they have been devised by trial and error. But earlier this year, Jim Lewis, an inventor based in Midland Park, New Jersey, set out to find the hardest possible "simple" puzzle, using a computer-based search. Mr Lewis's definition of "simple" was that the puzzle consist of up to three sorts of tile--one unit by one unit, one-by-two and two-by-two--and that the objective, as with Dad's Puzzle, should be to move one of the large tiles from one corner to another. He found that puzzles constrained within three-by-four and four-by-four frames were too easy to solve, but that anything larger than a four-by-five frame made the puzzle too complex. He then wrote a computer program to search through all possible puzzles within a four-by-five frame. 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. Mr Lewis claims that "Quzzle", as he dubs his invention, is "the world's hardest simple sliding-block puzzle". Within the terms of his particular definition of "simple", he would seem to have succeeded.