15 Puzzle

Author

Eric W. Weisstein
November 20, 2003

This notebook downloaded from http://mathworld.wolfram.com/notebooks/RecreationalMath/15Puzzle.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/15Puzzle.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

This could be made more efficient.  At the moment, it's O((n^2)), but should be O(n)

InversionCounts[l_List?VectorQ]:=Count[Thread[First[#]>Rest[#]],True]&/@NestList[Rest,l,Length[l]-1]

(*
InversionSum[l_List?VectorQ]:=Plus@@InversionCounts[l]
*)

InversionSum[l_List?VectorQ]:=Inversions[l]
PossibleQ[l_List?VectorQ]:=(Signature[l]==1)

InversionSum[m_List?MatrixQ]:=InversionSum[Flatten[m]]

Examples

Show[MagicSquarePlot[Partition[Append[r=Range[15],"\[Null]"],4]]]

{InversionSum[r],PossibleQ[r]}

Show[MagicSquarePlot[Partition[Append[r=Join[{2,1},Range[3,15]],"\[Null]"],4]]]

{InversionSum[r],PossibleQ[r]}

Show[MagicSquarePlot[Partition[Append[r={1,2,3,4,5,6,7,8,9,10,11,12,13,15,14},"\[Null]"],4]]]

{InversionSum[r],PossibleQ[r]}

<<DiscreteMath`Combinatorica`

r=RandomPermutation[15]

Show[MagicSquarePlot[Partition[Append[r,"\[Null]"],4],TextStyle->{FontFamily->"Times"}]]

InversionCounts[r]

{InversionSum[r],PossibleQ[r]}