cf.completefrontend
RECURSION & BACKTRACKING · ADVANCED

Backtracking with constraints

Fill slots one at a time while keeping quick lookups of which choices are still allowed, so broken partial answers are cut off at once.

Time O(n!)Space O(n)5 practice problemsStep-through picture

The idea

Some puzzles have many rules at once. Sudoku: each row, column, and box needs different digits. The queens puzzle: place n chess queens on an n × n board so that no two share a row, a column, or a diagonal.

Constraint backtracking fills one slot at a time, like plain backtracking. The key extra is a set of lookups that say, in one step, whether a choice breaks a rule. For queens, three sets remember which columns and which diagonals are already taken. Checking a square becomes three Set.has calls instead of scanning the board.

When a slot has no allowed choice, the search goes back to the slot before and tries its next choice. The rules cut off huge parts of the search, so puzzles with an enormous number of raw options finish quickly.

An everyday example

Seating wedding guests with a list of rules

You seat guests table by table. Some guests can't sit together, and each table needs a mix. You keep a sheet: which seats are taken, and who is already at each table. Before seating someone, you glance at the sheet instead of walking around the room. If a table has no one left who fits, you go back to the previous table, move one guest, and try again. Each time you seat or move someone, you update the sheet.

How the example maps to the code
In the exampleIn the code
The sheet of who sits whereThe sets cols, diagonals, antiDiagonals
Glancing at the sheet before seating someonecols.has(col) || ...
Seating a guest and noting itcols.add(col) and the other add calls
Moving a guest away againcols.delete(col) and the other delete calls
Every table is fullrow === n

From the slow way to backtracking with constraints

  1. Start with the slow way to count queen layouts: put n queens on any n of the n × n squares, then check every pair of queens for a clash. On a normal 8 × 8 board there are over 4 billion ways to pick 8 squares. Nearly all of them have two queens in the same row, which you could see at a glance.
  2. Use the first rule to shape the search. Two queens in one row always clash, so a valid layout has exactly one queen per row. Now a layout is just a column for each row: 8^8 is 16,777,216 choices for n = 8. Rows can never clash, but columns and diagonals still have to be checked at the end.
  3. Use the rules again, but earlier. If the queens in rows 0 and 1 already clash, no choice for rows 2 to 7 can fix that. So place rows one at a time and reject a column as soon as it clashes with the queens above it. This is backtracking, and for n = 8 it places only 2,056 queens to find all 92 layouts.
  4. The last cost is the check itself. Comparing a new queen with every queen above it takes up to n steps. Instead, remember what is already taken: a cols set, a diagonals set of row - col, and an antiDiagonals set of row + col. A check becomes three has calls. Add the three marks when placing, delete them when lifting. That loop is backtracking with constraints.

How it works

  1. Decide the order of slots. For queens, place one queen per row, from row 0 to row n - 1.
  2. Keep lookups of what is taken: cols for columns, diagonals for row - col, and antiDiagonals for row + col.
  3. In placeRow(row), if row === n, every queen is placed: count it and return.
  4. Otherwise try each col. Skip it if its column or either diagonal is already taken.
  5. Place the queen: add col, row - col, and row + col to the three sets.
  6. Call placeRow(row + 1) to fill the next row.
  7. Remove the three entries again, so the next col sees the board as it was.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function countQueenLayouts(n) {
  2. const cols = new Set();
  3. const diagonals = new Set();
  4. const antiDiagonals = new Set();
  5. let count = 0;
  6. function placeRow(row) {
  7. if (row === n) {
  8. count++;
  9. return;
  10. }
  11. for (let col = 0; col < n; col++) {
  12. if (cols.has(col) || diagonals.has(row - col) || antiDiagonals.has(row + col)) continue;
  13. cols.add(col);
  14. diagonals.add(row - col);
  15. antiDiagonals.add(row + col);
  16. placeRow(row + 1);
  17. cols.delete(col);
  18. diagonals.delete(row - col);
  19. antiDiagonals.delete(row + col);
  20. }
  21. }
  22. placeRow(0);
  23. return count;
  24. }

How fast it is

TimeO(n!)
Extra memoryO(n)

Row 0 has n options, row 1 at most n - 1 free columns, and so on, so there are at most about n! placements. The diagonal checks cut far more in practice. The sets and the call chain hold at most n entries.

  • Best caseO(n!)

    Counting all layouts must try every branch the rules allow, so there is no lucky input for a given n. Small boards are tiny: n = 3 needs just 5 placements to prove the answer is 0.

  • Average caseO(n!)

    In practice far below the bound, because diagonals cut most branches. For n = 8, the search places 2,056 queens, while 8! is 40,320.

  • Worst caseO(n!)

    The bound comes from columns alone: n choices in row 0, at most n - 1 free columns in row 1, and so on. For n = 12, the search places 856,188 queens to count 14,200 layouts.

