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*

Discipulus, The very fact that you write code like that, shows that you have earned true monk-dom.

---

I'm not really a human, but I play one on earth. ..... an animated JAPH

Only an idiot would want to do matrix equations by hand!! :-)

Please, a little respect... for I am perldigious, King of the Idiots. :-)

Just another Perl hooker - Yep, I've definitely seen more than my share of d*cks in the world, that's for sure.

Back in high school, I was very good at doing matrix math "by hand".

Of course, once I wasn't (explicitly¹) required to do it by hand, I didn't.

---

¹The instructor didn't specify, I didn't ask. But, I did include a note that I was also taking a 400-level CS class in algorithms and that he was welcome to see my source code.

In my case, I was doing this symbolically trying to derive equations in terms of variable resistance values to use in SPICE simulations. With Mathcad or some other symbolic capable mathematics package that also includes matrix math that would be relatively easy, but the equations were simple enough that I just set about doing it by hand figuring it would be faster than figuring out how to get some unfamiliar tool to do it (I may have been wrong about that). I ended up just using old fashioned linear system of equations substitution, and then later realized the entire thing could be solved a lot more simply based on the symmetry of the circuit.

Like I said, dumber every year I get further away from college. :-)

Just another Perl hooker - But the purist monks keep telling me I should do it for love, not money.