DSAverse
Backtracking
Loading Backtracking...
N-Queens Board
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Backtracking
Loading Backtracking...
N-Queens Board
Find a word in a 2D character grid by exploring all four directions from each cell. Backtracking un-marks visited cells when a path fails.
1 / 0
Matching char 1 of 4
Click Play to begin.
What does backtracking do when a grid cell doesn't match the next character of the target word?
The visited set prevents using a cell twice in one path. On backtrack, the cell is removed from the set — this is the "unchoose" step that makes other starting paths still able to use that cell.
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, idx, visited):
if idx == len(word):
return True
if (r < 0 or r >= rows or c < 0 or c >= cols
or (r, c) in visited
or board[r][c] != word[idx]):
return False
visited.add((r, c))
for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
if dfs(r+dr, c+dc, idx+1, visited):
visited.remove((r, c)) # optional cleanup
return True
visited.remove((r, c)) # backtrack
return False
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0, set()):
return True
return False