HardBacktrackingRecursionArray

N-Queens

1 approach, code in every language

On an n by n chessboard you must place n queens so that no two of them threaten each other. A queen attacks any piece sharing its row, its column, or either of its two diagonals, so a valid arrangement keeps every pair of queens off the same row, column, and diagonal.

Return all distinct board layouts that satisfy this rule. Represent each board as a list of strings where the character 'Q' marks a queen and '.' marks an empty square.

Example 1

Input: n = 4

Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]

There are exactly two ways to place four non-attacking queens on a four by four board.

Example 2

Input: n = 1

Output: [["Q"]]

A single queen on a one by one board trivially satisfies the rule.

Constraints

1 <= n <= 9
Exactly one queen is placed in each row and each column
No two queens may share a diagonal

Row-by-row placement with occupancy sets

Place one queen per row, using boolean markers for used columns and both diagonal directions so conflicts are detected in constant time before recursing.

Loading animation…

Intuition

Because exactly one queen belongs in each row, we can decide the columns row by row. For a queen at (row, col), the cells it attacks along diagonals all share a constant value of row + col on one diagonal and row - col on the other. By marking which columns and which diagonal values are already occupied, we can check any candidate square instantly. When we reach a row past the last one, every queen has been safely placed and we record the board.

Algorithm walkthrough

1Fill an n by n board with '.' and prepare markers for columns and the two diagonal families.
2Recurse on the current row; if the row index equals n, capture the completed board.
3For each column in the row, skip it if the column or either diagonal is already occupied.
4Place a queen, mark its column and diagonals, then recurse on the next row.
5Remove the queen and clear the markers so the next column can be tried.

Implementation

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        cols = set()
        diag1 = set()   # row - col
        diag2 = set()   # row + col
        board = [["."] * n for _ in range(n)]

        def backtrack(row: int) -> None:
            if row == n:
                result.append(["".join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        backtrack(0)
        return result

Time

O(n!)

Space

O(n^2)

Pruning by column and diagonal makes the effective branching far smaller than n per level; the board dominates space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Beacon Ridge Layouts is our own problem on the technique behind N-Queens: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free