Word Search, traced one call at a time

Each call dfs(i, j, k) stands on one cell that already matches word[k]. It marks that cell # so the path can't loop back, tries the four neighbours for word[k + 1], and puts the letter back when it backtracks.

Fixed

Your base case was if k == len(word):. k is the index of the letter the current cell matches, so it stops at len(word) - 1 and that test is never true. On the last letter the loop then reads word[k + 1] and raises IndexError, so the original crashes exactly when the word is on the board. All three versions here use if k == len(word) - 1:. The changed line is marked with a red dot.

CALL

1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Board

Row numbers on the left, column numbers on top

current cell on the path, set to # neighbour being checked outside the board word found

Call stack

Top frame runs; the rest are paused

Recursion tree

Hover a call to find its cell

not called yet running now paused, waiting on a child returned False returned True

Keyboard: ← → step, Space play or pause. Boards up to 6×6, words up to 12 letters. Letters are case-sensitive.