Python: My Depth-Limited Search algorithm won't work

Question

new to Python.

I have implemented a Depth Limited Search Algorithm to find a route from S to G. Where S is the starting position and G is the destination.

R represents a road while X represents an obstacle that we cannot pass through.
ADJ is a dictionary containing neighbouring paths from a given location.

So for S the neighbours are 2 and 6. 2 and 6 represents the neighbouring roads. I have not included X as X is an obstacle. However, it cannot move diagonally if one of the directions composing the diagonal contains an X.

The problem is that when I run the code below my algorithm does not find a route and gets stuck forever until it exceeds the depth limit.
There is a route from S to G but my algorithm does not find it.
How do I resolve this error? Thanks
Here is my code:

ADJ = {}
""""
SRRXG
RXRXR
RRRXR
XRXRR
RRRRX
"""
ADJ['S'] = ['2', '6']
ADJ['2'] = ['S', '3']
ADJ['3'] = ['2','8']
ADJ['G'] = ['10']
ADJ['6'] = ['S', '11']
ADJ['8'] = ['3', '13']
ADJ['10'] = ['G', '15']
ADJ['11'] = ['6', '12']
ADJ['12'] = ['11', '13', '17']
ADJ['13'] = ['8', '12']
ADJ['15'] = ['10', '20']
ADJ['17'] = ['12','22']
ADJ['19'] = ['20', '24']
ADJ['20'] = ['15','19']
ADJ['21'] = ['22']
ADJ['22'] = ['17','21','23']
ADJ['23'] = ['22', '24']
ADJ['24'] = ['19','23']
print (ADJ)
def dls(start, goal):
    depth = 0
    limit = 200
    OPEN=[]
    CLOSED=[]
    OPEN.append(start)
    while OPEN != []: # Step 2
        if depth<=limit:
            current = OPEN.pop() 
            if current == goal:
                CLOSED.append(current)
                print("Goal Node Found")
                print(CLOSED)
                return True
            else:
                CLOSED.append(current)
                lst = successors(current)
                for i in lst:
                    OPEN.append(i)
                depth +=1
        else:
            print("Not found within depth limit")
            return False


    return False

def successors(city):
    return ADJ[city]

def test():
    start = 'S'
    goal = 'G'
    print("Starting a dls from " + start)
    print(dls(start, goal))


if __name__ == "__main__":
    test()

Answer 1

The issue is that you are not keeping a check of nodes already visited. For example you start from a node "S" and then go to its neighbors, you should mark it as visited and do a check while appending to the OPEN list, so that you don't try to come to it again. If you don't do it, your code will get stuck in infinite loop as you will keep on jumping between two nodes.

Further, there was some issue in the ADJ that you had created, particularly in '22'. I have tried to make minimal changes to your code(keeping the removed parts as comments), though there are several other places where it can be improved. Corrected code:

ADJ = {}
""""
SRRXG
RXRXR
RRRXR
XRXRR
RRRRX
"""
ADJ['S'] = ['2', '6']
ADJ['2'] = ['S', '3']
ADJ['3'] = ['2','8']
ADJ['G'] = ['10']
ADJ['6'] = ['S', '11']
ADJ['8'] = ['3', '13']
ADJ['10'] = ['G', '15']
ADJ['11'] = ['6', '12']
ADJ['12'] = ['11', '13', '17']
ADJ['13'] = ['8', '12']
ADJ['15'] = ['10', '20']
ADJ['17'] = ['12','22']
ADJ['19'] = ['20', '24']
ADJ['20'] = ['15','19']
ADJ['21'] = ['22']
ADJ['22'] = ['17','21','23']
ADJ['23'] = ['22', '24']
ADJ['24'] = ['19','23']
print (ADJ)
# keep track of visited nodes
visited = {str(i) : False for i in range(1,26)}
visited['S'] = False
visited['G'] = False

def dls(start, goal):
    depth = 0
    limit = 200
    OPEN=[]
    CLOSED=[]
    OPEN.append(start)
    visited["S"] = True
    while OPEN != []: # Step 2
        if depth<=limit:
            current = OPEN.pop() 
            # visited[current] = False
            if current == goal:
                # CLOSED.append(current)
                print("Goal Node Found")
                # print(CLOSED)
                return True
            else:
                # CLOSED.append(current)
                lst = successors(current)
                for i in lst:
                    # try to visit a node in future, if not already been to it
                    if(not(visited[i])):
                        OPEN.append(i)
                        visited[i] = True
                depth +=1

        else:
            print("Not found within depth limit")
            return False


    return False

Further, you can write a function to calculate ADJ given the maze very easily, instead of hard coding it.