I hadn't read that node before, but from the description, it looks like the same puzzle as mine.  I saw that tye provided a solution, but I didn't look too closely as I want the fun of solving it for myself.

Ironically, I started the other way around -- I created a gui that would let you play it, and have only now started working on the "auto-solver" mechanism.

I didn't know at first even what the name of the puzzle was, but after working on getting the gui running, I've since found descriptions of it (and related puzzles) on the Internet.  This particular puzzle has several names -- in French it's "L'ane Rouge" ("Red Donkey") -- it's also called Klotski ("wooden blocks" in Polish).  A short while later a friend gave me a book about Perl written in Japanese as a birthday present, which coincidentally discusses the very same puzzle.  The Japanese version is called "hakoiri musume" ("Daughter in the box"), and uses Chinese characters for the pieces.

I'm still working on solving it (both by hand, and by developing a recursive algorithm), and I'm resisting the temptation to peek at any solutions until then.  I'm also thinking to expand the puzzle to incorporate other rules (such as "Rush Hour", which is very similar in nature).  Once I'm satisfied with it, I'll post it at Perlmonks.