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
02-20-2021, 10:10 AM
Post: #23
RE: Fifteen puzzle solvability, Numworks Python
Hello
Given a 4×4 board with 15 tiles (every tile has one number from 1 to 15) and one empty space. The objective is to place the numbers on tiles in order using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space. For example,


15puzzle

Here X marks the spot to where the elements can be shifted and the final configuration always remains the same the puzzle is solvable.
In general, for a given grid of width N, we can find out check if a N*N – 1 puzzle is solvable or not by following below simple rules :


If N is odd, then puzzle instance is solvable if number of inversions is even in the input state.
If N is even, puzzle instance is solvable if
the blank is on an even row counting from the bottom (second-last, fourth-last, etc.) and number of inversions is odd.
the blank is on an odd row counting from the bottom (last, third-last, fifth-last, etc.) and number of inversions is even.
For all other cases, the puzzle instance is not solvable.
What is an inversion here?
If we assume the tiles written out in a single row (1D Array) instead of being spread in N-rows (2D Array), a pair of tiles (a, b) form an inversion if a appears before b but a > b.
For above example, consider the tiles written out in a row, like this:
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 X
The above grid forms only 1 inversion i.e. (2, 1).
Find all posts by this user
Quote this message in a reply
02-23-2021, 12:53 AM
Post: #24
RE: Fifteen puzzle solvability, Numworks Python
(02-20-2021 10:10 AM)danielcharles Wrote:  Hello
Given a 4×4 board with 15 tiles (every tile has one number from 1 to 15) and one empty space. The objective is to place the numbers on tiles in order using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space. For example,


15puzzle

Here X marks the spot to where the elements can be shifted and the final configuration always remains the same the puzzle is solvable.
In general, for a given grid of width N, we can find out check if a N*N – 1 puzzle is solvable or not by following below simple rules :


If N is odd, then puzzle instance is solvable if number of inversions is even in the input state.
If N is even, puzzle instance is solvable if
the blank is on an even row counting from the bottom (second-last, fourth-last, etc.) and number of inversions is odd.
the blank is on an odd row counting from the bottom (last, third-last, fifth-last, etc.) and number of inversions is even.
For all other cases, the puzzle instance is not solvable.
What is an inversion here?
If we assume the tiles written out in a single row (1D Array) instead of being spread in N-rows (2D Array), a pair of tiles (a, b) form an inversion if a appears before b but a > b.
For above example, consider the tiles written out in a row, like this:
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 X
The above grid forms only 1 inversion i.e. (2, 1).

Daniel, I prefer the simpler test for solvability: Add the number of inversions and the row number (1-4) of the empty cell. If that number is odd, the configuration is not solvable, else it is.

If a configuration is not solvable, it can be made solvable by exchanging any two cells.
Find all posts by this user
Quote this message in a reply
02-23-2021, 07:14 AM
Post: #25
RE: Fifteen puzzle solvability, Numworks Python
(04-26-2020 07:46 PM)rprosperi Wrote:  
(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

If the rules didn't prohibit removing pieces then it's not cheating. It depends on how the problem was worded. If the problem statement only said, "arrange the tiles in order." then the students who removed pieces reached the objective. I would give them full credit for their out-of-the-box thinking and word my future problems more carefully. I tried to prepare my students for the real world where no one cares to see your work; they only want results. In the real world you're free to use all sorts of sources for help in solving a problem so I only gave open book tests. I made sure to give problems that couldn't just be looked up, however. If a student could get a good grade on my tests then (s)he really understood the material. I didn't need to see the steps.

Tom L
Cui bono?
Find all posts by this user
Quote this message in a reply
Post Reply 




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