N-Queens
Find every arrangement of n queens on an n by n board where no two share a row, column, or diagonal. Reflections and rotations are distinct solutions.
Work through the cases
3 examplesInput notation
An integer n from 1 through 9.Expected result
Print each board as n rows using Q and dots. Separate boards with a blank line; any board order is valid. Print none if impossible.Case 1
Input
4
Expected output
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
Case 2
Input
2
Expected output
none
Case 3
Input
1
Expected output
Q
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is to try every column permutation: put the queen in row i at column p_i, then check diagonals. n ≤ 9, so 9! is searchable, but we only discover a conflict after the board is full, and we still have to build the string grid. The waste is placing everything, then validating. One queen per row is mandatory; conflicts are only the same column or the same diagonal. Column, i+j, and n-i+j can all be marked in O(1). So we DFS row by row: place and mark only when legal, then backtrack. The board g flips 'Q'/'.' in lockstep; at row n we copy one answer.
We define three arrays col, dg, and udg to represent whether there is a queen in the column, the main diagonal, and the anti-diagonal, respectively. If there is a queen at position (i, j), then col[j], dg[i + j], and udg[n - i + j] are all 1. In addition, we use an array g to record the current state of the chessboard, where all elements in g are initially '.'.
Next, we define a function dfs(i), which represents placing queens starting from the ith row.
In dfs(i), if i = n, it means that we have completed the placement of all queens. We put the current g into the answer array and end the recursion.
Otherwise, we enumerate each column j of the current row. If there is no queen at position (i, j), that is, col[j], dg[i + j], and udg[n - i + j] are all 0, then we can place a queen, that is, change g[i][j] to 'Q', and set col[j], dg[i + j], and udg[n - i + j] to 1. Then we continue to search the next row, that is, call dfs(i + 1). After the recursion ends, we need to change g[i][j] back to '.' and set col[j], dg[i + j], and udg[n - i + j] to 0.
In the main function, we call dfs(0) to start recursion, and finally return the answer array.
The time complexity is O(n^2 × n!), and the space complexity is O(n). Here, n is the integer given in the problem.
class Solution {
private List<List<String>> ans = new ArrayList<>();
private int[] col;
private int[] dg;
private int[] udg;
private String[][] g;
private int n;
public List<List<String>> solveNQueens(int n) {
this.n = n;
col = new int[n];
dg = new int[n << 1];
udg = new int[n << 1];
g = new String[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], ".");
}
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == n) {
List<String> t = new ArrayList<>();
for (int j = 0; j < n; ++j) {
t.add(String.join("", g[j]));
}
ans.add(t);
return;
}
for (int j = 0; j < n; ++j) {
if (col[j] + dg[i + j] + udg[n - i + j] == 0) {
g[i][j] = "Q";
col[j] = dg[i + j] = udg[n - i + j] = 1;
dfs(i + 1);
col[j] = dg[i + j] = udg[n - i + j] = 0;
g[i][j] = ".";
}
}
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.