Visit State Check BFS 8-Puzzle

Question

I have implemented the Breadth-First Search for 8-Puzzle however I want to make it more efficient by keeping an account of the visited states/nodes.

If the state has not been visited then append it to visit and continue to expand that state/node else state was the visit then go to the next state/node

I am having trouble only appending the visit nodes and moving to a node that has not been visited.

Here is my code:

import copy
from random import randint


def bfs(puzzle):
    solution = []
    #initialization 
    goal = [0,1,2,3,4,5,6,7,8]
    #possible combination move
    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]
    
    #move check 
    move = 0
    loop = True
    while loop:
            
        node = queue.pop(0)
        print('\nthe state of this game position is:\n ' + str(node.state))
        
        if node.state == goal:
            loop = False
            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))
            #appending the solution
            queue.append(Node(possible_sw, node))
        
        #Test to check if it will show all the visited nodes 
        visit = (queue)
        for node in visit:
            if node in visit:
                print('there is a macth ' + str(node.state))
            else:
                print('there is no macth move on!')
    
    
    while node.parent:
        
        solution.append(node.state.index(8))
        node = node.parent
        move += 1
    print('moves made '+ str(move))
    

    solution.reverse()
    print('moves list '+ str(solution))
    
 
    return solution

Answer 1

When marking nodes as visited, you should not reset visit in each iteration. It should be a collection that is initialised once, at the start of the search, and then extends as nodes are visited.

For this you could use a set. To add states to that set, these states must be hashable, so I would suggest turning them into tuples.

You can decide to mark a node as visited when you pull it from the queue, or, alternatively, you can mark a node as visited when you are about to push it on the queue -- and if it is already visited, not push it unto it. Below I will go for the first approach. If you go for the second, then also mark the initial node as visited before the loop starts.

Not an issue, but here are some other remarks:

• There is no need for the loop name. Just use an unconditional loop (while True) from which you break.
• There is no need for the move name. You can know the number of moves with the len function

The adapted code:

def bfs(puzzle):
    #initialization 
    visited = set()  # Initialise only once
    solution = []
    goal = [0,1,2,3,4,5,6,7,8]
    #possible combination move
    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(f'the state of this game position is:\n {node.state}')
        if node.state == goal:
            break
        
        key = tuple(node.state)  # Make state usuable for adding in a set
        if key in visited:
            continue  # Don't visit twice
        visited.add(key)

        blank = node.state.index(8)
        possible_pos = possible_move[blank]
            
        for i in possible_pos:
            possible_sw = node.state[:]
            possible_sw[blank] = possible_sw[i]
            possible_sw[i] = 8
            queue.append(Node(possible_sw, node))
            
    while node.parent:
        solution.append(node.state.index(8))
        node = node.parent
    print(f'moves made {len(solution)}')
    
    solution.reverse()
    print(f'moves list {solution}')
     
    return solution