Fifteen puzzle solvability, Numworks Python

04082020, 10:41 AM
(This post was last modified: 04282020 02:24 PM by Don Shepherd.)
Post: #1




Fifteen puzzle solvability, Numworks Python
I just received a Numworks calculator and implemented a Python program to determine if a given configuration of the fifteen puzzle is solvable. Very interesting and beautiful calculator. I contacted Numworks with a question and the president of the company replied; excellent support.
List a contains the initial configuration of the 15 puzzle pieces (that you want to test) and the empty (0) cell. The 99 at the beginning is there so I could more easily convert an existing HP17 solver equation, since the Numworks list starts at index 0. The program returns the sum of the number of inversions and row number (14) of the empty cell. If this number is even, the puzzle configuration is solvable. Code:


04092020, 01:24 AM
(This post was last modified: 04092020 01:31 AM by Don Shepherd.)
Post: #2




RE: Fifteen puzzle solvability, Numworks Python
I finally figured out how to pass a list into the program at execution time.
Rather than hard code the 17 values in the program itself, you can instead pass the values when you execute the program like this: fifteen([99,5,15,8,12,13,1,4,10,2,7,14,11,9,3,6,0]) Thus, the program need not change for a new set of data. Remove the list assignment (a = [...]) from the program to do this, and change the def fifteen(): to def fifteen(a): 

04092020, 08:32 AM
(This post was last modified: 04092020 08:40 AM by stored.)
Post: #3




RE: Fifteen puzzle solvability, Numworks Python
Without "99" you can get a bit simpler code:
Code:


04092020, 12:13 PM
Post: #4




RE: Fifteen puzzle solvability, Numworks Python
(04092020 08:32 AM)stored Wrote: Without "99" you can get a bit simpler code:This works for the data you showed, but it does not work with this data: [15,9,2,14,4,6,0,8,11,1,13,3,7,12,5,10] that data should return 58, but it returns 62 

04092020, 01:15 PM
Post: #5




RE: Fifteen puzzle solvability, Numworks Python
You right. I misunderstood case a[i]==0.
Sorry. 

04092020, 01:24 PM
Post: #6




RE: Fifteen puzzle solvability, Numworks Python
May be like this, but not so concise.
Code: def fifteen(a): 

04092020, 03:06 PM
Post: #7




RE: Fifteen puzzle solvability, Numworks Python
(04092020 01:24 PM)stored Wrote: May be like this, but not so concise. I like this approach, but it returns the wrong value for selected cases: [0,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] returns 105, should be 106 [0,14,13,7,15,12,8,6,11,9,5,2,10,4,3,1] returns 86, should be 87 [1,10,11,2,9,8,7,12,0,5,6,13,4,15,14,3] returns 47, should be 48 

04092020, 03:19 PM
(This post was last modified: 04252020 02:15 PM by Albert Chan.)
Post: #8




RE: Fifteen puzzle solvability, Numworks Python
It may be best if the code return (Xrows, inversions), rather than Xrows + inversions
Inversion count are unaffected if the X is removed from the list. To generalize for nxn board, we have: Code: def board(a, n=4): # default 4x4 board >>> board([11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5]) # even n and even sum → solvable (1, 51) >>> board([15,9,2,14,4,6,0,8,11,1,13,3,7,12,5,10]) # even n and even sum → solvable (2, 56) For a 3x3 board, example from https://www.geeksforgeeks.org/checkinst...solvable/ >>> board([1,8,2,0,4,3,7,6,5], n=3) # odd n and even inversions → solvable (2, 10) 

04092020, 03:23 PM
Post: #9




RE: Fifteen puzzle solvability, Numworks Python
Oh, you are right again.
I was sloppy. Code: def fifteen(a): 

04092020, 04:30 PM
Post: #10




RE: Fifteen puzzle solvability, Numworks Python
(04092020 03:23 PM)stored Wrote: Oh, you are right again.Thanks, stored, looks like you did it! I tested with about a dozen examples I have in my files and they all worked. And thanks for enlightening me in aspects of Python I was not familiar with. I am new to that language and you have helped me understand a lot about it. 

04092020, 04:57 PM
Post: #11




RE: Fifteen puzzle solvability, Numworks Python
(04092020 03:19 PM)Albert Chan Wrote: It may be best if the code return (Xrows, inversions), rather than Xrows + inversions Thanks Albert. I would rather return a single value, and if this value is even the puzzle is solvable; if it is odd, the puzzle is not solvable. By adding the row# of the 0 cell to the count of inversions, we always get a single number that tells you whether the puzzle configuration is solvable. If it is not solvable, simply switching any two items with one another makes it solvable. Most 15 puzzles don't have removeable tiles so they are always solvable, but I have one that does and I use this program whenever I play this puzzle. I have written this program for many calcs and computers: BASIC, RPN, HP65, HP12c, HP17b solver... 

04242020, 11:05 PM
(This post was last modified: 04252020 01:43 AM by Albert Chan.)
Post: #12




