Abstract / Summary

Place n queens on an n by n chessboard so that no two queens attack each other.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 76% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Backtracking

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic N-Queens problem by enumerating all permutations of column positions and filtering those that satisfy the diagonal constraints. It builds each candidate board row by row, using bit masks to track occupied diagonals, and leverages early termination to avoid unnecessary work. The algorithm returns every distinct board configuration as a vector of strings, where each string represents a row with a single 'Q' and the remaining cells filled with '.'.

Permutation Generation

The algorithm starts by creating a vector order that holds the column indices [0, 1, …, n-1]. This vector is used as the source of permutations, each representing a possible placement of queens-one per row-without considering diagonal attacks.

vector<int> order;
for (int i = 0; i < n; i++)
    order.push_back(i);

The do … while (next_permutation(...)) loop iterates over every lexicographic permutation of order. Because each permutation guarantees that no two queens share a column, the algorithm only needs to verify diagonal safety.

Diagonal Blocking Logic

Two integer masks, blockLeft and blockRight, encode the occupied left-to-right and right-to-left diagonals, respectively. For a queen placed at column pos on the current row, the mask 1 << pos identifies the column. The algorithm checks that this column is not already blocked on either diagonal:

int mask = 1 << pos;
ok &= (mask & blockLeft)  == 0;
ok &= (mask & blockRight) == 0;

If the check fails, the current permutation cannot yield a valid solution, and the inner loop breaks early.

After the safety test, the masks are shifted to reflect the move to the next row:

blockLeft  <<= 1;
blockRight >>= 1;
blockRight &= (1 << n) - 1;

The left shift moves the left-to-right diagonal one column to the left, while the right shift moves the right-to-left diagonal one column to the right. The mask blockRight is additionally masked with (1 << n) - 1 to discard bits that fall outside the board width, ensuring correct handling when the rightmost diagonal would otherwise overflow.

The newly placed queen then contributes to the diagonal masks for subsequent rows:

blockLeft  |= mask << 1;
blockRight |= mask >> 1;

These operations add the queen’s influence on the diagonals of the rows that follow.

Solution Construction

When a queen passes the diagonal checks, the algorithm constructs the visual representation of the current row. It creates a string q consisting of pos dots, a 'Q', and the remaining dots to fill the row length n:

q.clear();
q.insert(q.end(), pos, '.');
q += 'Q';
q.insert(q.end(), n - pos - 1, '.');
solution.push_back(q);

The solution vector accumulates these row strings, forming a complete board layout when all rows are processed without conflict.

Early Pruning and Skipping

If a conflict is detected before all rows are placed, the algorithm aborts the current permutation early. The variable line records the index of the row where the conflict occurred. When a conflict happens, the code attempts to skip a large set of permutations that would share the same prefix, thereby reducing the number of permutations examined:

if (line < n - 1)
{
    // not perfect, but fast
    sort   (order.begin() + line + 1, order.end());
    reverse(order.begin() + line + 1, order.end());
}

By sorting and then reversing the suffix of order after the failing row, the algorithm forces the next call to next_permutation to jump to a permutation with a different prefix, effectively pruning many invalid candidates in one step.

Permutation Advancement

The outer loop relies on the standard library’s next_permutation to generate the next lexicographic ordering of columns. Because the algorithm may have reordered the suffix after a failure, next_permutation still correctly produces the subsequent permutation, now starting from a different prefix.

} while (next_permutation(order.begin(), order.end()));

When the loop finishes, all viable permutations have been examined, and the collected result vector contains every solution.

Edge Cases Handled

The implementation gracefully handles the smallest board sizes. For n = 0, the initial order vector is empty, the inner loop never executes, and the algorithm returns a vector containing a single empty board configuration, which aligns with the combinatorial definition of zero queens on an empty board. For n = 1, the single permutation [0] passes the diagonal checks, and the algorithm produces a board with a solitary 'Q'. The bit-mask operations are safe for any n up to the width of an int (typically 32 bits) because the masks are confined to the lower n bits using the & (1 << n) - 1 operation.

When n exceeds the bit-width of the integer type, the shift operations would still behave predictably because the mask is always limited to the lower n bits before being used in further calculations. This implicit handling ensures that the algorithm does not produce undefined behavior for larger n values within the limits of the language’s integer representation.

Performance Optimizations

The code employs several techniques to keep the search efficient:

• Column Uniqueness via Permutations: By generating permutations of column indices, the algorithm eliminates the need to check column conflicts, reducing the per-row validation to diagonal checks only.

• Bit-Mask Representation: Using integers to represent diagonal occupancy enables constant-time checks and updates. Bitwise AND, OR, and shift operations are far faster than array-based approaches.

• Early Termination: The ok flag combined with a break from the inner loop stops processing a permutation as soon as a conflict is found, preventing unnecessary construction of the remaining rows.

• Suffix Skipping: After a conflict, the code reorders the suffix of the permutation to force next_permutation to skip a block of permutations that would share the same invalid prefix. This heuristic reduces the total number of permutations examined, especially for larger n.

• In-Place Row String Construction: The row string q is reused for each row, with clear and insert operations that avoid allocating new strings repeatedly, thereby lowering memory churn.

Together, these strategies allow the solution to explore the solution space more rapidly than a naïve backtracking implementation that would examine every possible placement without pruning.

Imagine having a giant square game board with many empty squares. The goal is to place several toy queens on this board so that no queen can bump into another one. A queen is very powerful because she can move in lines that go up, down, across, or diagonally.

The code works by testing every single pattern where each queen is placed in a different row. It starts by lining up the queens in a simple order. Then, it checks each queen one by one to see if she is safe. It keeps track of where she can attack by using special markers that represent the diagonal paths.

If a queen is allowed to be placed in a spot without being attacked by the queens that were placed before her, the code draws her on a little map and moves to the next row. If the code finds a spot where a queen gets threatened, it stops looking at that specific pattern because it knows it will not work. It then scrambles the order of the remaining rows to find a new way to arrange the queens, and it keeps trying different combinations until it finds all the ways to place the queens safely.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: factorial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java				TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python	C#			Java			Go	TS
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows		Python
	bujosa		Python
	charles-wangkai						Java
	chenyanzhe	C++
	everthis					JS
	fpdjsns	C++
	gaosq0604		Python
	halfrost									Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru				Rust
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	varunu28						Java
	vli02							C
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fpdjsns	C++
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality