This reminds me a little of the old 15 number slide puzzles that were popular back in the 50's and 60's.
I don't remember meeting anyone who could solve it, but it was a solvable puzzle.
After some study with paper and pencil on this, I would opt for the brute force program, also.
I doubt that taking the time to learn the sequences you'd need to know for this, would really be worth the time you'd spend.
I'm generally fond of depth first searches, but with no ability to "score" anything for a "cut out", I'm thinking a breadth first search would be a much better solution.
You've had more time with this now, what do you think?