RE: Fifteen puzzle solvability, Numworks Python
I discovered a neat trick to solve this another way.
First, slide down hole to the bottom row. Example: \(\begin{bmatrix} 11 & & 3 & 8 \\ 1 & 6 & 15 & 10 \\ 7 & 14 & 2 & 13 \\ 4 & 12 & 9 & 5 \\ \end{bmatrix} ⇒ \begin{bmatrix} 11 & 6 & 3 & 8 \\ 1 & 14 & 15 & 10 \\ 7 & 12 & 2 & 13 \\ 4 & & 9 & 5 \\ \end{bmatrix} \) With the hole out of the way, simply flattened the matrix as a list, and sort the numbers. For nxn board, puzzle solvability = is_even(swaps needed to sort the list) Example, this is my selection sort routine to get swaps. Note: different sort algorithm produce different swap numbers, but parity is preserved. Note: no need for actual swaps, we only need number of swaps required. Code: def swaps(a, t=0): # assumed sorted(a) == range(1,n*n) >>> n = 4 >>> a = [11,6,3,8, 1,14,15,10, 7,12,2,13, 4,9,5] >>> sorted(a) == range(1,n*n) True >>> swaps(a) # even swaps = solvable 12  Another example, if list is in reverse order, is it solvable ? Try n=3: [8 7 6 5 4 3 2 1] → (swap 18,27,36,45) → [1 2 3 4 5 6 7 8] For n=3, swaps = 4 = even, thus solvable. In general, for integer n > 1, swaps = floor((n^21)/2) If n=2k, swaps = floor(((2k)^21)/2) = (4k^22)/2 = 2k^21 = odd If n=2k+1, swaps = floor((2k+1)^21)/2) = (4k^2 + 4k)/2 = 2k(k+1) = even → "reversed" puzzle can only be solved for odd nxn board. 

04252020, 02:03 AM
Post: #13




RE: Fifteen puzzle solvability, Numworks Python
(04242020 11:05 PM)Albert Chan Wrote: I discovered a neat trick to solve this another way. Albert, this is very interesting. I'm going to test this with about a dozen 4x4 layouts I have and see if it holds true for them. thanks, Don 

04252020, 08:58 AM
Post: #14




RE: Fifteen puzzle solvability, Numworks Python
Albert, I don't get the expected results for this data:
a=[11,3,8,1,6,15,10,7,14,2,13,4,12,9,5] the empty cell is right after 11 the result should be even (52 per my algorithm), but it is odd (11) the sorted(a) == range(1,n*n) command always returns FALSE, not TRUE Don 

04252020, 10:16 AM
Post: #15




RE: Fifteen puzzle solvability, Numworks Python
(04252020 08:58 AM)Don Shepherd Wrote: Albert, I don't get the expected results for this data: parity of swaps = partiy of inversions. Without shifting hole down to bottom row, for even nxn board, we need to add hole row number: row + inversions = 1 + 51 = 52 = even row + swaps = 1 + 11 = 12 = even But, removing the hole this way, we need another test for odd sized nxn board For odd nxn board, solvability = is_even(inversions) = is_even(swaps) This got me thinking of a simpler test. Move the hole to any even row, for any nxn board, this make row# even Hole at even row: solvability = is_even(inversions) = is_even(swaps) Quote:the sorted(a) == range(1,n*n) command always returns FALSE, not TRUE I were using Python 2.6, above expression just compare the list equality For Python 3, both side only returns an iterator, not actual list. This might work: list(sorted(a)) == list(range(1,n*n)) 

04252020, 01:02 PM
Post: #16




RE: Fifteen puzzle solvability, Numworks Python
(04252020 10:16 AM)Albert Chan Wrote:(04252020 08:58 AM)Don Shepherd Wrote: Albert, I don't get the expected results for this data: Thanks Albert. I'll stick with the original algorithm, I think it is easier to understand and it follows the logic I have used for this problem in other calculators (return number of inversions + row number of empty cell). I do appreciate your work. 

04252020, 04:19 PM
(This post was last modified: 04262020 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 

04252020, 06:33 PM
Post: #18




RE: Fifteen puzzle solvability, Numworks Python
Thanks Albert, I tried your new program with about 20 different configurations of the fifteen puzzle and it performed correctly. Congratulations, and thanks again.


04262020, 03:15 PM
(This post was last modified: 04262020 03:16 PM by ijabbott.)
Post: #19




RE: Fifteen puzzle solvability, Numworks Python
There is a recent (published 20200421) Numberphile video about solvability of 15puzzle configurations, including Sam Loyd's historical 1415 configuration.
— Ian Abbott 

04262020, 05:23 PM
Post: #20




RE: Fifteen puzzle solvability, Numworks Python
(04262020 03:15 PM)ijabbott Wrote: There is a recent (published 20200421) Numberphile video about solvability of 15puzzle configurations, including Sam Loyd's historical 1415 configuration. Thanks Ian. Yes, I have seen several Youtube videos about the 15 puzzle over the years and most of them are very good. The company that manufactured that puzzle with the impossible configuration on the back should have done more research before they finalized their back cover! They should have hired me and I would have made them change it. I love this puzzle because the solvability of a given starting configuration can be programmed easily on most programmable calculators. I have written programs to solve this on the following systems/calculators: 17bii solver original Dartmouth BASIC TI84+ TI Nspire CAS Casio FX9860g slim Android BASIC HP32sii HP32s HP71b Casio Prizm HP12cp HP12c+ HP65 (thanks to Dave Britten) Numworks As I mentioned in another post, most physical versions of this puzzle have interlocking pieces that cannot be removed from the board, and all of those puzzles therefore are automatically solvable unless the manufacturer goofed up. I have a version in which the pieces are removable, so whenever I want to mix them up and try to solve the puzzle, I always run one of my programs to verify that the particular starting configuration is solvable. Of all the possible initial configurations, only half are solvable. Back when I was a teacher, I would do what Sam Loyd did many years ago, present a puzzle with only two numbers switched and see if any of my students could solve it. Of course, after a few minutes of failures they would cheat by physically removing a piece from the board and inserting it where it belonged! Fascinating math. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)