I've built a 15 puzzle in JS but my random puzzle generation is creating instances of an unsolvable puzzle. This could be because I'm not a Computer Science head, but I'm not sure how to work out things like calculate the number of inversions in a permutation in code. I'm wondering how to write my code so that I can test that any given start state of my puzzle is solvable. I've seen other 15 puzzles in published apps out there that are unsolvable, so it seems I'm not the only one out there with my problem.

I've seen this post, but it stops at the CS level and I'm looking for a code implementation that would help me understand this a little better: 15 Puzzle Heuristic

I'm using JS, but any help and explanation from whichever language would be a great help.

I've built a 15 puzzle in JS but my random puzzle generation is creating instances of an unsolvable puzzle. This could be because I'm not a Computer Science head, but I'm not sure how to work out things like calculate the number of inversions in a permutation in code. I'm wondering how to write my code so that I can test that any given start state of my puzzle is solvable. I've seen other 15 puzzles in published apps out there that are unsolvable, so it seems I'm not the only one out there with my problem.

I've seen this post, but it stops at the CS level and I'm looking for a code implementation that would help me understand this a little better: 15 Puzzle Heuristic

I'm using JS, but any help and explanation from whichever language would be a great help.

• javascript
• algorithm
• heuristics

• 4 My approach would be to start every game with the original 15-digit sequence and make my scrambler the random aspect permutations of "Scrambling" (move block 5 up, block 10 right, block 6 down, etc.) also randomizing how many mis-movements are involved as well [given a range]. – Brad Christie Commented Oct 9, 2011 at 3:54
• 2 @Brad You should post that as an answer. – John Kugelman Commented Oct 9, 2011 at 4:19

2 Answers 2

The algorithm for solvability is based on the parity of inversion and explained in 15 Puzzle - Wolfram Math World It should not be too difficult to convert into code. IIRC swapping two adjacent squares on a non-solvable starting point makes it solvable, but you will need to confirm that.

Note that this is an exact algorithm determining whether or not a puzzle can be solved, not a heuristic for guiding the sequence of steps in the solution.

What I was eluding to in a ment, but wasn't sure if it the right approach:

1. Start out with the "correct" 15-digit sequence/board
2. Generate a random number of "miss-placings" you can apply to the board
3. Generate N list of valid miss-placings based off the random number you generated
4. You should now have a valid game.

Since you're starting with a valid board, then applying a set of forced mis-directions, you'll always end up a pletely legitimate start game.