First, go to Quzzle to try your hand at solving the problem. The goal of this version is to move the largest piece from its original upper-lefthand corner to the upper-righthand corner. Can you do it? In 84 or less moves?
The Quzzle was invented by Jim Lewis, using a computer to help ensure that it is "the most difficult simple sliding block puzzle in the world." Basically his special program Computer Assisted Puzzle Analyzer generated and tested the "search space" of puzzles using different sized blocks (e.g. 1x1, 1x2, 2x2) in different sized frames.
As part of his tests of potential puzzles, Lewis discovered that 3x4 and 4x4 frames turned out to be too easy, while those bigger than 4x5 became quite difficult. I know...you probably checked that the Quzzle you tested was exactly 4x5, and thus is in the category between "too easy" and "quite difficult."
In the tests for each configuration of sizes of pieces and frames, the program calculated in a "tree sequence" format all of the possible first moves from the original configuration. Then, given a first move, the program tested all of the second possible moves, etc. This process continued until all of the possible solution paths had been both documented and exhausted.
One particular puzzle version (the one you played with) seemed unusual, especially since his program first reported that it was insoluable. But, he later was able to show that it was soluable (comforting right!).
You can buy a commerical hand-held version for about $20 from Quirkle.com.
Finally, as an interesting visual, you might peek at a color-coded picture of the solution space.