Fifteen puzzle solvability, Numworks Python
|
04-25-2020, 04:19 PM
(This post was last modified: 04-26-2020 11:55 AM by Albert Chan.)
Post: #17
|
|||
|
|||
RE: Fifteen puzzle solvability, Numworks Python
Hi Don,
FYI, your original algorithm is also counting swaps (bubble sort) Again, there is no actual sorting, only swaps counting. puzzle = [11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5] Above case would swap 11⇄3, 11⇄8 11⇄1, 11⇄6, 11⇄10, 11⇄7, 11⇄2, 11⇄4, 11⇄9, 11⇄5, like this: Removed hole: [11,3,8,1,6,15,10,7,14,2,13,4,12,9,5] 10 bubbles => [3,8,1,6,10,15,7,2,14,4,13,9,12,5,11] 2 bubbles => [1,8,2,6,10,15,7,3,14,4,13,9,12,5,11] 6 bubbles => [1,2,6,7,10,15,3,4,14,5,13,9,12,8,11] 3 bubbles => [1,2,3,7,10,15,4,5,14,6,13,9,12,8,11] ... total swaps = 10 + 2 + 6 + 0 + 3 + 9 + 5 + 3 + 6 + 0 + 4 + 0 + 2 + 1 + 0 = 51 → row + swaps = 1 + 51 = 52 = even, thus solvable. Switching to selection sort, and let the code do the logic, solvable(a, n) work for any nxn board Code: def solvable(a, n): # assumed sorted(a) == range(n*n) >>> solvable([11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5], n=4) True >>> solvable([1,8,2,0,4,3,7,6,5], n=3) True |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)