Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
16-liner: heapq over and over again solution in Clear category for 8 Puzzle by przemyslaw.daniel
def checkio(puzzle, goal=((1, 2, 3), (4, 5, 6), (7, 8, 0))):
from heapq import heapify, heappush, heappop
queue, visited = [(0, "", tuple(map(tuple, puzzle)))], set([])
heapify(queue)
while queue:
depth, steps, puzzle = heappop(queue)
if puzzle == goal: return steps
if puzzle in visited: continue
visited |= {puzzle}
x, y = divmod(sum(puzzle, ()).index(0), 3)
neighbors = [(1,0,"D"), (-1,0,"U"), (0,1,"R"), (0,-1,"L")]
for i, j, s in neighbors:
if not (0 <= x+i < 3 and 0 <= y+j < 3): continue
pzl = [list(x) for x in puzzle]
pzl[x][y], pzl[x+i][y+j] = pzl[x+i][y+j], pzl[x][y]
heappush(queue, (depth+1, steps+s, tuple(map(tuple, pzl))))
Jan. 10, 2018
Comments: