For behind the scenes pictures, stories and special contests, follow us on Facebook!

Quzzle, Hardcore Computer Science

By Bruce Eaton

You are probably thinking I am insane to call the Quzzle, a sliding block puzzle, computer science or a gadget… but hear me out. Jim Lewis, an inventor from New Jersey, set out to create ?the world’s hardest simple sliding-block puzzle? and he did it with custom software and a high-speed computer.

Programming and number crunching, Lewis devised the Computer Assisted Puzzle Analyzer (CAPA) software in Haskell

a so called “Functional” programming language. He went through numerous revisions of the program to allow computation of a solution in an acceptable amount of time. The first version would have taken years of computer time to complete. Subsequent versions progressively reduced the needed computer time by making the program more and more efficient.

He then used the program to figure out which starting position for a 4 by 5 sliding block puzzle would have the largest solution tree. The result is a 9 piece puzzle that is deemed “nearly unsolvable” and comes with internet support for finding the answer.

The computer science behind these types of problems are called PSPACE-complete. Essentially it is very complicated polynomial so hard a math type that my brain just gave up while trying to write about it. So yes you might be able to solve a Rubiks Cube in under a minute behind your back but can you solve a Quzzle… looking at it… for a month… with internet help?

[Quzzle] VIA [Quirkle]