051. N-Queens

At a Glance

Topic: backtracking
Pattern: DFS / Backtracking (also bit-pruning variant: Bit Manipulation)
Difficulty: Hard
Companies: Amazon, Google, Meta, Microsoft, Apple
Frequency: High
LeetCode: 51

Problem (one-liner)

Place n queens on an n x n chessboard so no two attack each other (same row, column, or diagonal). Return every distinct valid board as a list of strings ('.' and 'Q').

Recognition Cues

"All solutions" / "every configuration" — exhaustive search with pruning, not greedy
Chess queens — rows/columns/diagonals conflict — place row-by-row, track forbidden columns and both diagonal families
Board size up to ~9 — implicit acceptance of exponential backtracking with pruning

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — enumerate all n^n or subset placements — astronomically bad.
Backtracking with validity scan — try each column per row, check all prior queens — O(n!)-ish with heavy overlap — workable only with small n.
Optimal (standard) — place one queen per row; maintain occupied columns and diagonal identifiers to test conflicts in O(1) — same asymptotic but much faster constants.
Bit-pruning variant — pack column / diagonal / anti-diagonal masks into integers — fewer allocations; same worst-case time, faster in practice for tight budgets.

Place one queen per row. Standard solution uses boolean arrays for column and both diagonal families (row ± col). A faster constant-factor variant packs those masks into integers (Bit Manipulation): for LeetCode constraints n ≤ 9, a single int mask suffices.

Go (column + diagonal arrays)

package main

func solveNQueens(boardSize int) [][]string {
	result := [][]string{}
	board := make([][]byte, boardSize)
	for rowIndex := range board {
		board[rowIndex] = make([]byte, boardSize)
		for columnIndex := range board[rowIndex] {
			board[rowIndex][columnIndex] = '.'
		}
	}

	columns := make([]bool, boardSize)
	diagonal := make([]bool, 2*boardSize-1)     // row + column
	antiDiagonal := make([]bool, 2*boardSize-1) // row - column + offset

	var backtrack func(rowIndex int)
	backtrack = func(rowIndex int) {
		if rowIndex == boardSize {
			snapshot := make([]string, boardSize)
			for copyRow := 0; copyRow < boardSize; copyRow++ {
				snapshot[copyRow] = string(board[copyRow])
			}
			result = append(result, snapshot)
			return
		}

		for columnIndex := 0; columnIndex < boardSize; columnIndex++ {
			diagonalIndex := rowIndex + columnIndex
			antiDiagonalIndex := rowIndex - columnIndex + boardSize - 1
			if columns[columnIndex] || diagonal[diagonalIndex] || antiDiagonal[antiDiagonalIndex] {
				continue
			}
			columns[columnIndex] = true
			diagonal[diagonalIndex] = true
			antiDiagonal[antiDiagonalIndex] = true
			board[rowIndex][columnIndex] = 'Q'

			backtrack(rowIndex + 1)

			board[rowIndex][columnIndex] = '.'
			columns[columnIndex] = false
			diagonal[diagonalIndex] = false
			antiDiagonal[antiDiagonalIndex] = false
		}
	}

	backtrack(0)
	return result
}

Go (bitmask pruning, same worst-case time)

package main

import "math/bits"

// Bitmasks encode occupied columns and both diagonal directions; picking the lowest
// set bit in "available" explores placements without allocating []bool per depth.
func solveNQueensBitmasks(boardSize int) [][]string {
	const maxBoard = 32
	if boardSize > maxBoard {
		return nil
	}
	allColumnsMask := (1 << boardSize) - 1
	result := [][]string{}
	columnPlacement := make([]int, boardSize)

	var search func(rowIndex int, columnsMask int, diagonalMask int, antiDiagonalMask int)
	search = func(rowIndex int, columnsMask int, diagonalMask int, antiDiagonalMask int) {
		if rowIndex == boardSize {
			board := make([]string, boardSize)
			for placementRow := 0; placementRow < boardSize; placementRow++ {
				line := make([]byte, boardSize)
				for columnIndex := range line {
					line[columnIndex] = '.'
				}
				columnIndex := bits.TrailingZeros(uint(columnPlacement[placementRow]))
				line[columnIndex] = 'Q'
				board[placementRow] = string(line)
			}
			result = append(result, board)
			return
		}
		occupied := columnsMask | diagonalMask | antiDiagonalMask
		available := allColumnsMask &^ occupied
		for available != 0 {
			lowestBit := available & -available
			columnPlacement[rowIndex] = lowestBit
			search(
				rowIndex+1,
				columnsMask|lowestBit,
				(diagonalMask|lowestBit)<<1,
				(antiDiagonalMask|lowestBit)>>1,
			)
			available -= lowestBit
		}
	}

	search(0, 0, 0, 0)
	return result
}

