Thread: N-Puzzle Solvability View Single Post
 Nov 9, 2012, 04:08 PM #1 Jizzler     Join Date: Aug 2007 Location: Geneva, FL, USA Posts: 3,010 (1.43/day) Thanks: 567 Thanked 606 Times in 487 Posts System Specs N-Puzzle Solvability 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  ```