Fifteen puzzle solvability, Numworks Python - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: Not HP Calculators (/forum-7.html) +--- Forum: Not remotely HP Calculators (/forum-9.html) +--- Thread: Fifteen puzzle solvability, Numworks Python (/thread-14814.html) Pages: 1 2 Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-08-2020 10:41 AM 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 HP-17 solver equation, since the Numworks list starts at index 0. The program returns the sum of the number of inversions and row number (1-4) of the empty cell. If this number is even, the puzzle configuration is solvable. Code:  def fifteen():   a = [99,11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5]   b=0        for i in range (1,17):          if a[i]==0:       b = int((i+3)/4)          for i in range (1,16):     for j in range (i+1,17):       if a[j] != 0 and a[j]>> 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/check-instance-15-puzzle-solvable/ >>> board([1,8,2,0,4,3,7,6,5], n=3) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿# odd n and even inversions → solvable (2, 10) RE: Fifteen puzzle solvability, Numworks Python - stored - 04-09-2020 03:23 PM Oh, you are right again. I was sloppy. Code: def fifteen(a):   b = 0   for i in range(16):     if a[i] == 0:       b = 1 + i // 4   for i in range(15):     for j in range(i+1, 16):       b += (a[j] < a[i]) * (a[j] != 0)   return b RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-09-2020 04:30 PM (04-09-2020 03:23 PM)stored Wrote:  Oh, you are right again. I was sloppy. Code: def fifteen(a):   b = 0   for i in range(16):     if a[i] == 0:       b = 1 + i // 4   for i in range(15):     for j in range(i+1, 16):       b += (a[j] < a[i]) * (a[j] != 0)   return b 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. RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-09-2020 04:57 PM (04-09-2020 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... RE: Fifteen puzzle solvability, Numworks Python - Albert Chan - 04-24-2020 11:05 PM 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)     a = list(a)     # copy     for i,x in enumerate(a,1):         if x != i:             a[a.index(i,i)] = x             t += 1     return t >>> 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^2-1)/2) If n=2k, ﻿ ﻿ ﻿ ﻿ ﻿﻿swaps = floor(((2k)^2-1)/2) = (4k^2-2)/2 = 2k^2-1 = odd If n=2k+1, swaps = floor((2k+1)^2-1)/2) = (4k^2 + 4k)/2 = 2k(k+1) = even → "reversed" puzzle can only be solved for odd nxn board. RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-25-2020 02:03 AM (04-24-2020 11:05 PM)Albert Chan Wrote:  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)     a = list(a)     # copy     for i,x in enumerate(a,1):         if x != i:             a[a.index(i,i)] = x             t += 1     return t >>> 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^2-1)/2) If n=2k, ﻿ ﻿ ﻿ ﻿ ﻿﻿swaps = floor(((2k)^2-1)/2) = (4k^2-2)/2 = 2k^2-1 = odd If n=2k+1, swaps = floor((2k+1)^2-1)/2) = (4k^2 + 4k)/2 = 2k(k+1) = even → "reversed" puzzle can only be solved for odd nxn board. 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 RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-25-2020 08:58 AM 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 RE: Fifteen puzzle solvability, Numworks Python - Albert Chan - 04-25-2020 10:16 AM (04-25-2020 08:58 AM)Don Shepherd Wrote:  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) 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)) RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-25-2020 01:02 PM (04-25-2020 10:16 AM)Albert Chan Wrote:   (04-25-2020 08:58 AM)Don Shepherd Wrote:  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) 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)) 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. RE: Fifteen puzzle solvability, Numworks Python - Albert Chan - 04-25-2020 04:19 PM 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)     a = list(a)         # copy     h = a.index(0)      # locate hole     a.pop(h)            # remove hole     t = n&1 or h//n     # handle odd or even nxn board     for i,x in enumerate(a,1):         if x != i:             a[a.index(i,i)] = x             t += 1      # add selection sort swaps     return t&1 != 0` >>> 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 RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-25-2020 06:33 PM Thanks Albert, I tried your new program with about 20 different configurations of the fifteen puzzle and it performed correctly. Congratulations, and thanks again. RE: Fifteen puzzle solvability, Numworks Python - ijabbott - 04-26-2020 03:15 PM There is a recent (published 2020-04-21) Numberphile video about solvability of 15-puzzle configurations, including Sam Loyd's historical 14-15 configuration. RE: Fifteen puzzle solvability, Numworks Python - Don Shepherd - 04-26-2020 05:23 PM (04-26-2020 03:15 PM)ijabbott Wrote:  There is a recent (published 2020-04-21) Numberphile video about solvability of 15-puzzle configurations, including Sam Loyd's historical 14-15 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 TI-84+ TI Nspire CAS Casio FX-9860g slim Android BASIC HP-32sii HP-32s HP-71b Casio Prizm HP-12cp HP-12c+ HP-65 (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.