# backtracking

- only enter a promising spot, so I need to :
- check before initial call
- check before every recursive/fan-out call
- check termination at the beginning of backtrack()
- add to path/visited before fanout for-loop
- remove from path/visited after fanout for-loop

def soln(grid, word):
    m = len(grid)
    n = len(grid[0])
    def inside(i, j):
        return (0 <= i < m and 0 <= j < n)

    def btrack (i, j, k):
        # Guaranteed this (i,j) matchs the letter

        # Termination: Record/return the result. Stop go further
        # If matched and already the last one -> full matched -> dump the path
        if k == len(word) - 1:
            ans_li.append(path + [(i, j)])  # Make a hard copy.
            return

        # Not yet full matched.
        # So, all guys in `path` and `visited` are always legal and promising
        path.append((i, j))
        visited.add((i, j))

        # fanout
        for newi, newj in [(i + 1, j), (i, j + 1)]:
            # only try on legal and promising spots
            if ((newi, newj) not in visited and inside(newi, newj) and
                grid[newi][newj] == word[k + 1]):  # https://google.github.io/styleguide/pyguide.html#32-line-length
                btrack(newi, newj, k + 1)

        path.pop()
        visited.remove((i, j))
        return

    ans_li = []
    path = []
    visited = set()

    for i in range(m):
        for j in range(n):
            # Always ensure btrack() is entering a promising spot
            # 1) inside: yes
            # 2) visited: no
            # 3) letter matched: yes
            if grid[i][j] == word[0]:
                btrack(i, j, 0)

    return ans_li

grid1 = [
    ['c', 'c', 't', 'n', 'a', 'x'],
    ['c', 'c', 'a', 't', 'n', 't'],
    ['a', 'c', 'n', 'n', 't', 't'],
    ['t', 'n', 'i', 'i', 'p', 'p'],
    ['a', 'o', 'o', 'o', 'a', 'a'],
    ['s', 'a', 'a', 'a', 'o', 'o'],
    ['k', 'a', 'i', 'o', 'k', 'i'],
]
word1 = "catnip"
word2 = "cccc"
word3 = "s"
word4 = "ant"
word5 = "aoi"
word6 = "ki"
word7 = "aaoo"
word8 = "ooo"
word9 = "a"



"""
find_word_location(grid1, word1) => [ (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4) ]
find_word_location(grid1, word2) =>
       [(0, 0), (1, 0), (1, 1), (2, 1)]
    OR [(0, 0), (0, 1), (1, 1), (2, 1)]
find_word_location(grid1, word3) => [(5, 0)]
find_word_location(grid1, word4) => [(0, 4), (1, 4), (2, 4)] OR [(0, 4), (1, 4), (1, 5)]
find_word_location(grid1, word5) => [(4, 5), (5, 5), (6, 5)]
find_word_location(grid1, word6) => [(6, 4), (6, 5)]
find_word_location(grid1, word7) => [(5, 2), (5, 3), (5, 4), (5, 5)]
find_word_location(grid1, word8) => [(4, 1), (4, 2), (4, 3)]
find_word_location(grid2, word9) => [(0, 0)]
"""
grid2 = [['a']]

print(soln(grid1, word1))
print(soln(grid1, word2))
print(soln(grid1, word3))
print(soln(grid1, word4))
print(soln(grid1, word5))
print(soln(grid1, word6))
print(soln(grid1, word7))
print(soln(grid1, word8))

print(soln(grid2, word9))

print(soln(grid1, word9))
print(soln(grid1, "qwert"))