With all the talk about n-puzzle, I wanted to start playing around with a PHP implementation. I've gotten a solver in place, but it only solves it some of the time. Want to get my validator looked at to see if I understood the parity calculation correctly. If it looks sound, then I know the problem is later in the code.
- I'm using explanation given
here about how to calculate parity.
- "total" is considered the space square.
- While permutations parity is odd, reshuffle the order until even parity is achieved.
- Loop through the range and for each square, test if value is greater than value of squares further in the sequence. If so, increment the counter.
PHP Code:
$tall = 3;
$wide = 3;
$total = $tall * $wide;
$range = range(1, $total);
do {
shuffle($range);
$permutations = 0;
for ( $i = 0; $i < ($total - 1); ++$i ) {
for ( $j = ($i + 1); $j < $total; ++$j ) {
if ( $range[$i] > $range[$j] ) {
++$permutations;
}
}
}
} while ( $permutations & 1 );
//use validated range for board