N-Queens and the sudoku idea

Why it matters

N-Queens is one of the most common backtracking questions in interviews. It shows the real power of the method. A plain search over every way to place the queens would be far too slow, but a search that stops early on a bad path finishes quickly. That stopping is called pruning. Sudoku uses the same plan, and it is a puzzle many learners already know. Once you see that both problems are "try a choice, check the rules, go deeper, undo if stuck," you have the core of backtracking for every problem in the rest of this course.

The problem: N queens on a board

A chessboard has 8 rows and 8 columns. A queen is a chess piece that attacks along its row, its column and both diagonals, for any distance, as long as no other piece blocks the way. The N-Queens problem asks you to place N queens on an N by N board so that no two queens attack each other.

Some rules follow from the attack rule. Two queens in the same row attack each other, so every row must hold exactly one queen. Two queens in the same column also attack, so every column holds at most one queen. Because there are N rows and N queens, every row has exactly one queen, and every column has exactly one queen. The only thing left to check is the two diagonals.

For a 4 by 4 board the answer has 2 solutions, and for an 8 by 8 board it has 92. A solution is a full placement, and two solutions that are mirror images or rotations of each other still count as two.

The idea: place one queen per row

Use the row rule to shape the search. Place queens row by row, starting at row 0. For the current row r, try each column c from 0 to N minus 1. If the square at (r, c) is safe, place a queen there and go to row r + 1. If no column works for row r, return without placing anything. The caller then moves its own queen to its next column. That return is the backtrack.

Think of filling a row of parking spaces with cars, where a car in one space blocks the spaces next to it in all directions. You park a car in row 1. Then you look for a legal space in row 2. If row 2 has no legal space, you pick up the car in row 1 and move it to the next legal space. You keep going until every row has a car, or until you have tried every option.

The row rule means the search never checks two queens in the same row, because it places only one per row. It still needs to check columns and diagonals. Checking them quickly is the next question.

Checking the diagonals fast

Two squares sit on the same diagonal when moving from one to the other takes the same number of steps across as up or down. Mathematically, the squares (r1, c1) and (r2, c2) share a diagonal when r1 - c1 equals r2 - c2, or when r1 + c1 equals r2 + c2. The first is the diagonal running from top left to bottom right, and the second is the diagonal running from top right to bottom left.

You could check every queen placed so far on each new square. That costs time proportional to the number of queens. A faster way is to keep three arrays of flags:

• col[c] is true when column c holds a queen.
• d1[r + c] is true when the anti-diagonal with sum r + c holds a queen. The sum runs from 0 to 2N minus 2, so the array has 2N minus 1 entries.
• d2[r - c + n - 1] is true when the diagonal with difference r - c holds a queen. The difference runs from minus (N minus 1) to N minus 1. Adding n - 1 shifts it so every index is zero or more, which is required for an array index.

Checking a square now takes three array reads. Placing a queen sets three flags, and undoing it clears the same three flags. Keep these three formulas in mind, because they are the most common place to make a mistake.

Worked example 1: print every solution for a board you choose

The first program reads a board size from the Input box, then prints every solution as a board of dots and Q letters, followed by the total. Read the function solve and notice the three checks, the placement, the recursion and the undo.

Type 4 into the Input box and press Run. The output is:

.Q..
...Q
Q...
..Q.
 
..Q.
Q...
...Q
.Q..
 
2 solutions

The first board has the queens at columns 1, 3, 0, 2 in rows 0 to 3. Check the rules by hand. Row 0 has its queen in column 1, row 1 in column 3, row 2 in column 0 and row 3 in column 2. All four columns are used once, so the column rule holds. For the diagonals, the queens have sums r + c of 1, 4, 2 and 5, which are all different, and differences r - c of minus 1, minus 2, 2 and 1, which are all different. No two queens share a diagonal, so the board is valid.

Trace the search for the first solution. Row 0 tries column 0 first, and that choice is a dead end for n equal to 4. Row 1 cannot use column 0, because it is taken. Column 1 is on the same diagonal as the queen in row 0, since both have difference 0. Column 2 is safe, so the search places a queen there. Row 2 then has no safe column: column 0 is taken, column 1 and column 3 are on diagonals of the queens in rows 0 and 1, and column 2 is taken. Row 2 returns without placing anything, and row 1 is undone. Row 1 tries column 3, which is safe, and row 2 then finds column 1. Row 3 has no safe column after that, so the search backs out again. Eventually row 0 moves to column 1, and the search finds the first board in the output, with queens at columns 1, 3, 0 and 2. Notice that the search did real work to reach this answer. It tried a dead end, backed out, and tried the next choice, which is the whole method in one example.

The line col[c] = d1[r + c] = d2[r - c + n - 1] = true; sets three flags in one statement. The chain works because each assignment returns the value it set, so the expression feeds the next one. The undo line clears the same three flags, in the same order, so the state returns exactly to what it was before the choice.

Step through the animation below. It shows the stack of rows, one frame for each queen placed so far.

Notice the depth. The stack holds at most N frames, one per row, because the row rule guarantees that each frame places exactly one queen. The loop inside each frame is what gives the search its width.

An 8 by 8 board with one queen per row and a line of attack along each diagonal from a queen

Why pruning matters

Without pruning, the search would place a queen in every row, in every column, with no checks. That is N to the power N placements, which is 4 to the power 4 for a small board, or 8 to the power 8 for a full chessboard, which is over 16 million. The pruning line if (col[c] || d1[...] || d2[...]) continue; discards every placement that breaks a rule at once. It also discards everything that could have grown from that placement. A bad square in row 2 means no need to explore rows 3 and beyond on that path.

The number of nodes actually visited is far smaller than the number of full placements. For 8 queens the search still needs to visit a large number of partial boards, but it finishes in well under a second on any modern machine. Its worst-case cost grows roughly like N factorial, which is a steep curve, but the pruning keeps the real cost far below the raw count for the sizes you will meet.

Pruning is the single idea to remember from this lesson. Backtracking without pruning is a brute force search. Backtracking with good pruning is practical. You prune by checking each choice against the rules as early as possible.

Worked example 2: count the solutions for many board sizes

The next program does not print the boards. It counts the solutions for every size from 1 to 9. It also reuses the same arrays for each size, which is why it resizes them inside the loop. Watching how the counts grow helps you see the pattern, and it is a useful test for any N-Queens function: the known answers are 1, 0, 0, 2, 10, 4, 40, 92 and 352.

No input is needed. The output is:

n=1 solutions=1
n=2 solutions=0
n=3 solutions=0
n=4 solutions=2
n=5 solutions=10
n=6 solutions=4
n=7 solutions=40
n=8 solutions=92
n=9 solutions=352

Two things stand out. First, boards of size 2 and 3 have no solutions at all. The pruning finds that out quickly: on a 3 by 3 board, every placement of the first queen leads to a dead end in the third row. Second, the counts do not grow smoothly. The count drops at 6, which is smaller than at 5. That is a fact of the puzzle, not a bug. Larger boards have more room, but also more ways to attack each other, and the count depends on how those rules interact.

Notice how small the new code is compared with the version that prints boards. The printing is the slow part for large counts. When a question asks only for the number, leave the output out of the recursion. This is the same habit you saw with derangements in the last lesson.

Worked example 3: stop at the first solution

Many problems ask for one answer, not all of them. The first solution is enough for a puzzle game, and it is faster to find than all of them. To stop early, change the recursion to return a bool. A true return means "this branch led to a full solution," and the caller stops looping and passes true upward. A false return means "no solution from here," and the caller undoes its choice and tries the next column.

This is the same pattern as sudoku, which comes later in the lesson. The bool return is the signal that stops the search. Notice that when the function returns true, it does not undo its choice. That is correct, because the board is the answer and must stay as it is.

Type 8 into the Input box and press Run. The output is the first board the search finds, scanning columns from 0 to 7 in each row:

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

The search backs out many times along the way. The first full board it completes is this one. It is the smallest in the order of the columns read row by row, because each row tries its columns from left to right. That is why the output is the same every time you run it.

The return value controls the search. solve(r + 1) returns true only when a full board is found below it. The caller passes that true upward with return true, so every frame above stops looping. A false return from solve(r + 1) is the signal to keep looping and try the next column. This is one of the most useful patterns in backtracking: use the return value to tell the caller "stop" or "keep trying."

