N-Queens and the sudoku idea in Python

Why it matters

The last lesson listed every subset and every permutation. That approach works for small lists, but a puzzle with 8 rows, 9 cells per row, or many choices per step has far too many possibilities to try them all. Real search problems need a second idea, which is called pruning. Pruning means you stop exploring a path as soon as you know that it cannot lead to a valid answer. The rest of the tree under that point is never visited.

This lesson takes the choose, explore, undo pattern from the last lesson and adds pruning. You will solve two classic puzzles, N-Queens and sudoku, and a third problem, generating valid parentheses, that is a common interview question. Interviewers like these problems because they test whether you can turn a rule into an early check, and whether you can undo a choice cleanly. Both are skills you will use in many other problems.

The idea from the first principle

Imagine you are walking through a park with a map that shows paths. You want to reach a fountain. At every fork you choose a path. Suppose one path leads to a fence with no gate. If you are sensible, you turn back as soon as you see the fence. You do not walk along the fence to check whether a gate appears at the far end, because you can already see that the path is blocked. Turning back at the fence is pruning. The alternative, walking every path to its end, is a full search. Pruning makes the search much shorter without changing the answer.

Pruning has one condition that must always hold: you may only cut a branch when you are sure that no valid answer lies under it. If you cut too much, you miss answers. If you cut too little, the search is slow. Your work as the programmer is to find a check that is both safe and early. For N-Queens the check is whether a new queen is attacked. For sudoku it is whether a digit repeats in a row, column or box. For parentheses it is whether a closing bracket has a matching opening bracket.

Every backtracking function you write will have the same shape. The state is the partial answer. The loop tries each choice. A check decides whether the choice is allowed. If it is, you choose, explore and undo. If it is not, you skip the choice. The check is the pruning. Here is that loop as text:

for each choice:
    if the check says no:
        skip it                      <- pruning: no subtree is built
    else:
        choose it                    (change the state)
        explore the rest             (recurse)
        undo the choice              (restore the state)

The "skip it" line is the pruning. It means the branch never grows into a subtree, so its cost is zero.

N-Queens: the problem

A queen is a chess piece that attacks along its row, its column and both of its diagonals, as far as no other piece blocks the line. The N-Queens problem asks you to place n queens on an n by n board so that no two queens attack each other. For n equal to 4 there are 2 solutions. For n equal to 8 there are 92, which is the famous count.

The first step is to reduce the problem. Two queens in the same row attack each other, so the solution must put exactly one queen in each row. That means the search can go row by row. At each row you try each column, and you need to check three things before placing a queen:

• the column is not already used by another queen,
• the diagonal going from bottom left to top right is not already used,
• the diagonal going from top left to bottom right is not already used.

If all three are free, the new queen is safe, so you place it and move to the next row. If any of them is taken, you skip that column. That is the pruning.

How the diagonal checks work

The diagonal checks are the part most learners find hard. The trick is to find a number that is the same for every square on the same diagonal.

Take the square at row r and column c. For the diagonal from top left to bottom right, moving one square right and one square down keeps the difference r - c the same. For example, the squares (0, 0), (1, 1) and (2, 2) all have r - c equal to 0. So you can record that diagonal by its number r - c.

For the diagonal from bottom left to top right, moving one square right and one square up keeps the sum r + c the same. The squares (0, 2), (1, 1) and (2, 0) all have r + c equal to 2.

Now the list indexes. The sum r + c runs from 0 up to 2n - 2, so a list of size 2n - 1 holds every sum. The difference r - c runs from -(n - 1) up to n - 1, which includes negative numbers. In many languages a negative index is an error, so the difference is shifted by n - 1 before it is used as an index. Python handles negative indexes in a different way, and the next sections show what that changes.

Once you know these two facts, the code is a set of three lists of True and False flags: one for columns, one for sums, and one for differences. Each check is a single list lookup, so it takes constant time.

Placing the queens

Here is a complete program that counts solutions for n equal to 4 through 8, and prints the first board it finds for 4 and for 8. The inner function solve takes the current row. Its base case is a row number equal to n, which means every row has a queen. Each row loops over the columns. The lists are created inside solve_board, and solve changes them, so no global variables are needed:

Press Run. The output is:

n=4 solutions=2 calls=17
n=5 solutions=10 calls=54
n=6 solutions=4 calls=153
n=7 solutions=40 calls=552
n=8 solutions=92 calls=2057
. Q . .
. . . Q
Q . . .
. . Q .
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

