Builds on Permutations, which you haven’t finished yet.
Constraint Satisfaction Backtracking (N-Queens, Sudoku)
N-Queens (LC 51)(opens leetcode.com)
Placing n chess queens on an n x n board so that no two queens share a row, column, or diagonal is the classic n-queens puzzle.
Given n, return every distinct board arrangement that solves the puzzle, in any order.
Represent each solution as a list of row strings, where 'Q' marks a queen and '.' marks an empty square.
Constraint Backtracking
board coordinates ➔ validation arrays (rows, cols, diags) ➔ explore & un-mark| 1 | from typing import Callable, Iterable, List, Set, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def place_and_check(slots: int, options: Callable[[int], Iterable[Item]], is_valid: Callable[[int, Item], bool], place: Callable[[int, Item], None], unplace: Callable[[int, Item], None], record: Callable[[], None]) -> None: |
| 7 | """Constraint Backtracking: fill slots 0..slots-1 one option each, checking every option as it is placed. |
| 8 | is_valid(slot, option) reads the marks of the options already placed; place and unplace set and clear them. |
| 9 | record() is called once for every complete filling. |
| 10 | B = the calls to backtrack. I = the loop steps over all calls. S = the complete fillings recorded. |
| 11 | T = the cost of one options, is_valid, place, unplace or record call. |
| 12 | Time: O((B + I + S) * T) | Space: O(slots) recursion stack, plus the marks |
| 13 | """ |
| 14 | def backtrack(slot: int) -> None: |
| 15 | # 1. Record a Complete Filling: |
| 16 | # Every option already placed passed is_valid when it was placed, so once |
| 17 | # slot reaches slots, every slot is filled and every rule still holds. |
| 18 | if slot == slots: |
| 19 | record() |
| 20 | return |
| 21 | |
| 22 | for option in options(slot): |
| 23 | # 2. Check Before Placing: |
| 24 | # is_valid reads the marks of the options already placed; an option that |
| 25 | # breaks a rule is cut off here, before it is ever placed on the board. |
| 26 | if not is_valid(slot, option): |
| 27 | continue |
| 28 | |
| 29 | # 3. Choose, Explore, Un-choose: |
| 30 | # place marks option for slot and recurse to the next slot; unplace then |
| 31 | # clears every mark place set, so a later option can reuse the same marks. |
| 32 | place(slot, option) |
| 33 | backtrack(slot + 1) |
| 34 | unplace(slot, option) |
| 35 | |
| 36 | backtrack(0) |
0 to r - 1 each hold one queen, no two of them attack each other, and cols, diag and anti hold exactly their columns and diagonals.Place one queen per row, so backtrack(r) only chooses a column c for row r, and skip c when c, r - c or r + c is already in cols, diag or anti. Each queen is checked the moment it is placed, so a board that breaks a rule is cut off at once instead of being built and tested at the end, and one queen per row already rules out attacks along a row. The trap is the undo: after backtrack(r + 1), reset board[r][c] and remove c, r - c and r + c from the three sets, or a queen that was taken back still blocks later rows.
See it run
Constraint Backtracking on a 4 x 4 board, step by step
r 0cols {}diag {}anti {}
Each row of the table is one board row and each column is one board column. Q is a queen and . is an empty cell. The replay stops after the first board is recorded.
placethe cell where the queen is placed nowqueena queen placed earlier and still on the boardattackeda cell in this row that cols, diag or anti rules outundoa cell that was just reset to empty
Start: the 4 x 4 board is empty, cols, diag and anti are empty, and backtrack(0) begins.
Gotcha 1 of 5
- The trap
Gotcha 1: Taking a queen back without removing its marks
Mistakeboard[r][c] = "."Fixboard[r][c] = "." cols.remove(c) diag.remove(r - c) anti.remove(r + c)What happens: Placing a queen adds
c,r - candr + cto the three sets. If the undo only resetsboard[r][c], those numbers stay in the sets. A queen that is gone then still blocks its column and diagonals in later rows. So no board is ever completed.Example: n = 4 (the number of boards)Mistake: returns 0Fix: returns 2
- Each cell only has to be reached once in total, as in Flood Fill (LC 733), so nothing is undone when the search steps back. See Flood Fill
Deep Dive
Check before placing: one queen per row, three sets for the rest
Permutations already shows the used marks: a choice is marked, the call recurses, and the choice is unmarked. This card adds one rule. Each option is tested against the marks of the options already placed, before it is placed. An option that breaks a rule is skipped, and its whole branch is never built.
In N-Queens (LC 51), the slot is a row. backtrack(r) chooses a column c for row r. One queen per row already rules out two queens in a row, so only columns and diagonals need a test.
A column is identified by c. A down-right diagonal is identified by r - c, because both r and c grow by 1 along it. A down-left diagonal is identified by r + c, because r grows by 1 and c shrinks by 1. So cols, diag and anti are three sets of numbers, and each test is O(1).
Example: a queen at (0, 0) has r - c = 0, and so does (1, 1). A queen at (0, 3) has r + c = 3, and so do (1, 2), (2, 1) and (3, 0). For n = 4, there are 24 ways to put one queen in each row and column. The search places only 16 queens in total and finds 2 boards.
One trace: dead rows and the undo, for n = 4
The board replays solveNQueens(4) until the first board is recorded. The answer for n = 4 is 2 boards. The first one is [".Q..","...Q","Q...","..Q."], and it has queens in columns 1, 3, 0, 2.
The search places (0, 0). In row 1, columns 0 and 1 are attacked, so (1, 2) is placed. In row 2, all four columns are attacked: columns 0 and 2 by cols, column 1 by anti, and column 3 by diag. The call returns, and the undo of (1, 2) removes 2, -1 and 3 from the three sets. This is the step marked as the trap on the board.
Row 1 then takes (1, 3), and row 2 takes (2, 1). In row 3, all four columns are attacked, so the search undoes (2, 1), then (1, 3), then (0, 0). Row 0 moves on to (0, 1). Rows 1, 2 and 3 take columns 3, 0 and 2, r reaches 4, and the first board is recorded.
That is 8 placed queens, 4 undos and 2 dead rows before the first board. The full search for n = 4 places 16 queens in 17 calls of backtrack. It finds the second board ["..Q.","Q...","...Q",".Q.."] after the first.
The undo must reverse every mark that the placement made
A placement writes four things: board[r][c], cols, diag and anti. The undo must write all four back, in any order. Then the state after backtrack(r + 1) is exactly the state before place, so the next column in the loop sees the marks of the queens above row r and nothing else.
A mark that stays is a queen that no longer exists but still blocks. For n = 4, an undo that resets only board[r][c] finds 0 boards instead of 2.
The sets use remove, not discard. If the code is correct, each undo removes a number the matching placement added. A KeyError is an early sign of a bug, such as a test that checks only diag. Then two queens share a down-left diagonal, anti holds the number once, and the second remove fails.
A saved board must be a copy. results.append(["".join(row) for row in board]) builds new strings. Saving board itself stores the list that the undo steps later empty.
Example: for n = 1, the board is [["Q"]] at record time. With results.append(board), the result is [[['.']]] after the undo.
The cost: placements times the cost of one test, and what changes for other puzzles
The card's complexity line is O((B + I + S) * T). B is the number of backtrack calls, I is the number of loop steps, S is the number of complete boards, and T is the cost of one option test, placement or undo. In N-Queens, each of them is O(1) except the copy of a board, so the search time is bounded by O(N!).
The bound is loose. Row r has at most N - r free columns, which gives N! at most. The tests cut far more. For n = 8, 2,056 queens are placed in 2,057 calls, and 92 boards are found. There are 8! = 40,320 ways to put one queen in each row and column.
The board takes O(N^2) space. The three sets and the recursion stack take O(N), and the saved boards are not counted.
Other puzzles use the same loop. N-Queens II (LC 52) asks only for the number of boards, so record adds 1 and no board is copied. Sudoku Solver (LC 37) needs one solved board, so backtrack returns True when the board is full, and the caller must return at once without undoing. Word Search (LC 79) marks a cell before it goes deeper and clears the mark after, so one path cannot reuse a cell.
Example: the same template with the slot as a position in a string and the options ( and ) gives Generate Parentheses (LC 22). The test is that a ) needs an open ( before it.
60-Second Pitch
"I put one queen in each row, so backtrack(r) chooses only a column c for row r. A column is c, a down-right diagonal is r - c, and a down-left diagonal is r + c. I keep each in a set, so a test is O(1). Before I place a queen, I test c, r - c and r + c. If one is taken, I skip that column, and the branch is never built. When r reaches n, I save a copy of the board. After the recursive call, I reset the cell and remove all three numbers. That keeps the marks exact for the next column. The time is bounded by O(N!), and in practice far less. For n = 8, the search places 2,056 queens and finds 92 boards. The space is O(N^2) for the board and O(N) for the sets and the stack."
Common Questions
- Why do
r - candr + cidentify the diagonals? Moving down-right adds 1 to both
randc, sor - cdoes not change. Moving down-left adds 1 torand subtracts 1 fromc, sor + cdoes not change. Two cells are on the same diagonal exactly when they have the same value.- Why does the code test an option before it places it?
A bad option is then cut off at once, and no deeper call is made for it. If the code tested only complete boards, it would build every filling first. For
n = 8, the early test places 2,056 queens, and one queen per row with no early test gives 8^8 = 16,777,216 fillings to check.- How do you change this to count boards, as in N-Queens II (LC 52)?
Replace the copy of the board with
count += 1. The three sets already carry all the information needed for the test, soboardis not needed at all. This saves the O(N^2) copy per board.- What changes for Sudoku Solver (LC 37)?
The slot is the next empty cell, the options are the digits 1 to 9, and the marks are a set for each row, column and box. The question asks for one solution, so
backtrackreturnsTruewhen the board is full, and every caller returnsTrueat once without undoing.- How can the three sets be made faster?
Store each set as the bits of one integer, so a test is one bitwise operation, and a placement sets three bits. The search still places the same queens. Only the constant factor drops. Say that in an interview after the sets version works.
SWE Reasoning
Spot it
- A board or a string is filled one position at a time, and each position takes one value from a small set.
- A rule links a new value to the values already placed: no two queens attack, no repeated digit in a row, no
)without an open(. - A rule can be tested the moment a value is placed, so a bad value is known at once.
- The question asks for every valid filling, the number of them, or one valid filling.
- On a board of cells, a path must not use the same cell twice, as in Word Search (LC 79).
The invariant, step by step
backtrack(r)is called when rows0tor - 1each hold one queen, and no two of them attack each other.cols,diagandantihold exactly the columns and the two kinds of diagonals of those queens.- If
r == n, allnrows have a queen and every queen passed the test when it was placed. The call records a copy of the board. - Otherwise the loop tries each column
c. Ifc,r - corr + cis in its set, a placed queen attacks the cell, and the loop continues with the next column. - If the cell is free, the code sets
board[r][c]and addsc,r - candr + cto the sets. The invariant now holds forr + 1, andbacktrack(r + 1)runs. - After the call, the code resets
board[r][c]and removes the three numbers. The state is again as it was before the placement, so the next column starts from the same marks.
Traps
- An undo that skips the sets. A queen that was taken back still blocks its column and diagonals. For
n = 4, the result is 0 boards instead of 2. - A test of only one diagonal. Two queens can share a down-left diagonal. The set
antiholds the number once, and the secondremoveraisesKeyError. - Saving
boarditself. The undo steps empty the saved board. Save a copy of the rows as strings. - Testing after the whole board is built. The search then builds every filling before it rejects one. Test each option before
place. - Ignoring the return value in Sudoku Solver (LC 37). The full board returns
True. If the caller does not stop, the undo clears the last cell and the solution is lost.
Practice
Builds on Permutations, which you haven’t finished yet.
Constraint Satisfaction Backtracking (N-Queens, Sudoku)
N-Queens (LC 51)(opens leetcode.com)
Placing n chess queens on an n x n board so that no two queens share a row, column, or diagonal is the classic n-queens puzzle.
Given n, return every distinct board arrangement that solves the puzzle, in any order.
Represent each solution as a list of row strings, where 'Q' marks a queen and '.' marks an empty square.
Constraint Backtracking
board coordinates ➔ validation arrays (rows, cols, diags) ➔ explore & un-mark| 1 | from typing import Callable, Iterable, List, Set, TypeVar |
| 2 | |
| 3 | Item = TypeVar("Item") |
| 4 | |
| 5 | |
| 6 | def place_and_check(slots: int, options: Callable[[int], Iterable[Item]], is_valid: Callable[[int, Item], bool], place: Callable[[int, Item], None], unplace: Callable[[int, Item], None], record: Callable[[], None]) -> None: |
| 7 | """Constraint Backtracking: fill slots 0..slots-1 one option each, checking every option as it is placed. |
| 8 | is_valid(slot, option) reads the marks of the options already placed; place and unplace set and clear them. |
| 9 | record() is called once for every complete filling. |
| 10 | B = the calls to backtrack. I = the loop steps over all calls. S = the complete fillings recorded. |
| 11 | T = the cost of one options, is_valid, place, unplace or record call. |
| 12 | Time: O((B + I + S) * T) | Space: O(slots) recursion stack, plus the marks |
| 13 | """ |
| 14 | def backtrack(slot: int) -> None: |
| 15 | # 1. Record a Complete Filling: |
| 16 | # Every option already placed passed is_valid when it was placed, so once |
| 17 | # slot reaches slots, every slot is filled and every rule still holds. |
| 18 | if slot == slots: |
| 19 | record() |
| 20 | return |
| 21 | |
| 22 | for option in options(slot): |
| 23 | # 2. Check Before Placing: |
| 24 | # is_valid reads the marks of the options already placed; an option that |
| 25 | # breaks a rule is cut off here, before it is ever placed on the board. |
| 26 | if not is_valid(slot, option): |
| 27 | continue |
| 28 | |
| 29 | # 3. Choose, Explore, Un-choose: |
| 30 | # place marks option for slot and recurse to the next slot; unplace then |
| 31 | # clears every mark place set, so a later option can reuse the same marks. |
| 32 | place(slot, option) |
| 33 | backtrack(slot + 1) |
| 34 | unplace(slot, option) |
| 35 | |
| 36 | backtrack(0) |
0 to r - 1 each hold one queen, no two of them attack each other, and cols, diag and anti hold exactly their columns and diagonals.Place one queen per row, so backtrack(r) only chooses a column c for row r, and skip c when c, r - c or r + c is already in cols, diag or anti. Each queen is checked the moment it is placed, so a board that breaks a rule is cut off at once instead of being built and tested at the end, and one queen per row already rules out attacks along a row. The trap is the undo: after backtrack(r + 1), reset board[r][c] and remove c, r - c and r + c from the three sets, or a queen that was taken back still blocks later rows.
See it run
Constraint Backtracking on a 4 x 4 board, step by step
r 0cols {}diag {}anti {}
Each row of the table is one board row and each column is one board column. Q is a queen and . is an empty cell. The replay stops after the first board is recorded.
placethe cell where the queen is placed nowqueena queen placed earlier and still on the boardattackeda cell in this row that cols, diag or anti rules outundoa cell that was just reset to empty
Start: the 4 x 4 board is empty, cols, diag and anti are empty, and backtrack(0) begins.
Gotcha 1 of 5
- The trap
Gotcha 1: Taking a queen back without removing its marks
Mistakeboard[r][c] = "."Fixboard[r][c] = "." cols.remove(c) diag.remove(r - c) anti.remove(r + c)What happens: Placing a queen adds
c,r - candr + cto the three sets. If the undo only resetsboard[r][c], those numbers stay in the sets. A queen that is gone then still blocks its column and diagonals in later rows. So no board is ever completed.Example: n = 4 (the number of boards)Mistake: returns 0Fix: returns 2
- Each cell only has to be reached once in total, as in Flood Fill (LC 733), so nothing is undone when the search steps back. See Flood Fill
Deep Dive
Check before placing: one queen per row, three sets for the rest
Permutations already shows the used marks: a choice is marked, the call recurses, and the choice is unmarked. This card adds one rule. Each option is tested against the marks of the options already placed, before it is placed. An option that breaks a rule is skipped, and its whole branch is never built.
In N-Queens (LC 51), the slot is a row. backtrack(r) chooses a column c for row r. One queen per row already rules out two queens in a row, so only columns and diagonals need a test.
A column is identified by c. A down-right diagonal is identified by r - c, because both r and c grow by 1 along it. A down-left diagonal is identified by r + c, because r grows by 1 and c shrinks by 1. So cols, diag and anti are three sets of numbers, and each test is O(1).
Example: a queen at (0, 0) has r - c = 0, and so does (1, 1). A queen at (0, 3) has r + c = 3, and so do (1, 2), (2, 1) and (3, 0). For n = 4, there are 24 ways to put one queen in each row and column. The search places only 16 queens in total and finds 2 boards.
One trace: dead rows and the undo, for n = 4
The board replays solveNQueens(4) until the first board is recorded. The answer for n = 4 is 2 boards. The first one is [".Q..","...Q","Q...","..Q."], and it has queens in columns 1, 3, 0, 2.
The search places (0, 0). In row 1, columns 0 and 1 are attacked, so (1, 2) is placed. In row 2, all four columns are attacked: columns 0 and 2 by cols, column 1 by anti, and column 3 by diag. The call returns, and the undo of (1, 2) removes 2, -1 and 3 from the three sets. This is the step marked as the trap on the board.
Row 1 then takes (1, 3), and row 2 takes (2, 1). In row 3, all four columns are attacked, so the search undoes (2, 1), then (1, 3), then (0, 0). Row 0 moves on to (0, 1). Rows 1, 2 and 3 take columns 3, 0 and 2, r reaches 4, and the first board is recorded.
That is 8 placed queens, 4 undos and 2 dead rows before the first board. The full search for n = 4 places 16 queens in 17 calls of backtrack. It finds the second board ["..Q.","Q...","...Q",".Q.."] after the first.
The undo must reverse every mark that the placement made
A placement writes four things: board[r][c], cols, diag and anti. The undo must write all four back, in any order. Then the state after backtrack(r + 1) is exactly the state before place, so the next column in the loop sees the marks of the queens above row r and nothing else.
A mark that stays is a queen that no longer exists but still blocks. For n = 4, an undo that resets only board[r][c] finds 0 boards instead of 2.
The sets use remove, not discard. If the code is correct, each undo removes a number the matching placement added. A KeyError is an early sign of a bug, such as a test that checks only diag. Then two queens share a down-left diagonal, anti holds the number once, and the second remove fails.
A saved board must be a copy. results.append(["".join(row) for row in board]) builds new strings. Saving board itself stores the list that the undo steps later empty.
Example: for n = 1, the board is [["Q"]] at record time. With results.append(board), the result is [[['.']]] after the undo.
The cost: placements times the cost of one test, and what changes for other puzzles
The card's complexity line is O((B + I + S) * T). B is the number of backtrack calls, I is the number of loop steps, S is the number of complete boards, and T is the cost of one option test, placement or undo. In N-Queens, each of them is O(1) except the copy of a board, so the search time is bounded by O(N!).
The bound is loose. Row r has at most N - r free columns, which gives N! at most. The tests cut far more. For n = 8, 2,056 queens are placed in 2,057 calls, and 92 boards are found. There are 8! = 40,320 ways to put one queen in each row and column.
The board takes O(N^2) space. The three sets and the recursion stack take O(N), and the saved boards are not counted.
Other puzzles use the same loop. N-Queens II (LC 52) asks only for the number of boards, so record adds 1 and no board is copied. Sudoku Solver (LC 37) needs one solved board, so backtrack returns True when the board is full, and the caller must return at once without undoing. Word Search (LC 79) marks a cell before it goes deeper and clears the mark after, so one path cannot reuse a cell.
Example: the same template with the slot as a position in a string and the options ( and ) gives Generate Parentheses (LC 22). The test is that a ) needs an open ( before it.
60-Second Pitch
"I put one queen in each row, so backtrack(r) chooses only a column c for row r. A column is c, a down-right diagonal is r - c, and a down-left diagonal is r + c. I keep each in a set, so a test is O(1). Before I place a queen, I test c, r - c and r + c. If one is taken, I skip that column, and the branch is never built. When r reaches n, I save a copy of the board. After the recursive call, I reset the cell and remove all three numbers. That keeps the marks exact for the next column. The time is bounded by O(N!), and in practice far less. For n = 8, the search places 2,056 queens and finds 92 boards. The space is O(N^2) for the board and O(N) for the sets and the stack."
Common Questions
- Why do
r - candr + cidentify the diagonals? Moving down-right adds 1 to both
randc, sor - cdoes not change. Moving down-left adds 1 torand subtracts 1 fromc, sor + cdoes not change. Two cells are on the same diagonal exactly when they have the same value.- Why does the code test an option before it places it?
A bad option is then cut off at once, and no deeper call is made for it. If the code tested only complete boards, it would build every filling first. For
n = 8, the early test places 2,056 queens, and one queen per row with no early test gives 8^8 = 16,777,216 fillings to check.- How do you change this to count boards, as in N-Queens II (LC 52)?
Replace the copy of the board with
count += 1. The three sets already carry all the information needed for the test, soboardis not needed at all. This saves the O(N^2) copy per board.- What changes for Sudoku Solver (LC 37)?
The slot is the next empty cell, the options are the digits 1 to 9, and the marks are a set for each row, column and box. The question asks for one solution, so
backtrackreturnsTruewhen the board is full, and every caller returnsTrueat once without undoing.- How can the three sets be made faster?
Store each set as the bits of one integer, so a test is one bitwise operation, and a placement sets three bits. The search still places the same queens. Only the constant factor drops. Say that in an interview after the sets version works.
SWE Reasoning
Spot it
- A board or a string is filled one position at a time, and each position takes one value from a small set.
- A rule links a new value to the values already placed: no two queens attack, no repeated digit in a row, no
)without an open(. - A rule can be tested the moment a value is placed, so a bad value is known at once.
- The question asks for every valid filling, the number of them, or one valid filling.
- On a board of cells, a path must not use the same cell twice, as in Word Search (LC 79).
The invariant, step by step
backtrack(r)is called when rows0tor - 1each hold one queen, and no two of them attack each other.cols,diagandantihold exactly the columns and the two kinds of diagonals of those queens.- If
r == n, allnrows have a queen and every queen passed the test when it was placed. The call records a copy of the board. - Otherwise the loop tries each column
c. Ifc,r - corr + cis in its set, a placed queen attacks the cell, and the loop continues with the next column. - If the cell is free, the code sets
board[r][c]and addsc,r - candr + cto the sets. The invariant now holds forr + 1, andbacktrack(r + 1)runs. - After the call, the code resets
board[r][c]and removes the three numbers. The state is again as it was before the placement, so the next column starts from the same marks.
Traps
- An undo that skips the sets. A queen that was taken back still blocks its column and diagonals. For
n = 4, the result is 0 boards instead of 2. - A test of only one diagonal. Two queens can share a down-left diagonal. The set
antiholds the number once, and the secondremoveraisesKeyError. - Saving
boarditself. The undo steps empty the saved board. Save a copy of the rows as strings. - Testing after the whole board is built. The search then builds every filling before it rejects one. Test each option before
place. - Ignoring the return value in Sudoku Solver (LC 37). The full board returns
True. If the caller does not stop, the undo clears the last cell and the solution is lost.