Robust solution checking

[JanDW]

• [ ] Try Xerxes' formula
• [ ] Check Inversion count
  • [ ] Create an object with output from getInversionCount() and log with console.table

---

Resources

Text https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html http://kevingong.com/Math/SixteenPuzzle.html https://en.wikipedia.org/wiki/15_puzzle

Video Numberphile dude part 1 Numberphile dude part 2 Linear Algebra 108 puzzle of fifteen

[JanDW]

Commits

• 356e350
• 892eea5
• e92683a

---

Formula to rule them all from @XerxesZorgon:

I think there might be a one size fits all formula for testing solvability. For any $ n \times n $ puzzle with $i$ inversions and the blank on the $r^{th}$ row from the top, the puzzle is solvable if

$$ \mod( i + (1 - \mod(r,2)) \times r, 2) = 0. $$

For any even $n$, if $r$ is odd counting from the bottom, then $r$ will be even counting from the top, and will be solvable if

• there are an even number of inversions and the blank is on an even row from the top, or
• there are an odd number of inversions and the blank is on an odd row from the top.

In either case, the sum of the inversions and the row number will be an even number, so $\mod(i + r,2) = 0$.

For $n$ odd, you don't have to worry about the blank. What the formula above does is to find out if $r$ is even or odd, and if it's odd then $1 - \mod(r,2) = 0$ so you're left with just $\mod(i,2)$, but if $r$ is even then the second term gets multiplied by 1 and you sum the inversions and the row.

[JanDW]

Oh... rats. This is rather comical/deeply tragical. Based on emptyAreaRow, gridSize, and inversionCount, the puzzle should be solvable. Except, it's not of course. So let's count the inversions for this array [7, 8, 11, 1, 2, 12, 10, 3, 9, 5, 16, 15, 4, 6, 14, 13]

Index	Value	# of inversions
0	7	6
1	8	6
2	11	8
3	1	0
4	2	0
5	12	6
6	10	5
7	3	0
8	9	3
9	5	1
10	16	5
11	15	4
12	4	0
13	6	0
14	14	1
15	13	0
	Total	48

I guess I need to drop [10] 16 → 5 which would lead to 44 which is even and thus not solvable. I don't remember if I take out the 16 in the code or what's happening there.

Here's another one: haven't attempted to solve it but number of inversions is off:

array = [1, 6, 2, 8, 3, 4, 5, 9, 7, 14, 11, 12, 13, 10, 15, 16];

Index	Value	# of inversions
0	1	0
1	6	5
2	2	0
3	8	5
4	3	0
5	4	0
6	5	0
7	9	2
8	7	0
9	14	5
10	11	1
11	12	1
12	13	1
13	10	0
14	15	0
15	16	0
	Total	20

[JanDW]

Cool beans. There's a wikipedia article on this puzzle too: https://en.wikipedia.org/wiki/15_puzzle

[JanDW]

Counts above are borked, but pretty sure count is accurate now (tried another inversionCount algorithm fron github and got matching results)

Still, no reason to get cheerful: 🤨

[XerxesZorgon]

My inversion count is [6 6 8 0 0 6 5 0 3 1 0 4 0 0 1 0], and it looks like the first difference is for 11 (in the 3rd position). I think it should be 8 because 1,2,10,3,9,5,4,6 all appear in the list after 11 and are less than 11. I get a sum of 40 for the total inversions.

On Sat, Aug 8, 2020 at 10:48 PM Jan De Wilde notifications@github.com wrote:

Counts above are borked, but pretty sure count is accurate now (tried another inversionCount algorithm fron github and got matching results)

Still, no reason to get cheerful: 🤨

[image: Screen Shot 2020-08-08 at 10 46 06 PM] https://user-images.githubusercontent.com/191317/89723816-2a53a480-d9c9-11ea-826b-0816fa41dcf8.png

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/JanDW/slide-number-puzzle/issues/5#issuecomment-670998066, or unsubscribe https://github.com/notifications/unsubscribe-auth/AC3KQPMIZRTXELMCFVBFIYDR7YE7ZANCNFSM4OQH3X4A .

[JanDW]