N-Queens Problem — Backtracking

What does it solve?

Place N queens on an N×N chessboard so that no two queens attack each other — no shared row, column, or diagonal.

Since each row gets exactly one queen, we place row by row: try a column, check safety, recurse — and undo (backtrack) when a path leads nowhere.

The core idea

// for each row, try every column:
if isSafe(row, col):
  place(row, col)
  solve(row + 1)
  unplace(row, col) // backtrack

Complexity

Time complexity

O(N!)

Worst-case exponential search space — heavily pruned by the column/diagonal safety check.

Space complexity

O(N)

The board array and recursion depth both scale linearly with N.

Examples & edge cases

Live animation

Trying this cell Conflict / rejected Queen placed Just placed Complete solution

Step — of —

Position

—

Action

—

Queens placed

—

Solutions found

—

so far

Select a board size and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Row	Col	Action	Board (col per row)	Note

C++ implementation

n_queens.cpp

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> board;              // board[row] = col of queen
vector<vector<int>> solutions;

bool isSafe(int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = board[r];
        if (c == col) return false;                 // same column
        if (abs(c - col) == abs(r - row)) return false; // same diagonal
    }
    return true;
}

void solve(int row) {
    if (row == n) {
        solutions.push_back(board);   // found a full, valid placement
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(row, col)) {
            board[row] = col;          // place
            solve(row + 1);
            board[row] = -1;         // backtrack
        }
    }
}

int main() {
    n = 4;
    board.assign(n, -1);
    solve(0);

    cout << "Total solutions: " << solutions.size() << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars