N-Queens

N-Queens is the classic puzzle that interviewers use to test backtracking. You have a chessboard. You must place queens so none of them can attack each other. It sounds hard. But once you see the trick of going one row at a time, it becomes a clean and steady process.

🎯 The Problem

You place n queens on an n by n board so no two queens attack each other.

The rules:

• A queen attacks along its row, its column, and both diagonals.
• No two queens may share a row, a column, or a diagonal.
• A spot is safe when no earlier queen shares its column or either diagonal.
• Return how many ways you can place them, or the actual boards.

Input:  n = 4
Output: 2

Explanation: There are two distinct ways to place 4 queens
on a 4x4 board so that none attack each other.

Here is one valid board for n equal to 4. The Q marks a queen. The dot marks an empty square. Notice no two queens share a column or a diagonal.

🐢 Approach 1: Place Queens Anywhere Then Check (Brute Force)

The idea:

• Try putting n queens on any n squares of the board.
• For each placement, check if any two queens attack each other.
• Count the placements where none attack.

Why it is weak:

• The number of ways to pick squares is enormous.
• Most placements break the rules right away.
• You scan the whole board to verify each one.
• It is far too slow even for small boards.

Here is a brute-force permutation check for that idea:

from itertools import permutations


def solve_n_queens(n):
    boards = []
    for cols in permutations(range(n)):
        if len({r + c for r, c in enumerate(cols)}) == n and len({r - c for r, c in enumerate(cols)}) == n:
            boards.append(["." * c + "Q" + "." * (n - c - 1) for c in cols])
    return boards

⚡ Approach 2: One Queen Per Row With Fast Safety (Best)

The idea in one line: place exactly one queen per row, track used columns and diagonals in sets, so each safety check is instant.

Why one queen per row:

• Two queens can never share a row this way.
• So one whole type of conflict is gone for free.
• Now only columns and diagonals matter.

How it works:

• Go row by row. In each row try every column.
• Ask: is this square safe from the queens in earlier rows?
• Safe means no earlier queen shares its column or either diagonal.

The diagonal trick:

• Two squares share one diagonal when row minus column is equal.
• They share the other diagonal when row plus column is equal.
• Track used columns, used diagonals, and used anti-diagonals in sets.
• Then the check is instant.

How a branch flows:

• Square is safe, so place a queen and mark its column and both diagonals.
• Recurse to the next row.
• Fill all n rows, count one valid board.
• No safe column in a row, dead end. Remove the last queen and try the next column. That removal is the backtracking.

Steps to Solve

1. Go one row at a time, starting from row zero.
2. If you have placed a queen in every row, count this as one valid board.
3. In the current row, try each column.
4. Check if that square is safe, meaning no queen shares its column or either diagonal.
5. If it is safe, place the queen and mark its column and both diagonals as used.
6. Recurse to the next row.
7. After the recursion returns, remove the queen and unmark its column and diagonals, then try the next column.

Here is the decision tree for the first row when n equals 4. We try each column, then go deeper only where it stays safe.

#include <stdio.h>

int n = 4;
int cols[10];      // used columns
int diag1[20];     // used row - col diagonals (offset by n)
int diag2[20];     // used row + col diagonals
int total = 0;

void solve(int row) {
    if (row == n) {        // a queen in every row
        total++;
        return;
    }
    for (int col = 0; col < n; col++) {
        int d1 = row - col + n;     // shift to keep index positive
        int d2 = row + col;
        if (cols[col] || diag1[d1] || diag2[d2]) continue;  // not safe
        cols[col] = diag1[d1] = diag2[d2] = 1;   // place queen
        solve(row + 1);                          // next row
        cols[col] = diag1[d1] = diag2[d2] = 0;   // remove (backtrack)
    }
}

int main(void) {
    solve(0);
    printf("%d\n", total);
    return 0;
}

2

#include <iostream>
#include <vector>
using namespace std;

int n = 4;
vector<bool> cols(10, false);
vector<bool> diag1(20, false);   // row - col
vector<bool> diag2(20, false);   // row + col
int total = 0;

