CODEWITHSUNDEEP
algorithmartificial-intelligence
Mint.K
Mint.K

Reputation: 897

8 puzzle solvability test cases errors

I have a 3 by 3 puzzle. To know whether it's solvable or not, I need to count the number of inversions. If the number of inversions even, then it's solvable. I found a sample code online:

https://gist.github.com/caseyscarborough/6544636

Here he says { 1, 0, 3, 7, 2, 5, 8, 4, 6 } is solvable. But my calculation says otherwise. I have (10,32,72,75,74,76,54,84,86). So the number of inversions for this case is 9, which is not solvable since it's odd.

Another case I've tested with the code is (3,0,7,6,8,2,1,4,5). It gives me (30,31,32,62,61,64,65,76,72,71,74,75,82,81,84,85,21), which is 17 inversions. So it's not solvable, but the code says it is solvable.

Am I making any mistakes? Or are there any mistakes in the code?

Upvotes: 1

Views: 68

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58399

Your method is slightly incorrect. Assuming 0 is the blank square, you should be ignoring it in your inversions count.

Making that change excludes exactly one inversion in both of your examples, so both are wrong.

Upvotes: 1

Related Questions