Oh do not overstimate me, nor my code: I have no idea about the minimum number of moves nor how to solve the puzzle programatically.

The possible/impossible solution is another matter and is a simple one: see the link to the mathworld site in the reference or run with the --verbose switch to see how to compute it.

Infact it is calculated counting, for every tile, how many are lesser of the current one, as if they lay on a single row and adding all these number: if the result is odd the game is impossible.

You can read on wikipedia:

> .. offering a $1,000 prize for anyone who could provide a solution for achieving a particular combination specified by Loyd, namely reversing the 14 and 15. This was impossible, as had been shown over a decade earlier by Johnson & Story (1879), as it required a transformation from an even to an odd combination.

Infact I simply do: $perm += grep {$_ < $appear[$num]} @appear[$num+1..$#appear]; and later on if ($permutation % 2){ print "Impossible game with odd permutations!"

Running with --verbose shows it clearly:

---------------------------------------------------------
Appearence of the board:
[14 15 12 2 10 6 1 7 13 5 9 11 4 3 8 X]
---------------------------------------------------------
current followers                      less than current
---------------------------------------------------------
[14]    15 12 2 10 6 1 7 13 5 9 11 4 3 8           13 +
[15]    12 2 10 6 1 7 13 5 9 11 4 3 8              13 +
[12]    2 10 6 1 7 13 5 9 11 4 3 8                 11 +
[2]     10 6 1 7 13 5 9 11 4 3 8                   1 +
[10]    6 1 7 13 5 9 11 4 3 8                      8 +
[6]     1 7 13 5 9 11 4 3 8                        4 +
[1]     7 13 5 9 11 4 3 8                          0 +
[7]     13 5 9 11 4 3 8                            3 +
[13]    5 9 11 4 3 8                               6 +
[5]     9 11 4 3 8                                 2 +
[9]     11 4 3 8                                   3 +
[11]    4 3 8                                      3 +
[4]     3 8                                        1 +
[3]     8                                          0 =
                                                  ----
MEDIUM game with even permutations                 68
[download]

Being 105 the highest value for permutations I just assign solved, easy, medium and hard difficulty level for permutations with values of 0, 1-35, 36-70 and 71-105

The real fun is running the program with --perl switch... ;=)

L*