Fifteen puzzle solvability, Numworks Python

[rprosperi]

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

[Albert Chan]

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

[danielcharles]

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

[Don Shepherd]

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

[toml_12953]

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

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.