Fifteen puzzle solvability, Numworks Python

[Don Shepherd]

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]<a[i]:
        b=b+1
        
  return b

[Don Shepherd]

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):

[stored]

Without "99" you can get a bit simpler code:

Code:


def fifteen(a):
  b = 0
  for i in range(15):
    for j in range(i+1, 16):
      b += a[j] < a[i]
  return b


a = [11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5]
print(fifteen(a))  # 52

[Don Shepherd]

(04-09-2020 08:32 AM)stored Wrote:  Without "99" you can get a bit simpler code:

Code:


def fifteen(a):
  b = 0
  for i in range(15):
    for j in range(i+1, 16):
      b += a[j] < a[i]
  return b


a = [11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5]
print(fifteen(a))  # 52

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

[stored]

You right. I misunderstood case a[i]==0.
Sorry.

[stored]

May be like this, but not so concise.

Code:

def fifteen(a):
  b = 0
  for i in range(16):
    if a[i] == 0:
      b += (i + 3) // 4
  for i in range(15):
    for j in range(i+1, 16):
      b += (a[j] < a[i]) * (a[j] != 0)
  return b

[Don Shepherd]

(04-09-2020 01:24 PM)stored Wrote:  May be like this, but not so concise.

Code:

def fifteen(a):
  b = 0
  for i in range(16):
    if a[i] == 0:
      b += (i + 3) // 4
  for i in range(15):
    for j in range(i+1, 16):
      b += (a[j] < a[i]) * (a[j] != 0)
  return b

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

[Albert Chan]

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
    a=list(a)           # copy
    x=a.index(0)        # locate X
    b=a.pop(x)          # remove X
    for i,ai in enumerate(a):
        for aj in a[i+1:]:
            if aj<ai: b += 1
    return 1+x//n, b    # Xrows, inversions

>>> 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-inst...-solvable/

>>> board([1,8,2,0,4,3,7,6,5], n=3)                            # odd n and even inversions → solvable
(2, 10)

[stored]

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

[Don Shepherd]

(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.

[Don Shepherd]

(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...

[Albert Chan]

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.

[Don Shepherd]

(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

[Don Shepherd]

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

[Albert Chan]

(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))

[Don Shepherd]

(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.

[Albert Chan]

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

[Don Shepherd]

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

[ijabbott]

There is a recent (published 2020-04-21) Numberphile video about solvability of 15-puzzle configurations, including Sam Loyd's historical 14-15 configuration.

[Don Shepherd]

(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.