Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
A* implementation solution in Uncategorized category for 8 Puzzle by altarfinch
from copy import deepcopy
DIRECTIONS = {"U": [-1, 0], "D": [ 1, 0], "L": [ 0,-1], "R" : [ 0, 1]}
END = [[1,2,3],[4,5,6],[7,8,0]]
class Node:
def __init__(self, state, previous, g, h, dir):
self.state = state
self.previous = previous
self.g = g #cost from the starting position
self.h = h #cost to the end position (heuristic)
self.dir = dir #direction as a string
#global cost
def f(self):
return self.g + self.h
#the heuristic used is the hamming distance
def euclidianCost(a,b):
cost = 0
for row in range(len(a)):
for col in range(len(a[0])):
pos = getPos(b,a[row][col])
cost += abs(row - pos[0]) + abs(col - pos[1])
return cost
#returns the node that have the lowest estimated cost (f)
def getBestNode(openSet):
firstIter = True
for node in openSet.values():
if firstIter or node.f() < bestF:
firstIter = False
bestNode = node
bestF = bestNode.f()
return bestNode
#get position of an element in an array
def getPos(state,elem):
for row in range(len(state)):
if elem in state[row]:
return (row,state[row].index(elem))
#returns all the adjacent nodes that are valid positions
def getAdjNode(node):
listNode = []
emptyPos= getPos(node.state,0)
for dir in DIRECTIONS.keys():
newPos = (emptyPos[0] + DIRECTIONS[dir][0], emptyPos[1] + DIRECTIONS[dir][1])
if 0 <= newPos[0] < len(node.state) and 0 <= newPos[1] < len(node.state[0]) :
newState = deepcopy(node.state)
newState[emptyPos[0]][emptyPos[1]] = node.state[newPos[0]][newPos[1]]
newState[newPos[0]][newPos[1]] = 0
listNode += [Node(newState, node.state, node.g + 1, euclidianCost(newState, END), dir)]
return listNode
#build the resulting path from the closedSet
def buildPath(closedSet):
node = closedSet[str(END)]
path = ""
while node.dir:
path = node.dir + path
node = closedSet[str(node.previous)]
return path
#implementation of the A* algorithm for best first path
def checkio(puzzle):
#add the start node
openSet = {str(puzzle) : Node(puzzle,puzzle,0,euclidianCost(puzzle,END), "")}
closedSet = {}
#stop condition in case there are no solution
while len(openSet) > 0:
examNode = getBestNode(openSet)
closedSet[str(examNode.state)] = examNode
if examNode.state == END:
#build the final path once the algo finished
return buildPath(closedSet)
adj = getAdjNode(examNode)
#update the closed set
for node in adj:
if str(node.state) in closedSet.keys() or str(node.state) in openSet.keys() and openSet[str(node.state)].f() < node.f():
continue
openSet[str(node.state)] = node
#remove the examined node from the openSet
del openSet[str(examNode.state)]
#if there is no solution return the empty string
return ""
if __name__ == '__main__':
print(checkio([[1, 2, 3],
[4, 6, 8],
[7, 5, 0]]))
June 10, 2013
Comments:
