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)

CodePudding user response：

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.
• The code has several names which serve no purpose, like l, notFound.
• It uses list which is a native name in Python -- choose a different name.
• The 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 [:].
• Assigning twice to queue in sequence (in the initialisation) makes the first assignment useless. Just have the second assignment.
• The loop in the initialisation part should not be a loop. At that moment you know the queue has only one entry, so iterating it is overkill. You can just output the initial state using puzzle. But maybe you wanted to output the state in the loop...
• There is no need for 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