Right! I did that solution in response to a Byte magazine contest years ago. It ran in 20 minutes in Basic on an HP2000.
The tricky part is permuting the array. I used a recursive swap routine, swapping to the right and testing if the array were valid to the left of i then recursing i+1. If it fails you don't have to recurse, you can pop, trimming the search tree drastically. There were 8 or 9 solutions if I remember right, less if you eliminate rotations and mirrors.
{edit: 12 solutions}
