History

The 15 puzzle is a sliding square puzzle invented by Noyes Chapman prior to 1880. (Although Sam Loyd claimed to be the inventor of the puzzle for a period of 20 years, 1891-1911 - an accomplishment in itself - he did not invent or had anything to do with the popularity of the puzzle.)

The puzzle contains 15 numbered squares from 1 to 15 and are placed in a 4×4 box, leaving one position of the 16 places empty.

The goal of the puzzle is to reposition the squares from a random initial arrangement by sliding the pieces one at a time to a desired 'final' arrangement.

Random Arrangement:

The random arrangement of the 15-puzzle has an interesting property. If all rows/columns summed parity is odd, the puzzle is not solvable. So as long as the empty cell is situated in a corner and the summed row/column parity is even, the puzzle is solvable.

The probability to randomly place the pieces for a solvable/unsolvable puzzle in the 4×4 slots - distributes to an even 50-50%

Parity of permutations:

One way to look at the problem and the solvability of a random order and a given set of rules, is to investigate the parity of permutations and the outcome of the unfold. By drawing lines to each home position for every piece reveals alternative paths for moving the pieces to the right postitions. For example, if swapping is required as a rule, number 6 could first swap with number 2 and then later with number 8 to reach home position. In the case below 1, 5, 7 and 2, 6, 8 are two seperate dependant groups.

The parity of permutations is used with the 15 puzzle as a mean to understand if a configuration is solvable or not by counting the number of 'swaps' in relation to the size n x m of the puzzle and the position of the hole. Since the parity is being used to define the solvability, only one difference/error should be spotted at an attempt to solve an illegal configuration of the puzzle. If not, the parity explanation does not hold, since the parity only has two states (odd or even). There are other ways to interpret parity, for example string intersections being overlapping or not, magnetic fields etc…Maximum dissorder:

The maximum number of moves required to solve the n x n generalization of the 15 puzzle for n=1, 2, … are 0, 6, 31, 80, … (Sloane's A087725).

var count = 1while(count<10){ var n = count; var numb = 0; numb += (2*count-2)*(2*count-2); n -= 2; while(n>3){ numb += (2*count-2)*(2*count-2)-2; n -= 2; } numb *=2; if(numb>1){ numb -=2; } trace(count + " : " + numb); count++;}

Swap distance sequence

-an estimate of the maximum number of moves required.

The 2D mirrored pattern of squared sized puzzle patterns would give the (floored step) swap distance sequence 0, 6, 30, 70, 126, 394, 570, 1166, 1526 (…an incomplete formula… 2((while n>=3, sum(2n-2)^2, foreach n-2 iterativ_sum -2;)))-2, so the actual length of steps and finding the shortest solution (and the NP-hard part of finding the hardest possible setup) therefore probably closely follow the complete and x-y mirrored 'home position' distance. It is likely that the furtherest distance is close to the opposite and reversed 'home position' pattern, however, it is not likely that the actual and maximum disorder pattern is the mirrored pattern, since a mirror is not a complete breakdown, but merely a reflection of the pattern.

Since I haven't found more than 4 values of the real maximum values from Sloane's, there is little to confirm any relationship between the actual number of moves - and the formula I made below, although I'm fairly certain it should be within the same neighborhood at least. We will see…
0, 6, 30, 70, 126, 394, 570, 1166, 1526 (swap distance sequence below)
0, 6, 31, 80, … (Sloane's A087725).

var count = 1
var theString ="";
while(count<10){
var n = count;
var numb = 0;
numb += (2*n-2)*(2*n-2);
n -= 2;
while(n>3){
numb += (2*n-2)*(2*n-2)-2;
n -= 2;
}
numb *=2;
if(numb>1){
numb -=2;
}
theString += numb + " ";
count++;
}
trace(theString);

Maximus distance

-a conceptual description to estimate the maximum distance pattern for the 15-puzzle.

The maximum distance for an ordered one dimensional setup can be found in a 2 dimensional system interpreting maximum distance between ordered coordinates on a circle - projected onto a line. At least one of the projections describes the maximum order distance.

One interesting property of the largest distance found in the 2D 'projection sequences', for example 3, 5, 1, 2, 6, 4, is that they are organized with half of the sequence with odd numbers, and the other half in even numbers.

For a two dimensional setting like the 15-puzzle, we would use a 3 dimensional body to interpret the maximum distance and then project that onto a 2 dimensional surface. However, there seems to be no easy way to configure maximum distance of coordinates on a sphere, or at least I cannot personally do that without CAD aid.(and I haven't done that yet), so there are no tests yet if this concept is valid.

sequence => steps to count the whole sequence

3, 5, 1, 2, 6, 4 => 16

3, 1, 5, 6, 2, 4 => 16

1, 6, 3, 4, 5, 2 => 13

6, 1, 4, 3, 2, 5 => 13

3, 2, 1, 6, 5, 4 => 9

6, 5, 4 ,3 ,2 ,1 => 5

1, 2, 3, 4, 5, 6 => 5

Links:

http://en.wikipedia.org/wiki/Fifteen_puzzle

http://kevingong.com/Math/SixteenPuzzle.html