Common mistakes

  • Checking a placement by scanning all earlier queens. It works, but each check costs O(n) instead of O(1).
  • Undoing only one of the three marks. The board slowly fills with ghost queens, and valid layouts are missed.
  • Mixing up the diagonal formulas. row - col can be negative, which is fine in a Set, but if you use an array you must add n - 1 to it first.
  • Trying to place queens square by square instead of row by row. The search gets much larger for no benefit.

When to use it

Look for these clues in a problem:

  • The puzzle has several rules that must all hold at once, such as Sudoku, queens, map coloring, or scheduling.
  • You fill a fixed list of slots (rows, cells, nodes, time slots), each with one value.
  • Checking a rule by scanning the whole board would be slow, but a set or array can remember what is taken.
  • The question asks for one valid filling, every valid filling, or how many there are.

Check yourself

Answer each one in your head first, then open it.

How many queens does countQueenLayouts(3) place, and what does it return?

It places 5 queens and returns 0. Every branch reaches a row where all columns clash.

Why do the squares (2, 1) and (3, 2) share a diagonal?

Both have row - col = 1. Moving one step down and one step right adds 1 to both row and col, so their difference stays the same.

What happens on a 4 × 4 board if you forget antiDiagonals.delete(row + col)?

Old anti-diagonal marks stay behind after their queens are lifted, so later squares are wrongly blocked. The function returns 0 instead of 2.

Why does n = 0 return 1?

The first call has row === n, so it counts one layout: the empty board, where no two queens clash because there are none.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule, at every call of placeRow(row): rows 0 to row - 1 each hold one queen, no two of them clash, and the three sets hold exactly those queens' col, row - col, and row + col. It is true at the start, with no queens and empty sets. A queen is placed only when all three of its marks are free, so it clashes with none of the queens above. The three delete calls after the deeper call put the sets back.

The marks are exact. Two squares are on the same down-right diagonal exactly when row - col is equal for both, and on the same down-left diagonal exactly when row + col is equal. So has on the sets answers "does this square clash with any queen above?" correctly, with no false alarms and no misses.

So the count is right. When row === n, there is one queen in every row and none clash, so each counted layout is valid. Every valid layout is counted: at each row, its column doesn't clash with its own queens above, so the loop reaches that column and places it. Two different layouts differ at some first row, so they are counted on different branches. The depth is at most n, so the search ends.

Going deeper

3 more ideas

Why row - col and row + col name the diagonals

Along a diagonal going down to the right, both row and col grow by 1 each step, so row - col stays the same. Along a diagonal going down to the left, row grows and col shrinks, so row + col stays the same. So every square on one diagonal shares one number, and a Set of those numbers tells you in one step if a diagonal is taken.

Why the rules make it fast

Placing 8 queens anywhere on 64 squares has over 4 billion options. One queen per row cuts that to 8^8, about 16 million. Checking columns and diagonals while placing cuts it to a few thousand placements. The earlier a rule can reject a partial answer, the more of the search disappears.

Choosing a good order of slots

In puzzles like Sudoku, fill the slot with the fewest allowed values first. If an empty cell has only one possible digit, place it now. If a cell has none, the current path is already broken and you can step back immediately. This order often cuts the search by a huge amount.

Work it by hand

Every step in a table, with why

Count the queen layouts on a 3 × 3 board. There are none, so the trace shows every dead end. Each row is one queen placed or one row that runs out of columns.

n = 3

Steprowcol triedcolsdiagonalsantiDiagonalsWhat happensWhy
100{0}{0}{0}place, go to row 1The board is empty, so column 0 is free. Its marks are column 0, 0 - 0 = 0, and 0 + 0 = 0.
210, 1, 2{0, 2}{0, -1}{0, 3}skip 0 and 1, place 2Column 0 is taken. Column 1 has 1 - 1 = 0, a taken diagonal. Column 2 is free, so a queen goes there.
320, 1, 2{0, 2}{0, -1}{0, 3}all clash: returnColumn 0 is taken, column 1 has 2 + 1 = 3, a taken anti-diagonal, and column 2 is taken. Row 2 has no place, so this call returns.
412{0}{0}{0}lift, loop endsBack in row 1, its queen at column 2 is lifted and its three marks deleted. Row 1 has no columns left to try.
500{}{}{}liftRow 0's queen at column 0 is lifted too. The board is empty again.
601{1}{-1}{1}place, go to row 1Now try the middle column in row 0.
710, 1, 2{1}{-1}{1}all clash: returnColumn 0 has 1 + 0 = 1, column 1 is taken, and column 2 has 1 - 2 = -1. A middle queen attacks every square of row 1.
802{2}{-2}{2}lift 1, place 2Lift the middle queen and try the last column of row 0.
910{2, 0}{-2, 1}{2, 1}place, go to row 2Column 0 in row 1 is free: column 0, 1 - 0 = 1, and 1 + 0 = 1 are all unused.
1020, 1, 2{2, 0}{-2, 1}{2, 1}all clash: returnColumn 0 is taken, column 1 has 2 - 1 = 1, and column 2 is taken. Another dead end in the last row.
1111, 2{2}{-2}{2}lift 0, skip 1 and 2Row 1 lifts its queen and tries the rest: column 1 has 1 + 1 = 2, a taken anti-diagonal, and column 2 is taken. Then row 0 lifts its queen and its loop ends.

countQueenLayouts(3) returns 0 after only 5 placements. Every branch hit a row with no free column, so row === n was never reached. The search ends when row 0 has tried all three columns.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Backtracking with constraintsO(n!)O(n)Many rules must hold at once and each can be checked with a quick lookup. The rules cut most branches early.
Scan earlier queens to checkO(n · n!)O(n)Fine for a first version or very small boards. Each check walks over the queens above, costing up to n steps.
Every column order, then check diagonalsO(n · n!)O(n)Rarely. It builds every full order of columns before checking diagonals, so it can't cut a branch early.
Bitmask backtrackingO(n!)O(n)You need speed for larger boards. Same search, but each check and update is a few bit operations.

Extra memory: O(n): each set holds at most n marks, and the call chain is at most n + 1 calls deep.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Backtracking with constraints and the other approaches, on a scale where each line up is 10 times more steps.
  • Backtracking with constraints, Bitmask backtracking O(n!)
  • Scan earlier queens to check O(n · n!)
  • Every column order, then check diagonals O(n · n!)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Backtracking with constraints4 millionmore than a quadrillionmore than a quadrillion
Scan earlier queens to check36 millionmore than a quadrillionmore than a quadrillion
Every column order, then check diagonals36 millionmore than a quadrillionmore than a quadrillion
Bitmask backtracking4 millionmore than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
n = 0
row === n is true on the first call, so it counts 1: an empty board has one layout, with no queens. If the problem wants 0 for this case, check it before the search.
n = 1
One queen on one square: placed, then row === 1 counts it. The answer is 1.
n = 2 and n = 3
Both return 0. Every way of placing the second or third queen clashes, as the trace shows for n = 3.
Negative diagonal numbers, such as row - col = -2
A Set stores -2 like any other number. If you switch to an array of true/false values for speed, add n - 1 to row - col so the index starts at 0.
Bigger boards, n = 12 and up
The count grows fast: n = 12 takes 856,188 placements, and each step up multiplies the work several times. Use bitmasks and board symmetry, covered below, before going higher.

Variations and follow-ups

Twists interviewers add

Stop at the first layout

Return true from placeRow when row === n, and stop the loop when a deeper call returns true. For n = 8, the first layout, columns [0, 4, 7, 5, 2, 6, 1, 3], is found after 113 placements. Keep the columns in an array so you can print the board.

Bitmasks instead of sets

Store cols, diagonals, and antiDiagonals as the bits of three numbers, shifting the diagonal masks by one bit per row. The free columns are the bits that are 0 in all three, and free & -free picks one in a single step. This is the fastest common way to count layouts.

Sudoku and other puzzles

Keep one set per row, per column, and per 3 × 3 box for the digits already used. Fill the empty cell with the fewest allowed digits first: a cell with one option is forced, and a cell with none means the current path is already broken.

Using symmetry

Every layout has a mirror image across the middle column. Only try row-0 columns in the left half, double the count, and handle the middle column once when n is odd. This halves the work.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "place n things so that no two ...", or from puzzles with several rules at once, like Sudoku, map coloring, or seating with conflicts.
  • Explain the two shapes of saving work: one queen per row removes the row rule, and the three sets turn each check into O(1). Then explain why row - col and row + col name the diagonals.
  • Test n = 1 (answer 1), n = 2 and n = 3 (answer 0), and n = 4 (answer 2). Those four values catch most diagonal mistakes.
  • A common follow-up is "return the boards, not the count". Keep an array queens with the column for each row, push and pop it with the sets, and build the rows of text when row === n.
  • Another is "make it faster". Answer with bitmasks for the three sets and the mirror-image trick, which together cut the time by a large factor without changing the search.

Where frontend code uses it

The same idea in real UI code
  • Some package managers resolve version ranges by backtracking with constraints. pip in Python is a well-known example: it picks a version, checks every requirement, and steps back on a conflict.
  • Calendar and booking UIs that place meetings into free slots with rules (no overlaps, required people) can search the slots this way when the problem is small.
  • Puzzle and game features in the browser, such as Sudoku hints or crossword fillers, use constraint backtracking with lookup sets.

Related algorithms