CODEWITHSUNDEEP
javascriptalgorithmheuristics
Lounge9
Lounge9

Reputation: 9

how to programatically create a valid 15 puzzle in code

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.

Upvotes: 0

Views: 5172

Answers (2)

Pete Kirkham
Pete Kirkham

Reputation: 49331

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.

Upvotes: 3

Brad Christie
Brad Christie

Reputation: 101614

What I was eluding to in a comment, 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 completely legitimate start game.

Upvotes: 2

Related Questions