This is an 8 puzzle and uses bfs and dfs to solve find the solution and prints out the path to the goal. I am having trouble poping and appending the children so that it can find the solution. My error is that it will only print out the two options and does not branch out from the possible solution. The terminal is still going despite not printing out anything.
Here is my code and on the bottom is a test case.
import copy
#This is the only file you need to work on. You do NOT need to modify other files
# Below are the functions you need to implement. For the first project, you only need to finish implementing bfs() and dfs()
#here you need to implement the Breadth First Search Method
def bfs(puzzle):
list = []
#initialization
state = copy.deepcopy(puzzle)
goal = [0,1,2,3,4,5,6,7,8]
possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
#appending the first state
queue = []
queue = [Node(state)]
for node in queue[:]:
print('the state of this game position is:\n ' + str(node.state))
loop = True
notFound = True
l = 0
while loop:
for node in queue:
#blank index in each state
blank = node.state.index(8)
print('the index of the blank is '+ str(blank))
#The possible position
possible_pos = possible_move[blank]
print('possible pos '+ str(possible_pos))
if state != goal:
for i in possible_pos:
possible_sw = copy.deepcopy(node.state)
print('index swap = '+ str(i))
temp = possible_sw[i]
possible_sw[i] = 8
possible_sw[blank] = temp
print('the child nodes is ' + str(possible_sw))
node.insertChild(possible_sw)
if possible_sw == goal:
print('end')
notFound = False
loop = False
#check each child and find the goal state
for node in queue[:]:
for child_state in node.children:
if child_state == [0,1,2,3,4,5,6,7,8]:
final_state = child_state
print('the final state is '+ str(final_state.state))
queue.pop(0)
#find the parent path
while node.parent and loop is False:
sol_path = final_state.state
list.append(sol_path.index(8))
if final_state.parent is not None:
final_state = final_state.parent
else:
parent = False
list.reverse()
list.pop(0)
print('moves list '+ str(list))
return list
#here you need to implement the Depth First Search Method
def dfs(puzzle):
list = []
return list
#This will be for next project
def astar(puzzle):
list = []
return list
def swap(list, pos1, pos2):
list[pos1],list[pos2] = list[pos2], list[pos1]
return list
class Node:
def __init__(self,state,parent = None):
self.parent = parent
self.state = state
self.children = []
def insertChild(self, child_state):
self.children.append(Node(child_state,self))
#test cases
# p =[0, 1, 2, 3, 4, 5, 8, 6, 7]
p = [0, 1, 2, 3, 4, 5, 6, 8, 7]
#p = [0, 1, 2, 3, 8, 4, 6, 7, 5]
#p =[0, 4, 1, 3, 8, 2, 6, 7, 5]
bfs(p)
print("+++++++++++++++++++++")
#dfs(p)
There are several issues with your attempt:
The queue never receives more entries; queue.append
is never called. On the other hand, the inner loop over queue[:]
empties the queue with pop
, removing its only element. And from that moment on the queue remains empty.
The Node
constructor is called only once, so there will never be more than one node, and the test node.parent
will always be false, making the last while
loop useless, and the moveslist (if any) will never be printed
If the end is not found in the first iteration -- meaning the initial position is not one move away from the goal -- the outer loop will get into an infinite loop: on its second iteration the queue is empty, so there is nothing to do, and the loop
name will never become True.
if state != goal
makes little sense as the state
name never changes in the loop. If anything, this should reference node.state
, not state
.
The list.pop(0)
at the very end unnecessarily removes a move. The loop condition already checks if the node has a parent -- so skipping the root state -- so then you'll miss two states.
The code does not check whether the initial position is maybe the goal position, and so it will not return an empty move list as solution when this is the case.
Some other remarks:
swap
is never called.l
, notFound
.list
which is a native name in Python -- choose a different name.children
attribute of the Node
instances is not useful. Although you iterate it to find the final state, the logic for identifying whether the goal was reached, is already present elsewhere in the code... it doesn't need children
.deepcopy
is not needed: the lists you use are not "deep". You can simply copy them by applying the list
(native) function, or slicing them with [:]
.queue
in sequence (in the initialisation) makes the first assignment useless. Just have the second assignment.puzzle
. But maybe you wanted to output the state in the loop...temp
to perform a swap. First of all, Python can do tuple assignment, but also: a move is not really a swap of two unknown values: you know that one of the two is the empty cell (8), so you can safely overwrite that cell with the other cell's value, and then set the other cell's value to 8 -- no temp
is needed.Here is your code corrected with the above remarks:
class Node:
def __init__(self,state,parent = None):
self.parent = parent
self.state = state
def bfs(puzzle):
solution = []
#initialization
goal = [0,1,2,3,4,5,6,7,8]
possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
node = Node(puzzle)
queue = [node]
while True:
node = queue.pop(0)
print('the state of this game position is:\n ' + str(node.state))
if node.state == goal:
break
blank = node.state.index(8)
print('the index of the blank is '+ str(blank))
possible_pos = possible_move[blank]
print('possible pos '+ str(possible_pos))
for i in possible_pos:
possible_sw = node.state[:]
print('index swap = '+ str(i))
possible_sw[blank] = possible_sw[i]
possible_sw[i] = 8
print('the child node is ' + str(possible_sw))
queue.append(Node(possible_sw, node))
while node.parent:
solution.append(node.state.index(8))
node = node.parent
solution.reverse()
print('moves list '+ str(solution))
return solution