The first four lines after the counts are the first board found for 4 queens. The Q marks a queen, and the dot marks an empty square. Reading down the board, the queen in row 0 is in column 1, the queen in row 1 is in column 3, the queen in row 2 is in column 0, and the queen in row 3 is in column 2. The eight lines after that are the first board for 8 queens.

The number 2 is the count for 4 queens, and 92 is the count for 8 queens. The function stops at a complete board and returns to its parent, which keeps trying the other columns, so every solution is counted.

Read the three lines of the loop carefully. The line cols[c] = diag1[row + c] = diag2[row - c + n - 1] = True sets all three flags in one statement. Python assigns the value to each target from left to right, so all three flags become True. It is clearer to write them on separate lines, and that is what you should do in your own code. The undo line clears the same three flags. The choose and undo lines must match exactly, or the search will be wrong.

Notice this detail: the check cols[c] or diag1[...] or diag2[...] comes before the choose. If you choose first and then check, you have already placed the queen and must undo it even when it turns out to be unsafe. The check first is simpler and cheaper.

The inner function changes calls[0] and not a plain number. Python does not let an inner function rebind a number from the outer function unless you write nonlocal first. A one-item list avoids that, and nonlocal is the other way to do it. Both are used in real code.

Measuring what pruning saves

It helps to see the number of calls, because the number tells you the cost. The counts above already show it. For 8 queens the search makes 2057 calls. Without any checks, the search would place one queen in each row without caring about attacks. That is 8 choices for the first row, 8 for the second, and so on, so there are 8 to the power 8, which is 16,777,216 complete placements. Pruning reduced the work from millions of full boards to about two thousand calls. The reduction grows as the board grows. The two numbers measure different things, so the gap is a rough guide, not an exact ratio.

The count of calls is not the same as the count of solutions. Each call is one node of the search tree. Most nodes are dead ends that pruning cut short, and the solutions are the leaves that reach row n. The ratio of calls to solutions is a useful way to see how well the pruning works.

The backtracking loop in one picture

Every loop in this lesson has the same three parts, and the text picture from the start of the lesson shows them. The loop tries a choice. The check is the decision point. If the check passes, the function chooses, explores and undoes. If the check fails, the function skips the choice at once.

Watch the undo. The undo comes after the explore, and it is what makes the next loop iteration start from a clean state. In N-Queens the undo clears the column, the two diagonals and the placed square. A missing undo breaks the next iteration, as the next section shows.

What goes wrong when you forget an undo

Here is N-Queens with one mistake. The diagonal flag for diag2 is set in the choose step, but the undo step only clears cols and diag1. The diag2 list keeps every flag it ever set. The program runs without an error:

Press Run. The output is:

0 0

Both answers are 0, but the correct answers are 2 and 4. The program runs without any error, and it prints a plausible-looking number. Trace the first row. The function places a queen at column 0 of row 0, which sets diag2 for that diagonal, and the undo does not clear it. Those flags stay set for the rest of the search. When the first branch ends, columns 1 and 2 of row 0 are already blocked by flags from that branch. Column 3 is tried, and then row 1 has no safe column, so the search finds nothing. The count stays at 0.

The lesson is the same one you saw in the last lesson. Every state you set in the choose step must be cleared in the undo step. The safest habit is to write the choose and undo lines next to each other while you write the code, so that you can check them together. Also, when a count is suspiciously zero, look for an undo that does not match its choose.

Negative indexes in Python

Adding n - 1 to the difference row - c keeps the index from going negative. Python behaves differently. A negative index counts from the end of the list, so flags[-1] is the last item. That means the offset is not needed for the program to run. Here is the same search with the offset removed, so the index is row - c:

Press Run. The output is:

[2, 10, 4, 40, 92]

The counts match the earlier run. The reason is that every difference r - c gets its own slot. The non-negative differences 0 to n - 1 use slots 0 to n - 1. The negative differences -1 to -(n - 1) wrap to the slots 2n - 2 down to n, which no non-negative difference uses. So the wrap is exact for this board, and no two squares share a slot by accident.

This is a fact about Python, and it is fragile. The code is right only because the list has size 2 * n - 1 and the wrap happens to land in unused slots. Keep + n - 1 anyway. It makes the index clear to a reader, and it does not depend on how negative indexes behave. The bigger lesson is about what Python does not tell you. If an index is negative by mistake, Python does not raise an error. The program keeps running with the wrong slot, and only the answer shows the problem. Check your index ranges on purpose.

