Fifteen puzzle solvability, Numworks Python
04-26-2020, 07:46 PM
Post: #21
 rprosperi Senior Member Posts: 4,461 Joined: Dec 2013
RE: Fifteen puzzle solvability, Numworks Python
(04-26-2020 05:23 PM)Don Shepherd Wrote:  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!

In addition to being a puzzle, seems this was a bit of an integrity checker as well...

--Bob Prosperi
04-26-2020, 08:59 PM (This post was last modified: 04-30-2020 02:41 AM by Albert Chan.)
Post: #22
 Albert Chan Senior Member Posts: 1,242 Joined: Jul 2018
RE: Fifteen puzzle solvability, Numworks Python
We can do sorting *faster* than even QuickSort !
With sorted(a) == range(n*n), we have sorted(a)[x] = x

Fast Algorithm:
For all items in the list, if a[k] != k, keep swapping a[k] and a[a[k]]
Each swap guaranteed 1 correct spot, 2 if lucky.

[11,0,3,8,1,6,15,10,7,14,2,13,4,12,9,5] // puzzle
[13,0,3,8,1,6,15,10,7,14,2,11,4,12,9,5] // swap a[0],a[a[0]]
[12,0,3,8,1,6,15,10,7,14,2,11,4,13,9,5] // swap a[0],a[a[0]]
[4,0,3,8,1,6,15,10,7,14,2,11,12,13,9,5] // swap a[0],a[a[0]]
[1,0,3,8,4,6,15,10,7,14,2,11,12,13,9,5] // swap a[0],a[a[0]]
[0,1,3,8,4,6,15,10,7,14,2,11,12,13,9,5] // swap a[0],a[a[0]] *
[0,1,8,3,4,6,15,10,7,14,2,11,12,13,9,5] // swap a[2],a[a[2]]
[0,1,7,3,4,6,15,10,8,14,2,11,12,13,9,5] // swap a[2],a[a[2]]
[0,1,10,3,4,6,15,7,8,14,2,11,12,13,9,5] // swap a[2],a[a[2]]
[0,1,2,3,4,6,15,7,8,14,10,11,12,13,9,5] // swap a[2],a[a[2]] *
[0,1,2,3,4,15,6,7,8,14,10,11,12,13,9,5] // swap a[5],a[a[5]] *
[0,1,2,3,4,5,6,7,8,14,10,11,12,13,9,15] // swap a[9],a[a[9]] *
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

On my laptop, with 100x100 board, this version has speed ≈ 100 times my selection-sort version.
(I expected more, but Python's list.index is coded in C, and very fast)

Code:
def solvable(a, n, t=0):    # assumed sorted(a) = range(n*n)     a = list(a)             # copy     x = y = a[0]            # locate hole     while x: y=x; x=a[x]; a[y]=0; t+=1     a[0] = 0     t += (n&1 or y//n) + y     for x in a:         while x: y=x; x=a[x]; a[y]=0; t+=1     return t&1 != 0

(*) Above code doubled counted the lucky cases, instead of skipping them. (parity is maintained)
For lucky case, x and a[x] are the same, and nonzero. It take 2 loops before x=0, thus double counted.
This is why I love Python, I would have not known this without experimentation ...

Replace with this for loop skipped over lucky cases, but is slightly slower
Code:
    for i, x in enumerate(a):         while x > i: y=x; x=a[x]; a[y]=0; t+=1
 « Next Oldest | Next Newest »

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