Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
breath-first search solution in Clear category for 8 Puzzle by kurosawa4434
MY_GOAL = '123456780'
MOVE = {0: 'RD', 1: 'LDR', 2: 'LD', 3: 'URD', 4: 'UDLR',
5: 'ULD', 6: 'UR', 7: 'LUR', 8: 'LU'}
def checkio(puzzle):
def move_empty_cell(dr, pz, ep):
if dr == 'U':
return pz[:ep-3] + '0' + pz[ep-2:ep] + pz[ep-3] + pz[ep+1:]
elif dr == 'D':
return pz[:ep] + pz[ep+3] + pz[ep+1:ep+3] + '0' + pz[ep+4:]
elif dr == 'R':
return pz[:ep] + pz[ep+1] + '0' + pz[ep+2:]
elif dr == 'L':
return pz[:ep-1] + '0' + pz[ep-1] + pz[ep+1:]
serialize_puzzle = ''.join([str(puzzle[y][x]) for y in range(3) for x in range(3)])
memo = set(serialize_puzzle)
next_pz = [(serialize_puzzle, '')]
while 1:
pz = next_pz[:]
next_pz = []
for p, step in pz:
e_pos = p.index('0')
for dr in MOVE[e_pos]:
new_pz = move_empty_cell(dr, p, e_pos)
if new_pz not in memo:
if new_pz == MY_GOAL:
return step+dr
memo.add(new_pz)
next_pz.append((new_pz, step+dr))
Aug. 28, 2016
Comments:
