How do you find a word in a grid of letters using backtracking?
You try every cell as the start of the word, and from each one you walk in the four directions trying to spell the word.
def exists(board, word):
rows = len(board)
cols = len(board[0])
def search(r, c, index):
if r < 0 or r >= rows or c < 0 or c >= cols:
return False
if board[r][c] != word[index]:
return False
if index == len(word) - 1:
return True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
if search(r + dr, c + dc, index + 1):
return True
return False
for r in range(rows):
for c in range(cols):
if search(r, c, 0):
return True
return False
So how does it work? The function search takes a row, a column and which letter of the word you are trying to place. It checks two things first. The square has to be on the board, and the letter on that square has to be the letter you want.
And then there are two stopping cases. If you are on the last letter of the word then you have spelled the whole thing and you give back True. Otherwise you try the four neighbouring squares and you see whether any of them carries on the word.
And the outer loops are what make it complete. You try every square as the start, so you cannot miss a word that starts somewhere in the middle of the board.
And there is one thing that this version does not handle, and it is worth knowing about. It can use the same square twice in one word. If the board has two a letters next to each other and the word is "aa", the search can go from the first a back onto itself and say yes, when the real answer is no. The fix is to mark the square while it is being used and to unmark it when you come back, which is the backtracking part.
And the complexity is O of rows times cols times four to the power of the length of the word for the time, because you try every start and every direction at every letter. And the space is O of the length of the word for the stack.
So the rule to remember is this. Try every start, walk in four directions, and mark the squares that you use.
The last question in this topic returns the path as well.