Expert · Backtracking · 236 of 264
Word search
Can the word be traced in the grid by moving between neighbouring letters (up, down, left, right), using each cell at most once?
Input: r and c, then r lines of letters, then the word. Output: yes or no
Examples
Input
3 4 ABCE SFCS ADEE ABCCED
Output
yes
Input
3 4 ABCE SFCS ADEE ABCB
Output
no
Input
1 1 A A
Output
yes
One more test checks other inputs when you press Check.
Stuck? The idea behind backtracking
Build an answer one choice at a time; when a choice leads nowhere, undo it and try the next. Recursion keeps track of where you are.
Check as early as you can whether a partial answer can still work, so dead ends are left quickly.
def subsets(items, chosen=[]):
if not items:
print(chosen)
return
subsets(items[1:], chosen + [items[0]])
subsets(items[1:], chosen)
subsets([1, 2])Watch for: Changing a shared list without undoing the change afterwards leaves the next choice with the wrong start.