N Queens Problem Explained With Backtracking

The n queens problem is the classic way students meet backtracking. And backtracking is where a lot of people get stuck, because most tutorials only show the path that works.

They never show the part that matters. What happens when you get stuck and have to take a move back? That undo is the real lesson here, so let me show it to you in full.

What is the n queens problem?

A queen in chess attacks along its row, its column, and both diagonals. The n queens problem asks a simple question. Can you place n queens on an n by n board so that no queen attacks any other?

For a standard 8 by 8 board, that means placing 8 queens with none sharing a row, a column, or a diagonal. It turns out there are 92 ways to do it. The smallest interesting board is 4 by 4, which has just two solutions, so that is what we will solve by hand.

The puzzle sounds like a chess problem, but it is really a lesson in a method called backtracking. That method is the actual prize here.

What is backtracking?

Backtracking is a way to try choices one at a time, and undo them when they lead nowhere. You make a move, then check if it could still work. If it can, you go deeper. If it cannot, you take the move back and try the next option.

Think of walking through a maze. You pick a path. When you hit a wall, you do not give up. You walk back to the last fork and try a different turn. Backtracking is that idea written in code, and it builds directly on how recursion works. Backtracking is really just recursion with an undo step.

How does n queens work step by step?

Let’s solve the 4 by 4 board by hand. The plan is to place one queen per row, then move down. For each row we try columns left to right, and we check that the new queen is safe from every queen already placed.

Start in row 0. Place a queen in column 0. So far so good, because the board is empty. Move to row 1. Columns 0 and 1 are attacked by the first queen, so the first safe square is column 2. Place a queen there and move to row 2.

Now row 2 is the interesting part. Column 0 is attacked down the file. Column 1 is attacked on a diagonal. Column 2 shares a column with the row 1 queen. Column 3 is attacked on the other diagonal. Every single square in row 2 is unsafe. This is a dead end.

Here is the move most tutorials skip. We backtrack. We remove the queen from row 1, column 2, and go back to try the next column in row 1. Column 3 is safe, so we place a queen there instead and move down again. This time the search finds room, and after a couple more placements the board reaches a full, valid solution with one queen in each row and none attacking another.

N queens code in Python and C++

The code follows the exact steps we just did. A helper checks if a square is safe. The main function tries each column in the current row, places a queen, and calls itself for the next row. Here it is in Python.

def solve(board, row, n):
    if row == n:
        return True                      # all queens placed
    for col in range(n):
        if is_safe(board, row, col, n):
            board[row] = col             # place queen
            if solve(board, row + 1, n):
                return True
            board[row] = -1              # backtrack, remove queen
    return False

The line that removes the queen is the backtrack. It runs only when the deeper call failed, which means the placement led to a dead end. Here is the same shape in C++, the language most Indian placement tests expect.

bool solve(int board[], int row, int n) {
    if (row == n)
        return true;                     // all queens placed
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row] = col;            // place queen
            if (solve(board, row + 1, n))
                return true;
            board[row] = -1;             // backtrack, remove queen
        }
    }
    return false;
}

Both versions store one column number per row, so the whole board fits in a small array. The recursion handles moving down the rows, and the loop handles trying each column and undoing failed tries.

What is the time complexity of the n queens problem?

This is where you have to be honest. The n queens problem is slow. In the worst case the time is around O(n factorial), because each row has fewer safe choices than the last, but the count still grows faster than any polynomial.

To put a number on it, an 8 by 8 board is fine and solves in an instant. But push n higher and the work explodes. Backtracking helps a lot, because it cuts off dead ends early instead of checking every full arrangement. Still, no one expects n queens to be fast. The space is O(n), since you only store one column per row. You can read more on Wikipedia’s eight queens page.

Why learn the n queens problem?

You will almost never place queens on a board at work. So why does this problem show up in every course and interview? Because the backtracking pattern it teaches is everywhere.

The same place, check, undo loop solves Sudoku, maze pathfinding, word search puzzles, and many constraint problems where you build a solution piece by piece. Learn it once on the clear, visual chessboard, and you can spot it in problems that look nothing like chess. It is one of the most reused patterns in any DSA learning path.

FAQ

What is the n queens problem in simple terms?

It asks you to place n queens on an n by n chessboard so no two queens attack each other. No two can share a row, a column, or a diagonal.

How many solutions does the 8 queens problem have?

There are 92 solutions on a standard 8 by 8 board. If you count only the truly distinct shapes, ignoring rotations and mirror images, there are 12.

What is backtracking in the n queens problem?

It is the step where the code removes the last queen it placed after hitting a dead end, then tries the next option. That undo lets the search recover instead of failing.

Why does the n queens problem use recursion?

Each row is a smaller version of the same task. Recursion handles one row, then calls itself for the next, which makes the place and undo pattern clean to write.

Is the n queens problem NP hard?

Finding one solution is not NP hard and can be done fairly quickly. But the problem grows fast as n rises, which is why it is used to teach backtracking rather than as a fast algorithm.

What is the smallest board with a solution?

A 1 by 1 board works trivially. After that, boards of size 2 and 3 have no solution, and the 4 by 4 board is the smallest real puzzle, with two solutions.

So what should you remember?

The n queens problem is not really about chess. It is about one powerful pattern. Place a choice, check if it can still work, go deeper, and undo the moment you get stuck.

That place, check, undo loop is backtracking, and it solves a huge family of puzzles once you see it clearly. The chessboard is just the easiest place to watch it happen.

Now picture the 4 by 4 board. If your first queen sits in row 0 column 1, which column is the first safe square for the queen in row 1?