Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Mark a cell only for the active path: The Word Board.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Word search backtracking matches the clues
- 2Keep this true after every move: the active path spells the matched word prefix and contains no repeated cell
- 3Reach the result within O(rows times cols times 4^wordLength)
Rules and pressure
- Target cost: O(rows times cols times 4^wordLength)
- State rule: the active path spells the matched word prefix and contains no repeated cell
Lesson 1 of 3
Live algorithm trace
Word search backtracking
Complete execution1 of 5
A
cell
B
C
C
E
D
Choose the A cell as a candidate start.
1
try each cell as start2
search(row,col,index)3
reject bounds, mismatch, or used cell4
if final character matched: succeed5
mark used and search four neighbors6
restore cell and returnword = ABCCEDstart = A
Truth to preserve / Cost target
Truth to preserve
the active path spells the matched word prefix and contains no repeated cell
Cost target
O(rows times cols times 4^wordLength)
Start from every matching cell. A recursive path advances four directions, temporarily marks its cell used, and restores it when the branch returns.
Your call · What should guide every step of this algorithm?