The sudoku idea

A sudoku board is a 9 by 9 grid, divided into nine boxes of 3 by 3. Some cells start filled with digits, and the rest are empty. The goal is to fill every empty cell with a digit from 1 to 9 so that every row, every column and every box holds each digit exactly once.

The backtracking plan is the same as N-Queens, with three changes. The choice is a digit, not a column. The rules are row, column and box, not diagonals. And the search goes to the next empty cell, not to the next row.

1. Find the next empty cell. If there is none, the board is solved, and the function returns true.
2. For each digit from 1 to 9, check that the digit is not already in the cell's row, column or 3 by 3 box.
3. If the digit is safe, write it into the cell and recurse to fill the next empty cell. If the recursion returns true, pass true upward.
4. If the recursion returns false, erase the digit, which is the undo, and try the next digit.
5. If no digit works, return false, so the caller can change its own digit.

The code below uses exactly this plan. It also uses the bool return from the previous example. Read the three checks in canPlace first, because they are the rules of the puzzle, and then read solve.

No input is needed. The output is the completed puzzle:

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

The puzzle is the famous example from many sudoku guides. The givens in the first row are 5, 3, 7, and the digits 4, 6, 8, 9, 1, 2 are the empty cells the search fills in. Each row, column and box holds 1 to 9 exactly once in the output. You can check that by eye for the first row, the first column and the top-left box.

Trace the start of the search. The first empty cell is row 0, column 2. Row 0 holds 5, 3 and 7, and column 2 holds 8. The box in the top left holds 5, 3, 6, 9 and 8. So the digits 1, 2 and 4 pass all three checks, and the solver tries them in order. It writes 1 and recurses. Later the search finds that 1 leads to a dead end, so it erases the 1 and tries 2, which also fails further on. Then it tries 4, which leads to the solution. The final board has 4 in that cell. Most of the work happens near the end, when only one or two digits are possible in each cell. A cell with one possible digit is filled at once, and a cell with no possible digit makes the search backtrack.

The search does not look at cells that are already filled, because solve skips any cell whose value is not 0. The first empty cell it finds is always the earliest one in row-major order. That order is a choice. Another order would still find a solution, but it might visit different partial boards on the way.

Think of the stack in this example. Each frame of solve belongs to one empty cell. The depth is the number of empty cells, which is at most 81. Each frame tries up to 9 digits, and the recursion goes deeper only for digits that pass the check.

What the three checks have in common

In N-Queens, the checks are the column flag and the two diagonal flags. In sudoku, the checks are the row, the column and the box. In both, the check is a rule about the whole partial solution, and each choice must keep every rule true. The search never builds a partial solution that breaks a rule, because the check comes before the choice. That is the common principle behind pruning: check the rules before making the choice, not after.

Look at the two undo lines. In N-Queens, three flags are cleared. In sudoku, one cell is set back to 0. In each case the undo restores the state from before the choice. A reader can check this at a glance: every write has a matching restore, and the restore happens after the recursion, not before.

Complexity

Let N be the board size, and let E be the number of empty cells in sudoku.

• For N-Queens, the search visits partial boards. In the worst case it visits a number of nodes that grows roughly like N factorial, and the pruning keeps the real count much lower. The memory used is the depth, N, plus the three flag arrays of size about 2N, so the extra space is O(N).
• For sudoku, the worst case is 9 to the power E, because each empty cell has up to 9 digits. Real puzzles are far smaller than that, because the rules rule out most digits early. The check costs O(1) for the row and column, and O(1) for the box, since each has nine cells. The extra space is the depth E, which is at most 81.

Be precise in an interview. Say that the worst case is exponential and that pruning makes typical inputs fast. Do not claim that a problem is always fast.

Bits as flags for the columns

The three flag arrays in this lesson can be replaced by bit masks, where each flag is one bit of an integer. This is the faster style often used in competitive programming. A board with up to 16 columns needs one integer for the column flags. The two diagonal masks move one bit per row: the left diagonal mask shifts left by one as the search goes down a row, and the right diagonal mask shifts right. A square is safe when its column bit and both diagonal bits are 0.

