Here below code will do perform A star algorithm on 8 puzzle problem but , I need to optimize this code can u help me with this.
class Node:
def __init__(self, data, level, fval):
self.data = data
self.level = level
self.fval = fval
Initialize the node with the data, level of the node and the calculated fvalue
def generate_child(self):
""" Generate child nodes from the given node by moving the blank space
either in the four directions {up,down,left,right} """
x, y = self.find(self.data, '_')
""" val_list contains position values for moving the blank space in either of
the 4 directions [up,down,left,right] respectively. """
val_list = [[x, y - 1], [x, y + 1], [x - 1, y], [x + 1, y]]
children = []
for i in val_list:
child = self.shuffle(self.data, x, y, i[0], i[1])
if child is not None:
child_node = Node(child, self.level + 1, 0)
children.append(child_node)
return children
Move the blank space in the given direction and if the position value are out of limits the return None
def shuffle(self, puz, x1, y1, x2, y2):
if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):
temp_puz = []
temp_puz = self.copy(puz)
temp = temp_puz[x2][y2]
temp_puz[x2][y2] = temp_puz[x1][y1]
temp_puz[x1][y1] = temp
return temp_puz
else:
return None
Copy function to create a similar matrix of the given node
def copy(self, root):
temp = []
for i in root:
t = []
for j in i:
t.append(j)
temp.append(t)
return temp
Specifically used to find the position of the blank space
def find(self, puz, x):
for i in range(0, len(self.data)):
for j in range(0, len(self.data)):
if puz[i][j] == x:
return i, j
Initialize the puzzle size by the specified size,open and closed lists to empty
class Puzzle:
def __init__(self, size):
self.n = size
self.open = []
self.closed = []
Accepts the puzzle from the user
def accept(self):
puz = []
for i in range(0, self.n):
temp = input().split(" ")
puz.append(temp)
return puz
Heuristic Function to calculate hueristic value f(x) = h(x) + g(x)
def f(self, start, goal):
return self.h(start.data, goal) + start.level
Calculates the different between the given puzzles
def h(self, start, goal):
temp = 0
for i in range(0, self.n):
for j in range(0, self.n):
if start[i][j] != goal[i][j] and start[i][j] != '_':
temp += 1
return temp
Accept Start and Goal Puzzle state
def process(self):
print("Enter the start state matrix \n")
start = self.accept()
print("Enter the goal state matrix \n")
goal = self.accept()
start = Node(start, 0, 0)
start.fval = self.f(start, goal)
""" Put the start node in the open list"""
self.open.append(start)
print("\n\n")
while True:
cur = self.open[0]
print("")
print(" | ")
print(" | ")
print(" \\\'/ \n")
for i in cur.data:
for j in i:
print(j, end=" ")
print("")
""" If the difference between current and goal node is 0 we have reached the goal node"""
if (self.h(cur.data, goal) == 0):
break
for i in cur.generate_child():
i.fval = self.f(i, goal)
self.open.append(i)
self.closed.append(cur)
del self.open[0]
""" sort the opne list based on f value """
self.open.sort(key=lambda x: x.fval, reverse=False)
puz = Puzzle(3)
puz.process()
whole code can be found here
https://github.com/Ajinkya-Sonawane/Python/blob/master/Artificial%20Intelligence/N%20Puzzle/Npuzzle.py