Builds on Constraint Backtracking, which you haven’t finished yet.
Find One Solution and Stop (Sudoku Solver, Word Search)
Sudoku Solver (LC 37)(opens leetcode.com)
Fill in every empty cell of a 9x9 Sudoku board so the finished board is a valid solution.
A board is valid when, in every row, in every column, and in each of the nine 3x3 sub-boxes, the digits 1 through 9 each appear exactly once.
Empty cells are marked with the '.' character.
Find One Solution
empty cell ➔ try each digit ➔ return True at once, undo only after False| 1 | def solveSudoku(board: list[list[str]]) -> list[list[str]]: |
| 2 | """Sudoku Solver (LC 37): fill every "." cell so that each row, column and 3 x 3 box holds 1 to 9 once. |
| 3 | One solved board is enough, so backtrack returns True as soon as every cell is filled and the search stops. |
| 4 | E = the number of empty cells. is_valid scans 27 cells, which is a constant. |
| 5 | Time: O(9^E) | Space: O(E) recursion stack, and the board is changed in place |
| 6 | """ |
| 7 | def is_valid(r, c, ch): |
| 8 | # Check Row and Column: |
| 9 | # A digit already in this row or this column at any position |
| 10 | # would repeat, so ch is rejected if it matches either. |
| 11 | for i in range(9): |
| 12 | if board[r][i] == ch or board[i][c] == ch: |
| 13 | return False |
| 14 | |
| 15 | # Check the 3x3 Box: |
| 16 | # br, bc is the box's top-left corner; scanning its 9 cells |
| 17 | # catches a repeat the row and column checks alone would miss. |
| 18 | br = r - r % 3 |
| 19 | bc = c - c % 3 |
| 20 | for bi in range(br, br + 3): |
| 21 | for bj in range(bc, bc + 3): |
| 22 | if board[bi][bj] == ch: |
| 23 | return False |
| 24 | return True |
| 25 | |
| 26 | def backtrack(): |
| 27 | for r in range(9): |
| 28 | for c in range(9): |
| 29 | # 1. Find the Next Empty Cell: |
| 30 | # Scanning row by row finds the first "." cell still to |
| 31 | # fill; once no empty cell remains, the board is solved. |
| 32 | if board[r][c] == ".": |
| 33 | for d in "123456789": |
| 34 | # 2. Choose, Explore, Un-choose: |
| 35 | # Try digit d only if is_valid allows it; place |
| 36 | # it and recurse, keeping it only if the rest of |
| 37 | # the board can still be solved, otherwise undo |
| 38 | # and try the next digit. |
| 39 | if is_valid(r, c, d): |
| 40 | board[r][c] = d |
| 41 | if backtrack(): |
| 42 | return True |
| 43 | board[r][c] = "." |
| 44 | |
| 45 | # 3. Fail This Cell: |
| 46 | # No digit 1-9 fits here given the current board, so |
| 47 | # this whole branch is a dead end. |
| 48 | return False |
| 49 | return True |
| 50 | |
| 51 | backtrack() |
| 52 | return board |
backtrack() returns True only when every cell is filled validly, and returns False with the board exactly as it was when it was called.Make backtrack return a boolean, and return True the moment every cell is filled. Every caller writes if backtrack(): return True, so the first success is passed up through all the calls and the search stops. The undo board[r][c] = "." runs only after a call returned False, so a failed branch leaves the board as it found it. The trap is writing backtrack() alone: the value True is lost, the undo runs after the solution was found, and it erases the solved board.
See it run
Word Search (LC 79) for ABCCED: one True stops the search
idx -path -found -exist -
Each cell of the table is one cell of the grid. The replay follows the Solve problem, Word Search (LC 79), which uses the same rule as Sudoku Solver (LC 37): the first True is passed up and the other calls are skipped.
nowthe cell that the current call is working onpatha cell on the path of the current call stackrejecteda cell that fails: the wrong letter, or already on the pathrestoreda cell that just got its letter back as its call returnedskippeda neighbour that is never tried because an earlier neighbour returned True
Start: the word is ABCCED and no cell is on the path. exist tries each cell as the first letter.
Gotcha 1 of 3
- The trap
Gotcha 1: Ignoring the value that
backtrack()returnsMistakebacktrack()Fixif backtrack(): return TrueWhat happens:
backtrack()returnsTruewhen every cell is filled. If the call is written alone, that value is thrown away. The lineboard[r][c] = "."then runs and erases the digit that was just placed. Every caller above does the same on the way back, so the search takes the solved board apart and ends with the empty cells it started with.Example: A solved board with 5 cells made empty: row 0 columns 2 and 3, row 1 column 1, row 4 column 4 and row 8 column 8 (the call counts the cells that are still empty in the result)Mistake: returns 5Fix: returns 0
- Every complete board is wanted, as in N-Queens (LC 51), so the search never stops early:
backtrackreturns nothing, and the loop goes on after each board is recorded. See Constraint Backtracking - Every ordering is wanted, as in Permutations (LC 46), so there is no
Trueto pass up and the search visits the whole tree. See Permutations
Deep Dive
Why the first True stops every caller
A search that needs only one solution can end when it has one. To do that, backtrack returns a boolean. It returns True when every cell is filled, and False when no digit fits the current cell.
Every caller writes if backtrack(): return True. The first True is passed up through all the calls, one return True after another. No caller tries another digit after that.
The board above replays Word Search (LC 79), the problem of the Solve stage of this card, because a 9 x 9 Sudoku board is too large to draw. It does not replay the Sudoku code of this card. It shows the same stop-early rule on a smaller problem. The four neighbour calls are joined with or, and or stops at the first True.
For the word ABCCED, the path A, B, C, C, E, D is found at step 11. Four neighbours were rejected before that: the S at (1, 0), the F at (1, 1), the cell (1, 2) that was already on the path, and the E at (2, 3). At step 14, the cells (1, 3) and (1, 1) are never tried, because (1, 2) already returned True. At the end, the other 11 start cells are never tried either.
Why the undo runs only after False
board[r][c] = d writes a digit, and board[r][c] = "." takes it back. A failed branch must leave the board as it found it, so the next digit starts from the same board. This is the invariant of the card.
A successful branch must not be undone, because the board is the answer. The line return True comes before the undo line, so a True skips the undo.
Suppose the call is written as backtrack() alone. The True is thrown away, and the undo line runs. Take a solved board with 5 empty cells: backtrack is called 6 times and never returns False. With the mistake, the undo erases all 5 digits on the way back, and solveSudoku returns the input again, with its 5 empty cells.
A dead end is the other case. When no digit from 1 to 9 fits the cell, the call returns False. Its caller then undoes its own digit and tries the next one. For a board with 14 empty cells, backtrack is called 20 times, and 5 of those calls return False.
The cost, and what happens with no solution
Each empty cell has at most 9 digits to try, so the time is O(9^E) for E empty cells. is_valid reads 27 cells, which is a constant. The stack holds one call for each empty cell, so the space is O(E).
The bound is loose, because is_valid cuts most digits at once. On the first example of Sudoku Solver (LC 37), which has 51 empty cells, backtrack is called 4,209 times. Of those calls, 4,157 return False and 52 return True.
If the board has no solution, no call ever returns True. The search visits the whole tree and returns False. Every digit was undone on the way, so the board is exactly the board that was given.
If the question asks for every solution, this card does not apply. N-Queens (LC 51) records every board and goes on after each one.
60-Second Pitch
"I make backtrack return a boolean. It finds the first empty cell and tries the digits 1 to 9. A digit is kept only if is_valid accepts it. If the recursive call returns True, I return True at once, so the solution stays on the board. If it returns False, I write "." back and try the next digit. If no digit fits, I return False. The time is O(9^E) for E empty cells, and the stack is O(E) deep."
Common Questions
- Why does
backtrackreturn a boolean and not a list of boards? The question needs one solved board, and the board is changed in place. The boolean tells each caller whether the rest of the board could be filled. The first
Trueends the search, so there is no list to build.- Why is the undo skipped after a
True? The board that holds the solution is the answer. An undo would write
"."over a digit that belongs to the solution. Thereturn Trueline comes before the undo line, so aTrueleaves the board as it is.- What happens if the board has no solution?
No call returns
True, so the search visits the whole tree and the first call returnsFalse. Every digit was undone on the way back, so the board is the same as the input.- How is this different from N-Queens (LC 51)?
N-Queens (LC 51) asks for every board, so
backtrackreturns nothing and the loop goes on after each board is recorded. Here one board is enough, sobacktrackreturns a boolean and the firstTrueends the search.- What is the time and space complexity?
O(9^E) time for E empty cells, because each empty cell has at most 9 digits and
is_validcuts most of them at once. The space is O(E) for the recursion stack. The board is changed in place.
SWE Reasoning
Spot it
- The statement asks whether a valid arrangement exists, or asks for any one valid arrangement.
- Any valid answer is accepted, so there is no list of answers to build.
- A board or a string is filled one position at a time, and each placement can be checked at once.
- The statement says "return true if" or "fill the board in place", and not "return all".
The invariant, step by step
backtrack()scans row by row for the first empty cell. If there is none, every cell is filled, and every digit passedis_validwhen it was placed. So it returnsTrue.- Otherwise the loop tries each digit
dfrom 1 to 9 in that cell.is_validskips a digit that already appears in the row, the column or the 3 x 3 box. - For a valid digit,
board[r][c] = dwrites it, andbacktrack()fills the rest of the board. - If that call returned
True, the caller returnsTrueat once and does not undo. The board now holds the solution. - If that call returned
False, the caller writes"."back and tries the next digit. The board is the same as before step 3. - If no digit works, the call returns
Falsewith the board exactly as it was when the call started.
Traps
- Ignoring the return value.
backtrack()alone throws theTrueaway, and the undo erases the solution. For the board with 5 empty cells, the result is the input again. - Forgetting
return Falseafter the digit loop. A cell with no valid digit does not stop the call. The call goes on to the next empty cell, and it reports success while some cells are still empty. - Not putting
"."back after a digit fails. The failed digit stays in the cell, and the next scan treats the cell as filled. For the board with 14 empty cells, the result is not a valid solution. - Using this card when every solution is needed. A
Truewould stop the search at the first board, and the other boards would never be found.
Practice
Builds on Constraint Backtracking, which you haven’t finished yet.
Find One Solution and Stop (Sudoku Solver, Word Search)
Sudoku Solver (LC 37)(opens leetcode.com)
Fill in every empty cell of a 9x9 Sudoku board so the finished board is a valid solution.
A board is valid when, in every row, in every column, and in each of the nine 3x3 sub-boxes, the digits 1 through 9 each appear exactly once.
Empty cells are marked with the '.' character.
Find One Solution
empty cell ➔ try each digit ➔ return True at once, undo only after False| 1 | def solveSudoku(board: list[list[str]]) -> list[list[str]]: |
| 2 | """Sudoku Solver (LC 37): fill every "." cell so that each row, column and 3 x 3 box holds 1 to 9 once. |
| 3 | One solved board is enough, so backtrack returns True as soon as every cell is filled and the search stops. |
| 4 | E = the number of empty cells. is_valid scans 27 cells, which is a constant. |
| 5 | Time: O(9^E) | Space: O(E) recursion stack, and the board is changed in place |
| 6 | """ |
| 7 | def is_valid(r, c, ch): |
| 8 | # Check Row and Column: |
| 9 | # A digit already in this row or this column at any position |
| 10 | # would repeat, so ch is rejected if it matches either. |
| 11 | for i in range(9): |
| 12 | if board[r][i] == ch or board[i][c] == ch: |
| 13 | return False |
| 14 | |
| 15 | # Check the 3x3 Box: |
| 16 | # br, bc is the box's top-left corner; scanning its 9 cells |
| 17 | # catches a repeat the row and column checks alone would miss. |
| 18 | br = r - r % 3 |
| 19 | bc = c - c % 3 |
| 20 | for bi in range(br, br + 3): |
| 21 | for bj in range(bc, bc + 3): |
| 22 | if board[bi][bj] == ch: |
| 23 | return False |
| 24 | return True |
| 25 | |
| 26 | def backtrack(): |
| 27 | for r in range(9): |
| 28 | for c in range(9): |
| 29 | # 1. Find the Next Empty Cell: |
| 30 | # Scanning row by row finds the first "." cell still to |
| 31 | # fill; once no empty cell remains, the board is solved. |
| 32 | if board[r][c] == ".": |
| 33 | for d in "123456789": |
| 34 | # 2. Choose, Explore, Un-choose: |
| 35 | # Try digit d only if is_valid allows it; place |
| 36 | # it and recurse, keeping it only if the rest of |
| 37 | # the board can still be solved, otherwise undo |
| 38 | # and try the next digit. |
| 39 | if is_valid(r, c, d): |
| 40 | board[r][c] = d |
| 41 | if backtrack(): |
| 42 | return True |
| 43 | board[r][c] = "." |
| 44 | |
| 45 | # 3. Fail This Cell: |
| 46 | # No digit 1-9 fits here given the current board, so |
| 47 | # this whole branch is a dead end. |
| 48 | return False |
| 49 | return True |
| 50 | |
| 51 | backtrack() |
| 52 | return board |
backtrack() returns True only when every cell is filled validly, and returns False with the board exactly as it was when it was called.Make backtrack return a boolean, and return True the moment every cell is filled. Every caller writes if backtrack(): return True, so the first success is passed up through all the calls and the search stops. The undo board[r][c] = "." runs only after a call returned False, so a failed branch leaves the board as it found it. The trap is writing backtrack() alone: the value True is lost, the undo runs after the solution was found, and it erases the solved board.
See it run
Word Search (LC 79) for ABCCED: one True stops the search
idx -path -found -exist -
Each cell of the table is one cell of the grid. The replay follows the Solve problem, Word Search (LC 79), which uses the same rule as Sudoku Solver (LC 37): the first True is passed up and the other calls are skipped.
nowthe cell that the current call is working onpatha cell on the path of the current call stackrejecteda cell that fails: the wrong letter, or already on the pathrestoreda cell that just got its letter back as its call returnedskippeda neighbour that is never tried because an earlier neighbour returned True
Start: the word is ABCCED and no cell is on the path. exist tries each cell as the first letter.
Gotcha 1 of 3
- The trap
Gotcha 1: Ignoring the value that
backtrack()returnsMistakebacktrack()Fixif backtrack(): return TrueWhat happens:
backtrack()returnsTruewhen every cell is filled. If the call is written alone, that value is thrown away. The lineboard[r][c] = "."then runs and erases the digit that was just placed. Every caller above does the same on the way back, so the search takes the solved board apart and ends with the empty cells it started with.Example: A solved board with 5 cells made empty: row 0 columns 2 and 3, row 1 column 1, row 4 column 4 and row 8 column 8 (the call counts the cells that are still empty in the result)Mistake: returns 5Fix: returns 0
- Every complete board is wanted, as in N-Queens (LC 51), so the search never stops early:
backtrackreturns nothing, and the loop goes on after each board is recorded. See Constraint Backtracking - Every ordering is wanted, as in Permutations (LC 46), so there is no
Trueto pass up and the search visits the whole tree. See Permutations
Deep Dive
Why the first True stops every caller
A search that needs only one solution can end when it has one. To do that, backtrack returns a boolean. It returns True when every cell is filled, and False when no digit fits the current cell.
Every caller writes if backtrack(): return True. The first True is passed up through all the calls, one return True after another. No caller tries another digit after that.
The board above replays Word Search (LC 79), the problem of the Solve stage of this card, because a 9 x 9 Sudoku board is too large to draw. It does not replay the Sudoku code of this card. It shows the same stop-early rule on a smaller problem. The four neighbour calls are joined with or, and or stops at the first True.
For the word ABCCED, the path A, B, C, C, E, D is found at step 11. Four neighbours were rejected before that: the S at (1, 0), the F at (1, 1), the cell (1, 2) that was already on the path, and the E at (2, 3). At step 14, the cells (1, 3) and (1, 1) are never tried, because (1, 2) already returned True. At the end, the other 11 start cells are never tried either.
Why the undo runs only after False
board[r][c] = d writes a digit, and board[r][c] = "." takes it back. A failed branch must leave the board as it found it, so the next digit starts from the same board. This is the invariant of the card.
A successful branch must not be undone, because the board is the answer. The line return True comes before the undo line, so a True skips the undo.
Suppose the call is written as backtrack() alone. The True is thrown away, and the undo line runs. Take a solved board with 5 empty cells: backtrack is called 6 times and never returns False. With the mistake, the undo erases all 5 digits on the way back, and solveSudoku returns the input again, with its 5 empty cells.
A dead end is the other case. When no digit from 1 to 9 fits the cell, the call returns False. Its caller then undoes its own digit and tries the next one. For a board with 14 empty cells, backtrack is called 20 times, and 5 of those calls return False.
The cost, and what happens with no solution
Each empty cell has at most 9 digits to try, so the time is O(9^E) for E empty cells. is_valid reads 27 cells, which is a constant. The stack holds one call for each empty cell, so the space is O(E).
The bound is loose, because is_valid cuts most digits at once. On the first example of Sudoku Solver (LC 37), which has 51 empty cells, backtrack is called 4,209 times. Of those calls, 4,157 return False and 52 return True.
If the board has no solution, no call ever returns True. The search visits the whole tree and returns False. Every digit was undone on the way, so the board is exactly the board that was given.
If the question asks for every solution, this card does not apply. N-Queens (LC 51) records every board and goes on after each one.
60-Second Pitch
"I make backtrack return a boolean. It finds the first empty cell and tries the digits 1 to 9. A digit is kept only if is_valid accepts it. If the recursive call returns True, I return True at once, so the solution stays on the board. If it returns False, I write "." back and try the next digit. If no digit fits, I return False. The time is O(9^E) for E empty cells, and the stack is O(E) deep."
Common Questions
- Why does
backtrackreturn a boolean and not a list of boards? The question needs one solved board, and the board is changed in place. The boolean tells each caller whether the rest of the board could be filled. The first
Trueends the search, so there is no list to build.- Why is the undo skipped after a
True? The board that holds the solution is the answer. An undo would write
"."over a digit that belongs to the solution. Thereturn Trueline comes before the undo line, so aTrueleaves the board as it is.- What happens if the board has no solution?
No call returns
True, so the search visits the whole tree and the first call returnsFalse. Every digit was undone on the way back, so the board is the same as the input.- How is this different from N-Queens (LC 51)?
N-Queens (LC 51) asks for every board, so
backtrackreturns nothing and the loop goes on after each board is recorded. Here one board is enough, sobacktrackreturns a boolean and the firstTrueends the search.- What is the time and space complexity?
O(9^E) time for E empty cells, because each empty cell has at most 9 digits and
is_validcuts most of them at once. The space is O(E) for the recursion stack. The board is changed in place.
SWE Reasoning
Spot it
- The statement asks whether a valid arrangement exists, or asks for any one valid arrangement.
- Any valid answer is accepted, so there is no list of answers to build.
- A board or a string is filled one position at a time, and each placement can be checked at once.
- The statement says "return true if" or "fill the board in place", and not "return all".
The invariant, step by step
backtrack()scans row by row for the first empty cell. If there is none, every cell is filled, and every digit passedis_validwhen it was placed. So it returnsTrue.- Otherwise the loop tries each digit
dfrom 1 to 9 in that cell.is_validskips a digit that already appears in the row, the column or the 3 x 3 box. - For a valid digit,
board[r][c] = dwrites it, andbacktrack()fills the rest of the board. - If that call returned
True, the caller returnsTrueat once and does not undo. The board now holds the solution. - If that call returned
False, the caller writes"."back and tries the next digit. The board is the same as before step 3. - If no digit works, the call returns
Falsewith the board exactly as it was when the call started.
Traps
- Ignoring the return value.
backtrack()alone throws theTrueaway, and the undo erases the solution. For the board with 5 empty cells, the result is the input again. - Forgetting
return Falseafter the digit loop. A cell with no valid digit does not stop the call. The call goes on to the next empty cell, and it reports success while some cells are still empty. - Not putting
"."back after a digit fails. The failed digit stays in the cell, and the next scan treats the cell as filled. For the board with 14 empty cells, the result is not a valid solution. - Using this card when every solution is needed. A
Truewould stop the search at the first board, and the other boards would never be found.