The 15 puzzle is a natural example of a groupoid, indeed a groupoid action!
oh!
The natural invariant is:
"sign of permutation (reading l-r, top-bottom)
*times* (-1)^(row num of blank)"
invariant under side-side movements, (no changes)
and invariant under up/down moves,
b/c moving up/down is a 4-cycle on the numbers!!!!!
[so for 3x3, "sign" works]
(can make formula general: "row num*(# cols-1)")
(-1^{r(c-1)})
fix Wikipedia page:
formally, there's an action of a groupoid on it
(it's a groupoid, not a group, b/c can't compose all maps)
http://en.wikipedia.org/wiki/Fifteen_puzzle#Solution
http://en.wikipedia.org/wiki/Even_and_odd_permutations
Link also to references at:
http://mathworld.wolfram.com/15Puzzle.html
[Cyclic, theta,
and rest are "is it bipartite or not?"]
A Modern Treatment of the 15 Puzzle
(includes literature survey, but incorrect info about Sam Loyd)
Aaron F. Archer
The American Mathematical Monthly, Vol. 106, No. 9. (Nov., 1999), pp. 793-799.
...on JSTOR (give link)
http://links.jstor.org/sici?sici=0002-9890(199911)106%3A9%3C793%3AAMTOT1%3E2.0.CO%3B2-6
also at:
http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/15-puzzle.pdf
http://www.research.att.com/~aarcher/Research/index.html