Post Reply 
Fifteen puzzle solvability, Numworks Python
04-26-2020, 07:46 PM
Post: #21
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... Wink

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
04-26-2020, 08:59 PM (This post was last modified: 04-30-2020 02:41 AM by Albert Chan.)
Post: #22
RE: Fifteen puzzle solvability, Numworks Python
We can do sorting *faster* than even QuickSort ! Big Grin
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
Find all posts by this user
Quote this message in a reply
Post Reply 




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