I am trying to implement various algorithms to solve a 8 puzzle problem. For those who are not familiar with the problem, there are 3 rows and 3 columns,and a one empty tile, represented by zero here. It looks like this:

Here's my code:

initial_state = [1,2,3,4,5,6,7,0,8]
goal_state = [1,2,3,4,5,6,7,8,0]


moves = [
    [ (0,1), (0,3) ],
    [ (1,1), (1,0), (1,4) ],
    [ (2,1), (2,5) ],
    [ (3,0), (3,6), (3,4) ],
    [ (4,1), (4,7), (4,5), (4,3) ],
    [ (5,2), (5,8), (5,4) ],
    [ (6,3), (6,7) ],
    [ (7,4), (7,8), (7,6) ],
    [ (8,5), (8,7) ],
]
def find_new_nodes(state):
    return  [ swap_positions(state[:],a,b) for a,b in moves[find_zero(state)] ]

def find_zero(state):
    return state.index(0)

def swap_positions(lis, pos1, pos2):
    lis[pos1],lis[pos2] = lis[pos2],lis[pos1]
    return lis

def BFS(start,goal):

    visited = [] #visited list
    node_queue= [start] #main queue
    visited.append(start)
    while node_queue:
        current = node_queue.pop(0)
        print(current)
        if current == goal:
            return True
       for newnode in find_new_nodes(current):
           if newnode not in visited:
               node_queue.append(newnode)
               visited.append(newnode)

    return False

def DFS(start,goal):

    visited = [] #visited list
    node_queue= [start] #main queue
    visited.append(start)
    while node_queue:
        current = node_queue.pop()
        print(current)
        if current == goal:
            return True
        for newnode in find_new_nodes(current):
            if newnode not in visited:
                node_queue.append(newnode)
                visited.append(newnode)

    return False

I changed the pop(0) to pop() so that it is lifo, not fifo. My output of DFS seems like a never ending loop, but it is just a few moves away with this starting list and it reaches the goal with the bfs function in 3 moves. Why doesn't it work?

CodePudding user response：

There is nothing wrong going on. It is just slow for a couple of reasons.

The first reason for it being slow is that, thanks to it being a DFS, it winds up having to look at all 181440 solvable states before finding the answer.

The second reason is that the line if newnode not in visited winds up having to scan the entire array. So hundreds of thousand of times we need to scan a list that is over 100,000 long, and comparing arrays isn't exactly cheap. This requires tens of billions of operations, which takes a while.

You can eliminate the second problem with switching to a set like this:

def DFS(start,goal):

    visited = set() #visited list
    node_queue= [start] #main queue
    visited.add(tuple(start))
    while node_queue:
        current = node_queue.pop()
        print((len(visited), current))
        if current == goal:
            return True
        for newnode in find_new_nodes(current):
            if tuple(newnode) not in visited:
                node_queue.append(newnode)
                visited.add(tuple(newnode))

    return False

You can verify by inspection that the algorithm isn't fundamentally changed, but its performance should be improved. And indeed on my laptop it now manages to finish in about a second.