The bit version needs no index formulas, which removes the n - 1 shift error entirely. It is harder to read, though, and the arrays in this lesson are the clearer choice while you learn. Pick the style you can check by eye. A correct solution that a reader can follow is worth more than a fast one nobody can review.

How to test an N-Queens solver

Use the known counts as a test table. For n equal to 1 the count is 1, for 2 and 3 it is 0, for 4 it is 2, for 5 it is 10, for 6 it is 4, and for 8 it is 92. Run the counting version for each size and compare. A solver that matches every row of that table is almost certainly correct, because the pattern of counts is hard to match by accident.

Test the boards as well. Write a short checker that reads each printed board and confirms three things: each row has exactly one Q, each column has exactly one Q, and no two Q characters share a diagonal. The checker is also a good habit for any puzzle solver, because it tests the rules directly instead of trusting the search.

The sudoku search as a tree

The sudoku search is a tree too. Each level is one empty cell, and each node has up to nine children, one for each digit that passes the checks. The tree is pruned at every node where a digit fails, so most branches are cut near the top.

For a puzzle with one answer, the search visits the path to that answer plus every dead end it entered before reaching it. The number of dead ends depends on the order of the cells. Filling the cell with the fewest possible digits first is a well-known improvement, and it can cut the search sharply on hard puzzles. You are not asked to build it here, but an interviewer may ask how you would speed up the solver, and that is the first answer to give.

Common mistakes and the messages you will see

Mistake 1: wrong diagonal index. The difference r - c can be negative, so the index for the second diagonal array must add n - 1. Without the shift, the index for row 0, column 1 is -1, which is outside the array. A vector<bool> does not check its bounds with [], so the program may read or write memory it does not own. The result is random behavior or a crash. Using .at() instead of [] gives a clear message:

terminate called after throwing an instance of 'std::out_of_range'

Use .at() while you are debugging, and switch back to [] once the code is correct.

Mistake 2: forgetting to undo all three arrays. If you clear only col[c], the diagonals stay marked after a branch ends. Later branches then see fake attacks and skip valid squares. The count of solutions comes out too small, often zero. The fix is to clear all three flags, in the same order they were set.

Mistake 3: checking after recursing. If you place the queen first and check afterward, the search goes down bad paths and then discovers the problem late. The result may still be correct, but the search is much slower. Always check before you choose.

Mistake 4: sudoku keeps going after a solution. If solve() returns void, or the caller ignores the result, the function keeps searching after the board is full. It then undoes the solution and may print a different board or none at all. The fix is the bool return, with if (solve()) return true;.

Mistake 5: forgetting the box corner. The box for cell (r, c) starts at row r / 3 * 3 and column c / 3 * 3. Writing r / 3 gives the box number, not the corner. The check then looks at the wrong nine cells. This error does not give a compile message. The output is an invalid board.

Mistake 6: flag arrays sized too small. The column array needs N entries, and the two diagonal arrays need 2N minus 1 entries each. If d1 is sized to N instead, the index r + c runs past its end for large rows and columns. With .at() the program stops with a range message that names the bad index and the size. Size the arrays from the board size, as the program does with assign.

Debugging walkthrough

A student writes N-Queens and gets 0 solutions for n equal to 4, which is wrong. The student prints the arrays after each placement and sees that d1 never becomes false again. The buggy undo line is this:

void solve(int r) {
    if (r == n) { solutions++; return; }
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
        col[c] = d1[r + c] = d2[r - c + n - 1] = true;
        solve(r + 1);
        col[c] = false;              // bug: the two diagonal flags are never cleared
    }
}

After the first branch clears only the column flag, the diagonal flags stay set for the rest of the search. Every later row sees diagonals that are not really attacked, so the search dead-ends early. The count drops to zero. The fix is to clear all three flags, col[c] = d1[r + c] = d2[r - c + n - 1] = false;.

The method is the same as in the earlier lessons. Print the state before and after each recursive call. Check that the state after the undo matches the state before the choice. A backtracking function that fails this check is wrong, even if it happens to give the right answer on a small input.

Variations and edge cases

Board size 1. The answer is one solution, the single queen on the single square. Your arrays must have size 2N minus 1, which is 1, so the formulas still work.

Boards that have no solution. For n equal to 2 and 3 there is no solution. The function returns false from the top, and the program must say so instead of printing nothing.