JavaScript

/**
 * @param {number} boardSize
 * @return {string[][]}
 */
function solveNQueens(boardSize) {
	const result = [];
	const board = Array.from({ length: boardSize }, () =>
		Array.from({ length: boardSize }, () => '.')
	);
	const columns = Array(boardSize).fill(false);
	const diagonal = Array(2 * boardSize - 1).fill(false);
	const antiDiagonal = Array(2 * boardSize - 1).fill(false);

	function backtrack(rowIndex) {
		if (rowIndex === boardSize) {
			result.push(board.map((row) => row.join('')));
			return;
		}
		for (let columnIndex = 0; columnIndex < boardSize; columnIndex++) {
			const diagonalIndex = rowIndex + columnIndex;
			const antiDiagonalIndex = rowIndex - columnIndex + boardSize - 1;
			if (columns[columnIndex] || diagonal[diagonalIndex] || antiDiagonal[antiDiagonalIndex]) {
				continue;
			}
			columns[columnIndex] = true;
			diagonal[diagonalIndex] = true;
			antiDiagonal[antiDiagonalIndex] = true;
			board[rowIndex][columnIndex] = 'Q';
			backtrack(rowIndex + 1);
			board[rowIndex][columnIndex] = '.';
			columns[columnIndex] = false;
			diagonal[diagonalIndex] = false;
			antiDiagonal[antiDiagonalIndex] = false;
		}
	}

	backtrack(0);
	return result;
}

JavaScript (bitmask variant, `n ≤ 32`)

function solveNQueensBitmasks(boardSize) {
	const allColumnsMask = (1 << boardSize) - 1;
	const result = [];
	const columnPlacement = new Array(boardSize);

	function search(rowIndex, columnsMask, diagonalMask, antiDiagonalMask) {
		if (rowIndex === boardSize) {
			const board = [];
			for (let placementRow = 0; placementRow < boardSize; placementRow++) {
				const line = Array(boardSize).fill('.');
				const bit = columnPlacement[placementRow];
				const columnIndex = Math.trunc(Math.log2(bit));
				line[columnIndex] = 'Q';
				board.push(line.join(''));
			}
			result.push(board);
			return;
		}
		let available = allColumnsMask & ~(columnsMask | diagonalMask | antiDiagonalMask);
		while (available !== 0) {
			const lowestBit = available & -available;
			columnPlacement[rowIndex] = lowestBit;
			search(
				rowIndex + 1,
				columnsMask | lowestBit,
				(diagonalMask | lowestBit) << 1,
				(antiDiagonalMask | lowestBit) >>> 1
			);
			available -= lowestBit;
		}
	}

	search(0, 0, 0, 0);
	return result;
}

Walkthrough

n = 4. Row 0: try columns 0..3. Pick 1: mark column 1, diagonals (0+1) and (0-1+3). Row 1: skip conflicting columns; place at 3. Continue until row 4 → record board. Backtrack removes marks so sibling branches explore other column choices.

Invariant: After placing rowIndex queens, arrays columns, diagonal, antiDiagonal encode exactly the occupied rank/file/diagonal constraints for all rows < rowIndex.

Edge Cases

n = 1 — single ["Q"]
No solution for n = 2 or n = 3 — return []
n = 4 — smallest nontrivial case with two symmetry-related families of solutions
Large n — exponential blow-up; interviewer may ask for count only (same search, no materialization)

Pitfalls

Confusing the two diagonal directions (row + col vs row - col) or wrong offset for negative row - col
Forgetting to unmark on backtrack — silent duplication or missed solutions
Allocating a new board per recursion depth unnecessarily — reuse one buffer + deep copy only on success

Variants

Count only (LeetCode 52) — same search, return len(solutions); bitmasks avoid building [][]string at leaves
Stop at first solution — early exit after one complete placement (interview speed check)
Unique up to symmetry — quotient by D4 relabelings to dedupe solution families in enumeration tasks
Array vs bit tradeoff — []bool is clearer in interviews; bitmasks win when n approaches the stack limit of allocations or in hot loops (always state the n ≤ 32 / two’s-complement assumption)

Mind-Map Tags

#backtracking #chess #diagonals #constraint-pruning #bitmasks-optional #exhaustive-search