CODEWITHSUNDEEP
pythonalgorithm
Donbeo
Donbeo

Reputation: 17617

8 puzzle compute neighbours python

I am writing an algorithm to solve the 8 puzzle. https://en.wikipedia.org/wiki/15_puzzle

A state is represented by a tuple (1,2,3,4,5,6,7,8,0) where 0 is the free box ( this is equivalent to a 3*3 matrix).

Given a state of the puzzle p = (1,3,2,5,4,6,0,7,8) I have written a function to compute the neighbours. 

def neighbours(p):
    p = np.array(p).reshape(3,3)
    ind0 = np.argwhere(p == 0).squeeze()
    x0, y0 = ind0

    ind_neig = [[ind0[0] - 1, ind0[1]], 
                [ind0[0] + 1, ind0[1]],
                [ind0[0], ind0[1] - 1],
                [ind0[0], ind0[1] + 1]]

    ind_neig = [ind for ind in ind_neig if min(ind) >= 0 and max(ind) < 3]

    neig = [ p.copy() for i in range(len(ind_neig))]

    for i in range(len(ind_neig)):
        x, y = ind_neig[i]
        neig[i][x0, y0] = p[x, y]
        neig[i][x, y] = 0

    neig = [tuple(np.ravel(i)) for i in neig]
    return neig

I would like a quicker version of the neighbours function and that possibly does not require the numpy library. In particular I would like a function that can be used also when the puzzle has larger dimension such as the 15- puzzle

Upvotes: 4

Views: 1464

Answers (1)

Nir Alfasi
Nir Alfasi

Reputation: 53535

I think you'll find the following implementation pretty straightforward, plus, it doesn't use numpy:

def neighbours(p):
    res = []
    ind = p.index(0)
    if not top(ind):
        res.append(up_neig(p, ind))
    if not bottom(ind):
        res.append(down_neig(p, ind))
    if not left(ind):
        res.append(left_neig(p, ind))
    if not right(ind):
        res.append(right_neig(p, ind))
    return res

def top(ind):
    return ind < 3

def bottom(ind):
    return ind > 5

def left(ind):
    return ind in [0, 3, 6]

def right(ind):
    return ind in [2, 5, 8]

def up_neig(p, ind):
    _p = list(p)
    _p[ind], _p[ind-3] = _p[ind-3], _p[ind]
    return tuple(_p)

def down_neig(p, ind):
    _p = list(p)
    _p[ind], _p[ind+3] = _p[ind+3], _p[ind]    
    return tuple(_p)

def left_neig(p, ind):
    _p = list(p)
    _p[ind], _p[ind-1] = _p[ind-1], _p[ind]
    return tuple(_p)

def right_neig(p, ind):
    _p = list(p)
    _p[ind], _p[ind+1] = _p[ind+1], _p[ind]
    return tuple(_p)

p = (1,3,2,5,4,6,0,7,8)
print neighbours(p)  # [(1, 3, 2, 0, 4, 6, 5, 7, 8), (1, 3, 2, 5, 4, 6, 7, 0, 8)]

Upvotes: 3

Related Questions