void solve(int row) {
    if (row == n) {       // queen placed in every row
        total++;
        return;
    }
    for (int col = 0; col < n; col++) {
        int d1 = row - col + n;
        int d2 = row + col;
        if (cols[col] || diag1[d1] || diag2[d2]) continue;  // not safe
        cols[col] = diag1[d1] = diag2[d2] = true;   // place queen
        solve(row + 1);                             // next row
        cols[col] = diag1[d1] = diag2[d2] = false;  // backtrack
    }
}

int main() {
    solve(0);
    cout << total << endl;
    return 0;
}

2

public class NQueens {
    static int n = 4;
    static boolean[] cols = new boolean[10];
    static boolean[] diag1 = new boolean[20];   // row - col
    static boolean[] diag2 = new boolean[20];   // row + col
    static int total = 0;

    static void solve(int row) {
        if (row == n) {       // a queen in every row
            total++;
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n;
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;  // not safe
            cols[col] = diag1[d1] = diag2[d2] = true;   // place queen
            solve(row + 1);                             // next row
            cols[col] = diag1[d1] = diag2[d2] = false;  // backtrack
        }
    }

    public static void main(String[] args) {
        solve(0);
        System.out.println(total);
    }
}

2

def total_n_queens(n):
    cols = set()        # columns that already have a queen
    diag1 = set()       # row - col diagonals
    diag2 = set()       # row + col diagonals
    count = 0

    def solve(row):
        nonlocal count
        if row == n:                 # a queen in every row
            count += 1
            return
        for col in range(n):
            d1 = row - col
            d2 = row + col
            if col in cols or d1 in diag1 or d2 in diag2:
                continue             # this square is not safe
            cols.add(col)            # place the queen
            diag1.add(d1)
            diag2.add(d2)
            solve(row + 1)           # move to the next row
            cols.remove(col)         # remove the queen (backtrack)
            diag1.remove(d1)
            diag2.remove(d2)

    solve(0)
    return count


print(total_n_queens(4))

2

function totalNQueens(n) {
  const cols = new Set();   // used columns
  const diag1 = new Set();  // row - col
  const diag2 = new Set();  // row + col
  let count = 0;

  function solve(row) {
    if (row === n) {        // a queen in every row
      count++;
      return;
    }
    for (let col = 0; col < n; col++) {
      const d1 = row - col;
      const d2 = row + col;
      if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) {
        continue;           // not safe
      }
      cols.add(col);        // place the queen
      diag1.add(d1);
      diag2.add(d2);
      solve(row + 1);       // next row
      cols.delete(col);     // backtrack
      diag1.delete(d1);
      diag2.delete(d2);
    }
  }

  solve(0);
  return count;
}

console.log(totalNQueens(4));

2

Let us read the Python version line by line. The three sets are what make the safety check fast.

cols = set() holds every column that already has a queen. diag1 = set() and diag2 = set() hold the diagonals that are taken. We use sets because checking membership in a set is almost instant.

if row == n: is the stop condition. row is the row we are filling. When row reaches n, we have placed a queen in every single row. So this is one complete valid board, and we add one to the count.

for col in range(n): tries every column in the current row. For each column we compute d1 = row - col and d2 = row + col. These two numbers name the two diagonals that pass through this square. Every square on the same diagonal shares the same difference or the same sum.

if col in cols or d1 in diag1 or d2 in diag2: is the safety check. If the column is used, or either diagonal is used, the square is under attack. So we continue and skip it.

cols.add(col) and the two diagonal adds place the queen. They mark the column and both diagonals as taken. Then solve(row + 1) recurses to the next row.

The three remove calls are the backtrack. After we finish exploring this placement, we lift the queen off. We free its column and both diagonals. Now the loop can try the next column on a clean board.

⏱️ Time and Space Complexity

In the worst case we try about n choices in the first row, then fewer in each deeper row as conflicts cut branches. The rough upper bound on the time is O(n!), because the safe spots shrink row by row like a factorial. The space is O(n) for the recursion depth plus O(n) for the three sets that track columns and diagonals.

🧩 Key Takeaways

• ✅ Place exactly one queen per row, so two queens can never share a row.
• ✅ Track used columns and both diagonals so the safety check is fast.
• ✅ Two squares share a diagonal when their row minus col is equal, or their row plus col is equal.
• ✅ When a queen sits in every row, you have one full valid board.
• ✅ Place the queen, recurse, then remove it and unmark its lines to try the next column.

🚀 What’s Next?

• Word Search
• Palindrome Partitioning