Samile maze using IDS | Python Code

 

adj={

    'S':['A','B','D','E'],

    'A':['S'],

    'B':['S','C','D'],

    'C':['B','J'],

    'D':['B','G','S'],

    'E':['G','S'],

    'F':['G','H'],

    'G':['D','E','F','J','H'],

    'H':['G','F','I'],

    'I':['H','J'],

    'J':['I','C','G']

}

def dls(start,end,limit):

    vis=set()

    vis.add(start)

    stack=[(start,[start],0)]

    while stack:

        node,path,depth=stack.pop()

        if(node==end):

            return path

        if depth>=limit:

            continue

        for child in adj[node]:

            if child not in vis:

                vis.add(child)

                stack.append((child,path+[child],depth+1))

def ids(start,end):

    max_depth=100

    for x in range(max_depth+1):

        if dls(start,end,x) is not None:

            return dls(start,end,x)

    return None

start="S"

end="I"

print("BFS solution : ")

print(ids(start,end))