The code needs to produce nodes for the current state. and when the current state isnt the goal state, its supposed to create child nodes and pick the node with the smallest manhattan distance and make that the next node in the list. Then print all of the states of the board until the goal state classÂ
PriorityQueue(): def __init__(self): self.thisQueue = [] def push(self, thisNode): heapq.heappush(self.thisQueue, (thisNode.val, -thisNode.id, thisNode)) def pop(self): return heapq.heappop(self.thisQueue)[2] def isEmpty(self): return len(self.thisQueue) == 0 def length(self): return len(self.thisQueue) class Set(): def __init__(self): self.thisSet = set() def add(self, entry): if entry is not None: self.thisSet.add(entry.__hash__()) def length(self): return len(self.thisSet) def isMember(self, query): return query.__hash__() in self.thisSet class Node(): def __init__(self, val, startstate, endstate, depth, cost): global nodeid self.id = nodeid nodeid += 1 self.val = val self.state = startstate self.endstate = endstate self.depth = 0 self.cost = cost def __str__(self): return 'Node: id=%d val=%d' % (self.id, self.val) class State(): def __init__(self): self.xpos = 0 self.ypos = 0 self.tiles = [[0, 1, 2], [3, 4, 5], [6, 7, 8]] self.cost= cost def left(self): if self.ypos == 0: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos - 1] s.ypos -= 1 s.tiles[s.xpos][s.ypos] = 0 return s def right(self): if self.ypos == 2: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos + 1] s.ypos += 1 s.tiles[s.xpos][s.ypos] = 0 return s def up(self): if self.xpos == 0: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos - 1][s.ypos] s.xpos -= 1 s.tiles[s.xpos][s.ypos] = 0 return s def down(self): if self.xpos == 2: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos + 1][s.ypos] s.xpos += 1 s.tiles[s.xpos][s.ypos] = 0 return s def __hash__(self): return (tuple(self.tiles[0]),tuple(self.tiles[1]),tuple(self.tiles[2])) def __str__(self): return '%d %d %d%d %d %d%d %d %d'%( self.tiles[0][0],self.tiles[0][1],self.tiles[0][2], self.tiles[1][0],self.tiles[1][1],self.tiles[1][2], self.tiles[2][0],self.tiles[2][1],self.tiles[2][2]) def copy(self): s = copy.deepcopy(self) return s def __eq__(self, other): if other is None: return False return self.tiles == other.tiles class State(): def __init__(self): self.xpos = 0 self.ypos = 0 self.tiles = [[0, 1, 2], [3, 4, 5], [6, 7, 8]] self.cost= 0 def left(self): if self.ypos == 0: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos - 1] s.ypos -= 1 s.tiles[s.xpos][s.ypos] = 0 return s def right(self): if self.ypos == 2: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos][s.ypos + 1] s.ypos += 1 s.tiles[s.xpos][s.ypos] = 0 return s def up(self): if self.xpos == 0: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos - 1][s.ypos] s.xpos -= 1 s.tiles[s.xpos][s.ypos] = 0 return s def down(self): if self.xpos == 2: return None s = self.copy() s.tiles[s.xpos][s.ypos] = s.tiles[s.xpos + 1][s.ypos] s.xpos += 1 s.tiles[s.xpos][s.ypos] = 0 return s def __hash__(self): return (tuple(self.tiles[0]),tuple(self.tiles[1]),tuple(self.tiles[2])) def __str__(self): return '%d %d %d%d %d %d%d %d %d'%( self.tiles[0][0],self.tiles[0][1],self.tiles[0][2], self.tiles[1][0],self.tiles[1][1],self.tiles[1][2], self.tiles[2][0],self.tiles[2][1],self.tiles[2][2]) def copy(self): s = copy.deepcopy(self) return s def __eq__(self, other): if other is None: return False return self.tiles == other.tiles def expand(current_node, closedlist, goal_state,h): closedlist.add(current_node.state) # add the non solution to a closed list successors = [] # Initialize a node that will hold the subsequent values current_state=current_node.state # Variable to hold the state of the current node up_child = current_state.up() # Name all of the values of the of the current moves down_child = current_state.down() right_child = current_state.right() left_child = current_state.left() children = [left_child, right_child, up_child, down_child] for child in children: if child is not None and not closedlist.isMember(child): s = Node(0, child, " ", None, current_node.depth + 1) s.parent_node = current_node if child == left_child: s.action = "left" elif child == right_child: s.action = "right" elif child == up_child: s.action = "up" elif child == down_child: s.action = "down" s.cost = current_node.cost + 1 successors.append(s) return successors def step_cost(child_node,goal_state, h): if (h =="0"): return int(1) if (h=="1"): return int(manhattan(child_node.state.tiles,goal_state.tiles)) def misplaced(currenttiles, stiles): misplaced = 0 for i in range(len(stiles)): for j in range(len(currenttiles)): if stiles[i][j] != currenttiles[i][j]: misplaced += 1 return misplaced def manhattan(currenttiles, stiles): total = 0 for i in range(len(stiles)): for j in range(len(currenttiles)): if stiles[i][j] != currenttiles[i][j]: y = stiles[i][j] a = i b = j for k in range(len(stiles)): for l in range(len(stiles)): if currenttiles[k][l] == y: d = k e = l count = (abs(d - a) + abs(e - b)) total += count return total def copy(self): s = State() s.xpos = self.xpos s.ypos = self.ypos s.tiles = [row[:] for row in self.tiles] return s def tree_search(frontier,initial_state, goal_state, closedlist, h): #closedlist.add(current_node.state) start_node = Node(0, initial_state, None, None,0) # print(start_node.val) frontier.push(start_node) V = 0 N = 0 d = 0 while not frontier.isEmpty(): #While the frontier isnt empty if frontier.length() > N: # Update the N value based on how many values are in the frontier N = frontier.length() current_node = frontier.pop() #Pop off the node V += 1 #Increment the V value if current_node.state == goal_state: #if the state of the first node is the same as the goal state d = current_node.depth # Found the solution print(current_node.state) return current_node, V, N, d #Return the node and all of the values expanded = expand(current_node, closedlist, goal_state, h) #if its not the goal state, send the node to the expand function for node in expanded: frontier.push(node) return None, V, N, d def main(): global nodeid frontier=PriorityQueue() inputs = [] for line in sys.stdin: inputs += line.split() array = [ [int(inputs[0]), int(inputs[1]), int(inputs[2])], [int(inputs[3]), int(inputs[4]), int(inputs[5])], [int(inputs[6]), int(inputs[7]), int(inputs[8])] ]goal_state = State() goal_state.tiles = [[0, 1, 2], [3, 4, 5], [6, 7, 8]] s = State() current = State() current.tiles = array s.tiles = [[0, 1, 2], [3, 4, 5], [6, 7, 8]] print(array) printMan = manhattan(array, goal_state.tiles) print("Initial State:") print(current) print("Goal State:") print(goal_state) print("Manhattan Distance:", printMan) closedlist = Set() nodeid = 0 h=0; # print(tree_search(frontier,current,goal_state,closedlist,h)) d, N, V,current_node = tree_search(frontier,current, goal_state, closedlist, h) print("Heuristic", h) print(current_node) print("Nodes Visited/Expanded (V):", V) print("Maximum Nodes Stored in Memory (N):", N) print("Depth of Optimal Solution (d):", d) # print(current_node) main()