Counting versus finding. Use the counting version when the question asks how many, and the bool version when it asks for one arrangement. Changing the return type is the switch.

Sudoku with a unique answer. A well-made puzzle has exactly one solution. The solver finds it, and it stops there. A puzzle with several answers still returns the first one in order.

Rows and columns with no empty cells. The sudoku solver handles this by returning true when it finds no empty cell, which means the board is already complete.

Interview questions

• Describe the N-Queens backtracking in one paragraph. Answer with the row-by-row placement, the three flag arrays, the undo, and the reason pruning matters.
• Why is a diagonal index r - c + n - 1 and not r - c? Answer that the difference can be negative, and array indexes must be zero or more.
• How do you stop the search after the first solution? Answer by returning a bool and passing true upward without undoing.
• What is the worst-case time for sudoku? Answer 9 to the power of the number of empty cells, and explain that the rules make real puzzles much faster.

Real-world uses

Backtracking with pruning is behind many tools that search for a valid arrangement. A timetable generator places classes into time slots and backs out when two classes clash. A logistics tool that assigns trucks to routes uses the same idea, with the capacity as the rule. A compiler's register allocator and a scheduling tool for a factory both search partial assignments and undo them when they break a constraint. A game that generates a puzzle with one answer uses the solver to check that the answer is unique. In each case, the rule checks happen before the choice, and the undo restores the state for the next try.

Practice

Write each exercise before you open the solution. The hints show a way to start.

1. Count solutions for n equal to 6, which should be 4, and for n equal to 5, which should be 10. Hint: use the counting version from worked example 2, and change only the size.

2. Change the bool version so it prints the number of nodes it visits, not the board. Predict the count for n equal to 4 before you run it, then check it. Hint: add a counter and increment it at the top of solve.

3. Write bool safe(const vector<string>& board, int r, int c) for a board of '.' and 'Q' characters. It returns true when no queen attacks (r, c). Hint: scan the column, then the two diagonals going up.

bool safe(const vector<string>& board, int r, int c) {
    int n = board.size();
    for (int i = 0; i < r; i++) {
        if (board[i][c] == 'Q') return false;                              // column
        if (c - (r - i) >= 0 && board[i][c - (r - i)] == 'Q') return false; // up-left
        if (c + (r - i) < n && board[i][c + (r - i)] == 'Q') return false;  // up-right
    }
    return true;
}

4. Write the sudoku helper int countEmpty(int grid[9][9]) that returns how many cells hold 0. Test it on the puzzle from this lesson, which has 51 empty cells.

int countEmpty(int grid[9][9]) {
    int count = 0;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            if (grid[r][c] == 0) count++;
    return count;
}

5. Explain why the sudoku solve checks grid[r][c] == 0 and not canPlace before it chooses the first empty cell.

6. A student says the sudoku solver is still correct if return true; at the end of solve is changed to return false;. Explain why this is wrong.

7. Write bool isSolvedRow(int row[9]) that returns true when a row holds the digits 1 to 9 exactly once each. Hint: use a flag array of size 10.

bool isSolvedRow(int row[9]) {
    bool seen[10] = {false};
    for (int i = 0; i < 9; i++) {
        if (row[i] < 1 || row[i] > 9 || seen[row[i]]) return false;
        seen[row[i]] = true;
    }
    return true;
}

8. Predict whether the first solution for n equal to 8 changes if the columns are tried from 7 down to 0. Explain your answer.

9. Explain why the three checks in N-Queens are enough, and why a fourth check for rows is not needed.

10. A student writes the bool version of N-Queens and forgets the undo line after the failed recursive call. Predict what goes wrong for n equal to 4, and explain how you would see it.

What you now know

• N-Queens places one queen per row, and it uses three flag arrays to check columns and diagonals in constant time.
• Pruning checks each choice against the rules before making it, which keeps the search small.
• A bool return from the recursion tells the caller to stop after the first solution, or to keep trying.
• Sudoku uses the same choose, check, explore and undo plan, with rows, columns and boxes as the rules.
• Every write in backtracking needs a matching undo after the recursion.
• Check the diagonal and box formulas carefully, because most errors come from an index that is off by one or shifted.