find_string_in_maze.py

arr = [
    ['k','l','n','m','d'],
    ['x','m','b','c','d'],
    ['r','a','r','y','x'],
    ['y','i','o','o','d'],
    ['m','s','g','p','t']
]
arrLen = len(arr)
s = "maryis"

covered = [[0 for j in range(arrLen)] for i in range(arrLen)]

def isNotCovered(i,j):
    if (i >= 0) and (i < arrLen) and (j >= 0) and (j < arrLen):
        if covered[i][j] == 0:
            covered[i][j] = 1
            return arr[i][j]

def left(i,j): return isNotCovered(i,j-1)
def right(i,j): return isNotCovered(i,j+1)
def top(i,j): return isNotCovered(i-1,j)
def bottom(i,j):return isNotCovered(i+1,j)

def adjecent_cell(other, path, pre_state):
    print(other,path,pre_state)
    new_loc = None

    if other == '':
        print('SUCCESS')
        print(path)
        exit(0)
    
    (x,y) = path[-1]

    if(left(x,y) == other[0]):
        print('Going Left',(x,y))
        new_loc = (x,y-1)
    elif(right(x,y) == other[0]):
        print('Going Right',(x,y))
        new_loc = (x,y+1)
    elif(top(x,y) == other[0]):
        print('Going Top',(x,y))
        new_loc = (x-1,y)
    elif(bottom(x,y) == other[0]):
        print('Going Bottom',(x,y))
        new_loc = (x+1,y)
    
    if new_loc != None:
        new_path = path + [new_loc]
        new_state = pre_state + [other]
        adjecent_cell(other[1:],new_path, new_state)
    elif len(path) > 1:
        new_path = path[:-1]
        new_state = pre_state[:-1]
        adjecent_cell(pre_state[-1],new_path,new_state)

for i in range(arrLen):
    for j in range(arrLen):
        if arr[i][j] == s[0]:
            adjecent_cell(s[1:],[(i,j)],[s])