3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It depends on where you place the numbers and the blank space ! $\endgroup$ – Jean Marie Jan 4 at 22:41
  • $\begingroup$ Apparently. If this should be hint I don't understad it. I have to find permutation of these numbers which is most difficult to solve and count the moves. But I don't see any other way than brute force. $\endgroup$ – KarmaL Jan 5 at 16:01
  • $\begingroup$ Does a "move" consist of transposing the blank space with an adjacent space? (Some people consider it a single move whenever the blank space moves either horizontally or vertically, no matter how far.) $\endgroup$ – Barry Cipra Jan 6 at 22:22
  • $\begingroup$ @BarryCipra only the blank space with an adjacent space $\endgroup$ – KarmaL Jan 6 at 22:26
  • 1
    $\begingroup$ Well, If you want to solve it on computer then you can do it with A* algorithm and manhattan distance. If this is the case then let me know. I can explain as i have implemented such heuristic based algorithm and it does not need to be 3x3 matrix but it can be any NxN matrix. $\endgroup$ – Khan Saab Jan 8 at 0:46
2
+50
$\begingroup$

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)]
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I understand how it works but I don't know how to implement it. How do you tell the program that neighbours are created only with chnaging place of 0 and one number? I was trying to create this 'tree' of position by hand but I somehow ended with position [7,6,4,5,3,2,1,0] and 64 moves which is not correct. $\endgroup$ – KarmaL Jan 11 at 19:13
  • $\begingroup$ The level of help we can give you depends on where this problem is coming from. Is it homework? Quiz? What level of help are you allowed? Without knowing those, here's my general advice: I assume you have a function that takes a position as input as returns a list of positions as output, where each output position is reachable from the input in $1$ move, right? Debug this function carefully, because if this is messed up your tree search will be wrong. $\endgroup$ – antkam Jan 12 at 0:35
  • $\begingroup$ I am allowed any help I can find. It's one of the exercises I should be able to solve before I take an exam. So it's not homework or quiz. Teacher gave us some tasks to try to solve home and this one I am not able to solve. So before I go to exam I want to know how to solve this because in the exam can appear something similar or based on similar priciple. $\endgroup$ – KarmaL Jan 13 at 19:18
  • $\begingroup$ If you could help me I would appreciate more the way how you find this solution then just the solution. I suppose that you are able to find the positions for any number of moves and not only in 2*4 puzzle, right? Like in this one if you have 1 mobe then there are to positions [1,2,3,4;5,6,0,7] and [1,2,3,0;5,6,7,4] . $\endgroup$ – KarmaL Jan 13 at 19:59
  • $\begingroup$ Pls see my update. Hope it helps! $\endgroup$ – antkam Jan 14 at 16:06
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So it works like I have written? From the solved puzzle always add one move and do it as many times as you will be creating new combination with this move? $\endgroup$ – KarmaL Jan 8 at 12:00
  • $\begingroup$ Do all the one-move positions then all the two-move positions and so on, otherwise you might take many moves to reach a position that you could have reached in fewer. $\endgroup$ – Empy2 Jan 8 at 15:41
0
$\begingroup$

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:

enter image description here

You can get output like this:

enter image description here

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your program optimally solves a mixed state. The question however is about finding the particular state that takes the most moves when solved optimally. While you could solve all the states one by one with your program to find the worst case, there are better ways provided you have enough memory available. $\endgroup$ – Jaap Scherphuis Jan 9 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.