Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for 8 Puzzle by sleepyone
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def push(self, item, priority):
pair = (priority,item)
heapq.heappush(self.heap,pair)
def pop(self):
(priority,item) = heapq.heappop(self.heap)
return item
def isEmpty(self):
return len(self.heap) == 0
def locate_zero(pos):
for x in range(0, len(pos)):
for y in range(0, len(pos[x])):
if pos[x][y] == 0:
return (x,y)
return (-1,-1)
moves = [('U', (-1,0)), ('D', (1,0)), ('L', (0,-1)), ('R', (0,1))]
def fix(move, pos, x, y):
pos = [[y for y in x] for x in pos] # Deepcopy of pos
d, (dx, dy) = move
pos[x][y], pos[x+dx][y+dy] = pos[x+dx][y+dy], pos[x][y]
return (d, pos)
def neighbors(pos):
x, y = locate_zero(pos)
m = [m for m in moves if -1 < x+m[1][0] < len(pos) and -1 < y+m[1][1] < len(pos[x])]
return [fix(move, pos, x, y) for move in m]
def dist(a, b):
# Hamming distance
return sum([1 for x in a for y in b if x != y])
def astar(start, goal=[[1,2,3],[4,5,6],[7,8,0]]):
"""
Notion of a state is represented as the tuple (pos, path).
seen contains positions.
"""
seen = set()
fringe = PriorityQueue()
fringe.push((start, ''), dist(start, goal))
while not fringe.isEmpty():
(pos, path) = fringe.pop()
key = ''.join([str(el) for row in pos for el in row])
if key in seen:
continue
if pos == goal:
return path
seen.add(key)
for n in neighbors(pos):
move, newpos = n
fringe.push((newpos, path + move), dist(newpos, goal) + len(path))
return ''
def checkio(puzzle):
'''
Solve the puzzle
U - up
D - down
L - left
R - right
'''
return astar(puzzle)
April 13, 2013
Comments:
