Sliding puzzle 2*4

Question

I have a task that I have to solve and I would appreciate some hints or links.

If you know Lloyd's Fifteen this is based on the same principle but half size. I have a sliding puzzle 2*4 with numbers 1-7 and one blank space. My task is to find out from which starting position I need the most moves to put it into the right order(1234567_) and the number of moves.

I generated all permutation and for each one, I know if it has a solution or not, and I am able to solve some given starting combination, but I don't know how to find the most difficult start and count the moves.

I found some step by step tutorial on how to solve this puzzle. What if I use it but start from the end? But even if I find some difficult start how would I be sure that it is the most difficult one?

Answer 1

There are 20160 solvable positions. Each has two or three neighbours, one move away.
One of the positions needs no moves. Its neighbours need one move; their neighbours need two moves; (or fewer if you've seen it before) and so on.
So find all positions that need one move; then for each $n$, use the $n$-move positions to find the new $n+1$-move positions. Eventually you will run out of new positions.

Answer 2

I implemented such an algorithm few years ago. Basically the idea is to use A* algorithm with either manhattan distance or hamming distace.

The basic idea:

You can get output like this:

Full link to code is here: Link to code

If puzzle is too hard and requires more memory then it will throw GC_overhead_limit_exceeded unless you give it more memory.

Answer 3

Following the advice of Empy2 (which is a form of Breadth First Search), my code found that the worst position is unique:

It takes $36$ moves to go from $[0, 7, 2, 1; 4, 3, 6, 5]$ to the solved position $[1,2,3,4; 5, 6, 7, 0]$ where $0$ denotes the space.

(Also, in my (limited) experience, A* may be suited for solving a particular position. But the OP task is to find the worst position, and for that, BFS is easier - conceptually, implementationally, etc.)

UPDATE: Here is the part of my code that, given an old position, generates all the new positions reachable by $1$ move. Once you have this, you can follow Empy2's hints or other descriptions of breadth first search to generate positions reachable (from solved position) in $1$ move, then in $2$ moves, then in $3$ moves, etc. Hope this helps!

def swapPos(p, k0, k):
    """
    p is position tuple
    k, k0 are indices into tuple 
    returns new tuple after swapping contents of p[k] & p[k0]
    """

    swap = p[k]
    q = list(p)
    q[k0], q[k] = swap, 0
    return tuple(q)

def nextPos(p, m, n):
    """
    m, n = board size: m rows, n columns
    p = input position tuple, 1-D, listed row by row
    returns list of all new positions reachable from p in 1 step
    """    

    k0 = p.index(0)     # where is the space (0)
    i, j = k0/n, k0%n   # row no. & col no. of space

    res = []

    if i > 0:
        res.append(swapPos(p, k0, k0-n))        
    if i < m-1:
        res.append(swapPos(p, k0, k0+n))
    if j > 0:
        res.append(swapPos(p, k0, k0-1))        
    if j < n-1:
        res.append(swapPos(p, k0, k0+1))

    return res

# example:
In: nextPos((1,2,3,4,5,6,7,0), 2, 4)
Out: [(1, 2, 3, 0, 5, 6, 7, 4), (1, 2, 3, 4, 5, 6, 0, 7)]