Sudoku: the same pattern on a grid

A sudoku is a grid of nine rows and nine columns, split into nine boxes of three by three. Some cells start with a digit, and the rest are empty. You must 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 idea is the same as N-Queens. Find the first empty cell. Try the digits 1 to 9 in that cell. For each digit, check whether it is safe, meaning the row, the column and the box do not already hold it. If it is safe, write the digit (choose), solve the rest of the grid (explore), and if the rest fails, erase the digit (undo). If no digit works in the cell, return False so that the caller tries its next digit.

Here is the solver with the classic puzzle built in. The function is_safe does the three checks, and solve does the search. The puzzle is written as nine strings, where a dot marks an empty cell:

Press Run. The output is:

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Each row, column and box of the output holds the digits 1 to 9 once. The first row is 5 3 4 6 7 8 9 1 2, and the first column is 5 6 1 8 4 7 9 2 3. Check a box yourself: the top left box is 5 3 _, 6 _ _, _ 9 8 in the puzzle, and the solved box holds 5, 3, 4, 6, 7, 2, 1, 9, 8.

Read the solver closely. The return False after the digit loop is the key line. If no digit fits the first empty cell, the function reports failure, and the caller undoes its own digit and tries another. Without that line, a dead end would look like success and the grid would stay half empty. The return True at the end means that no empty cell is left, so the grid is solved, and the True value travels up through every caller to stop the search at once.

The pruning here is the is_safe check. Without it, every empty cell would try all nine digits, and most of those tries would fail only at the end of the grid. With it, a digit that breaks a rule is dropped at once.

The solver changes g in place. Each change is undone with g[r][c] = 0 when the rest fails, so the grid is clean for the caller's next digit. A grid that is solved is left in its solved state, because the function returns True before the undo runs.

The mistake of checking too late

Both the N-Queens and the sudoku solvers check before they choose. A common beginner version places the digit first, recurses, and then checks the result. That version is correct only if the check happens before the recursion. If it happens after, the whole subtree below a bad placement is searched first, and the answer is found only after that wasted work. In sudoku this makes the search do far more work, because every invalid digit is explored before it is rejected. Put the check where the choice is made, every time.

Generating valid parentheses

The third problem is a favourite in interviews. Given n pairs of brackets, list every string of n opening brackets and n closing brackets that is valid. A string is valid when every closing bracket has an earlier matching opening bracket, and the brackets pair up without crossing. For n equal to 2 the valid strings are (()) and ()(). The string )( is not valid, because a closing bracket comes first.

The pruning rules come from that definition. You may add an opening bracket while you have fewer than n of them. You may add a closing bracket only while there are more open brackets than closed ones, so that the closing bracket has a partner. These two checks are the whole method. The program below takes n as a fixed value. To read it from the user, replace the 3 with int(input()):

The output is:

((()))
(()())
(())()
()(())
()()()

There are five strings, which is the Catalan number for 3. Each line is a valid string, and the order comes from trying the opening bracket first at each step.

Look at what the two if checks prune. The string )( never appears, because the closing bracket is blocked when no opening bracket is open. The string (((( never gets past n opening brackets, because the first check blocks it. Each branch is cut as soon as it cannot finish as a valid string. The function never builds an invalid string and then rejects it. That is the efficiency of pruning in one small example.

The state is a single list of characters, which is changed on the way down and restored by pop on the way back up. The counters open_count and close are passed as values, so they need no undo. Both styles appear in backtracking code, and you should be able to say which one you are using and why.

Trace n equal to 2 to see the pruning. The first choice is (. From (, you may add another (, giving ((, or a ), giving (). From ((, only ) is allowed, because the opening count has reached 2. That gives ((), then (()), which is the first answer. From (), the opening bracket is still allowed, giving ()(, and then ()(), which is the second answer. The string )) is never tried, because the close check close < open_count blocks it at once.

The same rules can count without building any string. The base case returns 1, and the two checks add up the counts of their branches:

The output is:

5 2

Common mistakes

Checking after recursing. The sudoku and N-Queens checks must run before the choice. Checking after means searching a whole subtree of invalid boards first.

Forgetting the undo of a flag. The stale flag case above produced a plausible 0 with no error. When a count is zero, check every undo.

A negative index that wraps. In many languages a negative index stops the program with an error. In Python it reads the end of the list instead, and the program keeps going. Here the error is silent:

The output is:

True
True

The write to flags[-1] landed on the last slot, so the program never shows a sign of trouble. An index that goes past the end is different. It raises an error, as this program shows:

The output ends with:

IndexError: list index out of range

The fix for both is the same. Compute each index from the rules, and check that it is between 0 and len(flags) - 1 for the smallest input. A print of the index on the first call is the fastest check.

Forgetting return False in sudoku. If the digit loop ends without a return False, the function falls through to the next empty cell and never backtracks, so the grid is left with a wrong digit. Keep the return False after the loop.

Stopping too early or too late. In a search for one answer, return as soon as you find it. In a search for all answers, do not return after the first one. Decide which you need before you write the base case.

Sharing one list between boards. The boards.append(placed[:]) line saves a copy. Without the copy, every saved board would show the final state of placed, which is the same bug as the subsets lesson.

Debugging walkthrough

Suppose a friend's N-Queens program prints 0 for 4 queens and asks you what is wrong. Use the method from the first lesson. Name the expected answer: 2 solutions for 4 queens. Find the smallest input where the program fails: 4 is already the smallest interesting size, because 1 queen has 1 solution and 2 and 3 queens have none. The program fails on 4, so start there.

Look at the choose and undo lines side by side. In the buggy version above, the choose sets diag2 and the undo does not clear it. Add a print line inside solve that shows the row and column being tried, and watch the first few lines. The trace shows the flags from the first branch blocking later choices, so row 0 skips columns 1 and 2, and row 1 has no safe square after a queen in column 3. The cause is the missing undo for diag2, and the fix is one line.

Check the fix on 4 queens first. The output should be 2. Then check 5 queens, which should be 10, and 6 queens, which should be 4. Only then trust the program for 8 queens. Testing with small sizes first is the cheapest debugging tool for search problems, because the expected answers are known.

Cost in plain numbers

Plain backtracking for N-Queens places one queen per row with no checks, so it considers up to n to the power n boards. With pruning, the work is much less, but the worst case is still exponential, because the number of solutions and dead ends can still grow fast. For 8 queens the search makes 2057 calls, as the measured run showed.

Sudoku has the same worst case. A naive solver can take a long time on a puzzle with few clues. The solver in this lesson is simple and correct, and it solves the classic puzzle at once. Real sudoku tools add more pruning, such as choosing the empty cell with the fewest possible digits first, which cuts the search a lot. You can mention that in an interview as the next improvement.

Parentheses have a clean cost. The number of valid strings for n pairs is the Catalan number, which grows roughly by a factor of 4 for each extra pair. The function's work is proportional to the number of answers times n, because each answer is printed in full.

For stack space, each function here recurses once per choice. N-Queens and sudoku use one frame per row or per empty cell, so the stack depth is at most 8 or 81. Parentheses use one frame per character, so the depth is 2n. Python's default recursion limit of 1000 is well above these depths, so none of these programs reach it.

Interview and real-world uses

In an interview, the three problems in this lesson come with the same follow-up questions. What is your pruning rule, and is it safe? What is the undo, and what state does it restore? What would the cost be without pruning? A good answer names the check, explains why it cannot cut a valid answer, and gives the cost without and with the check. For parentheses, the answer is also the number of strings, which is the Catalan number, and the interviewer may ask you to prove that count by a recurrence.

In real software, the same pattern appears in layout engines that try placements and undo them, in scheduling tools that try a timetable slot and backtrack, in compilers that try a parse and back off on failure, and in puzzle games that check moves. Engineers rarely write raw backtracking for big problems, but the pruning idea, which is "do not explore what cannot work", is the basis of most search tools.

Walking through a 4-Queens search by hand

The counter program showed the numbers, but a hand trace shows why pruning works. Start with a queen at row 0, column 0. Row 1 cannot use column 0, which is taken. Column 1 is blocked by the diagonal from (0, 0), because both squares have the same difference row - c, which is 0. Columns 2 and 3 are both safe. Take column 2 first, which places a queen at (1, 2).

Now row 2. Column 0 is used. Column 1 shares the sum row + c with (1, 2), which is 3, so it is blocked. Column 2 is used. Column 3 shares the difference row - c with (1, 2), which is -1, so it is blocked too. Row 2 has no safe square, so the call for row 2 returns without placing anything. The search goes back to row 1 and tries its next safe column, column 3.

With (1, 3) placed, row 2 has one safe column, column 1, which places a queen at (2, 1). Row 3 has no safe square. Column 2 shares the difference with (2, 1), and columns 0, 1 and 3 are already used. The search backs up to row 2 and tries column 2, which shares the sum with (1, 3), so it is blocked too. Row 2 is finished, and row 1 has no columns left. So the square (0, 0) has failed, and the top row moves on to column 1. Only then does a complete board appear, with queens at (0, 1), (1, 3), (2, 0) and (3, 2). That is the first board the program prints.

Look at how much work the failed branch did. It tried a few queens, and at each row with no safe square it stopped, instead of filling the whole board under (0, 0). This is the real effect of pruning. The search does not know the answer in advance. It notices each dead end as early as it can and turns back.

Walking through an interview question about N-Queens

Suppose an interviewer asks you to count the ways to place n queens on a board. A good answer begins by restating the rules, including the fact that two queens cannot share a row, which lets you place one per row. Then name the three checks, the column and the two diagonals, and say how you store them: lists of flags indexed by column, by row + c and by row - c + n - 1.

Next explain the search. The base case is row n, which counts one solution. The loop tries each column, skips the blocked ones, and for each safe column chooses, explores and undoes. Say why the checks come before the choice. Then state the cost. Without pruning, the search would make n to the power n placements. With the checks, the search is much smaller, but the worst case is still exponential, because a board may have many dead ends.

The interviewer may ask how to print one solution instead of counting. Say that you return True at the first complete board and stop the loops, as the existence version in the Practice section does. Then ask whether the lists must be restored in that case. If you do not need them again, the undo can be skipped, but you must say so and be sure nothing else reads them.

A checklist for pruning searches

Use this checklist for any search that tries choices and rejects some of them.

• Does the check run before the choice, so a rejected choice never changes the state?
• Is the check safe, meaning it can never reject a choice that leads to a valid answer?
• Does every state the choose step sets get cleared in the undo step, with the same index?
• Is every index inside its bounds for the smallest input, including any negative values that Python would wrap?
• Does the base case count or save one complete answer, and does it stop at the right depth?
• Do you know how many calls the search makes for a small size, so you can compare it with a hand count?

Work through the checklist on a small example before you rely on the function for a large one. The counter program and the hand trace above are both useful for that.

Practice

Exercise 1 (easy). Predict the number of solutions for 4 queens and for 8 queens. Then run the first program in this lesson and check your answer. Hint: the program prints the two counts on lines starting with n=.

Show the answer

The output is 2 for 4 queens and 92 for 8 queens. Those are the known counts. If your prediction was different, check the rule that each row has exactly one queen and that the three checks are all applied.

Exercise 2 (easy). Compute the diagonal indexes for the square at row 2, column 1, on a board of size 4. Give the value of row + c and of row - c + n - 1.

Show the answer

row + c is 2 + 1, which is 3. row - c + n - 1 is 2 - 1 + 4 - 1, which is 4. Both are inside the lists of size 2 * 4 - 1, which is 7, so both indexes are valid.

Exercise 3 (easy). Using the first 4-queens board in this lesson, list the squares that a queen at row 0, column 1 attacks in the same row and the same column. Then say which columns are free in row 1 after that queen is placed.

Show the answer

The queen attacks all of row 0 except its own square, and all of column 1 below it. In row 1 the diagonals from column 1 reach columns 0 and 2, so those two squares are blocked by the diagonal checks, and column 1 is blocked by the column check. That leaves column 3 free, which matches the board, where the next queen sits in column 3.

Exercise 4 (medium). Write is_safe for N-Queens as a separate function that takes placed, a list with the column of the queen in each earlier row, and a new row and column. Hint: loop over the earlier rows and compare columns and diagonal distances.

Show the answer

def is_safe(placed: list[int], row: int, col: int) -> bool:
    for r in range(row):
        c = placed[r]
        if c == col or abs(c - col) == row - r:
            return False
    return True
 
 
print(is_safe([1], 1, 3))  # True: column 3 is not attacked by a queen at (0, 1)
print(is_safe([1], 1, 2))  # False: (0, 1) and (1, 2) are on a diagonal

Two queens attack when they share a column, which is c == col, or when their row distance equals their column distance, which means they are on a diagonal. The function is slower than the flag lists, because it loops over the rows, but it is easier to read.

Exercise 5 (medium). Run the parentheses program for n equal to 2, and predict the output before you run it. Then explain why ))( can never appear, using the rule that a closing bracket needs more opening brackets before it.

Show the answer

The output is (()) and ()(). The string ))( starts with a closing bracket, and the rule close < open_count is false at the start because both counts are 0, so the function never adds it. Any string that starts with a closing bracket is blocked in the same way.

Exercise 6 (medium). Count the calls the 4-queens search makes with the pruning in this lesson. The earlier run printed 17. Then predict roughly how many calls the search would make with no check at all for 4 queens, using the count of 4 to the power 4 full boards. Hint: compare the two numbers.

Show the answer

With the checks the search makes 17 calls for 4 queens. With no check, the search would try each of 4 columns in each of 4 rows, which is 4 to the power 4, or 256 complete boards, plus the partial boards above them. That is far more than 17, so pruning cuts the work sharply even at this small size.

Exercise 7 (medium). Write a function that counts the valid strings for a given n using the same pruning, without building any string. Check that n equal to 3 gives 5.

Show the answer

The function is the count_parens function from this lesson. Call it as count_parens(3, 0, 0), which returns 5. The base case counts one complete string, and the two pruning checks are the same as before. No string is built, so the space is only the stack.

Exercise 8 (hard). Explain, in a short paragraph, why the sudoku solver is correct when it returns True only after the last empty cell is filled. Then explain what would go wrong if the return True at the end were changed to return False.

Show the answer

The function reaches the end of the loops only when no empty cell is left, and every digit placed on the way passed is_safe, so the grid is a valid solution. Returning True lets every caller stop searching at once. If the end returned False, a solved grid would look like a failure, so every caller would undo its digit and search the rest of the tree. The solver would then undo a correct solution and report that the puzzle has no answer.

Exercise 9 (hard). Explain why the choose and undo lines in N-Queens must touch the diag2 list with the same index. Then write a short test that would catch a typo, where the undo uses row + c for diag2 by mistake.

Show the answer

If the undo writes to a different index from the choose, the flag set by the choose is never cleared, and the list keeps a stale flag, as the buggy program showed. A test is to run the count for 4 queens and expect 2. A typo in the undo index gives a wrong count, often 0, because stale flags block later rows. Another test is to check that after solve returns, every flag is False again, which catches any choose without a matching undo.

Exercise 10 (hard). Write a function that returns True when n queens can be placed on an n by n board, and stops as soon as one solution is found. Explain why it returns sooner than the counting version, and state its worst-case cost.

Show the answer

def exists_solution(n: int) -> bool:
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)
 
    def place(row: int) -> bool:
        if row == n:
            return True
        for c in range(n):
            if cols[c] or diag1[row + c] or diag2[row - c + n - 1]:
                continue
            cols[c] = diag1[row + c] = diag2[row - c + n - 1] = True
            if place(row + 1):
                return True
            cols[c] = diag1[row + c] = diag2[row - c + n - 1] = False
        return False
 
    return place(0)
 
 
print(exists_solution(4), exists_solution(8))  # True True

It returns True from every level at once when a row completes, so the loops stop and the other columns are not tried. The undo runs only on a failed branch, so a True answer leaves the lists set, which is fine because the lists are local to the function. The worst case is still exponential, for a board with no solution, because every branch must be explored before the function can return False.

What you now know

• Pruning cuts a branch of the search tree as soon as it cannot lead to a valid answer, and it must never cut a branch that could.
• N-Queens places one queen per row and checks the column and both diagonals before each choice.
• The diagonal checks use row + c and row - c + n - 1 as list indexes, so they stay in range.
• Python wraps a negative index to the end of the list without an error, so a bad index can give a wrong answer silently. Check index ranges on purpose.
• Sudoku uses the same loop. The is_safe check is the pruning, and return False after the digit loop is the backtrack.
• Parentheses use two pruning rules: add an opening bracket only while there are fewer than n, and add a closing bracket only while it has a partner.
• Check before you choose, and undo every change you made, or stale state gives a wrong answer.
• Count the calls to measure the cost. For 8 queens the pruned search made 2057 calls, while the naive search would make 16,777,216 complete placements.