-
Notifications
You must be signed in to change notification settings - Fork 0
109 — N Queens
LeetCode 51 · Hard. The n-queens puzzle is the problem of placing n chess queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions, each represented as a list of strings where 'Q' marks a queen and '.' marks an empty space.
A queen attacks along its entire row, column, and both diagonals — so the very first useful observation is that no two queens can ever share a row, which means the search can place exactly one queen per row and never has to reconsider that choice. That collapses the problem from "choose n cells out of n²" down to "choose one column per row," which is already backtracking's bread and butter: one decision per level, with the previous decisions constraining which choices remain legal.
"Place n queens such that no two attack each other, return all distinct solutions" is the cue: a placement problem with pairwise conflict constraints (row, column, and both diagonals) is a backtracking search — one placement per row, validity re-checked against everything placed so far, backtrack the instant a placement is unsafe.
Place one queen per row (already necessary just to keep the search tractable), but validate each candidate placement with a full board rescan — check every previously placed queen, row by row and column by column, for a conflict — instead of tracking conflicts directly.
func solveNQueensBruteForce(_ n: Int) -> [[String]] {
var results: [[String]] = []
var board = Array(repeating: Array(repeating: Character("."), count: n), count: n)
func isSafe(_ row: Int, _ col: Int) -> Bool {
// Full board scan: re-examine every cell of every previously placed row.
for r in 0..<row {
for c in 0..<n {
if board[r][c] == "Q" {
if c == col { return false }
if abs(r - row) == abs(c - col) { return false }
}
}
}
return true
}
func backtrack(_ row: Int) {
if row == n {
results.append(board.map { String($0) })
return
}
for col in 0..<n {
if isSafe(row, col) {
board[row][col] = "Q"
backtrack(row + 1)
board[row][col] = "."
}
}
}
backtrack(0)
return results
}
// smoke test
print(solveNQueensBruteForce(4).count) // 2
print(solveNQueensBruteForce(1)) // [["Q"]]
print(solveNQueensBruteForce(2).count) // 0
print(solveNQueensBruteForce(3).count) // 0Big-O: roughly O(n!) placements explored (same combinatorial shape as the optimal version), but each isSafe call costs up to O(n · row) — scanning every cell of every previously placed row — instead of O(1), making the true cost closer to O(n! · n²).
Track occupied columns and both diagonal families with sets, so checking whether a placement is safe is an O(1) membership test instead of a board rescan. A queen at (row, col) occupies diagonal row - col (constant along a ↘ diagonal) and anti-diagonal row + col (constant along a ↙ diagonal).
func solveNQueens(_ n: Int) -> [[String]] {
var results: [[String]] = []
var columns = Set<Int>()
var diagonals = Set<Int>()
var antiDiagonals = Set<Int>()
var queenCols = [Int](repeating: -1, count: n) // queenCols[row] = column of the queen in that row
func backtrack(_ row: Int) {
if row == n {
let board = (0..<n).map { r -> String in
var line = [Character](repeating: ".", count: n)
line[queenCols[r]] = "Q"
return String(line)
}
results.append(board)
return
}
for col in 0..<n {
let diag = row - col
let antiDiag = row + col
if columns.contains(col) || diagonals.contains(diag) || antiDiagonals.contains(antiDiag) {
continue // prune: O(1) conflict check, no rescanning previously placed queens
}
columns.insert(col)
diagonals.insert(diag)
antiDiagonals.insert(antiDiag)
queenCols[row] = col
backtrack(row + 1)
columns.remove(col)
diagonals.remove(diag)
antiDiagonals.remove(antiDiag)
}
}
backtrack(0)
return results
}
// smoke test — same cases as the brute force
print(solveNQueens(4).count) // 2
print(solveNQueens(1)) // [["Q"]]
print(solveNQueens(2).count) // 0
print(solveNQueens(3).count) // 0Big-O: roughly O(n!) placements explored, each validated in O(1) via three set lookups instead of an O(n · row) rescan — the true cost stays close to O(n!) instead of ballooning to O(n! · n²).
Both versions explore essentially the same shape of search tree — one queen per row, backtracking the instant a column runs out of safe placements. The gap is entirely in the cost of answering "is this placement safe?" The brute force answers that question by re-deriving it from scratch every time: loop over every previously placed queen and check for a column or diagonal collision. The optimal version instead maintains the answer incrementally — inserting into columns, diagonals, and antiDiagonals when a queen is placed, and removing on backtrack — so "is this placement safe" becomes three O(1) set lookups instead of an O(n)-per-row rescan. Multiply that per-placement savings by O(n!) placements, and the constant-factor difference becomes the difference between "runs instantly" and "runs, but visibly slower," for even modest n.
- DFS and Backtracking — one decision per row, pruned before recursing, is the same choose/recurse/un-choose shape as every other problem in this chapter, just with the diagonal bookkeeping as the twist.
-
Arrays and Strings —
queenColsbuilds up the final board representation incrementally, one row at a time, mirroring thepatharray used throughout this batch.
N-Queens is one queen per row — track which columns and diagonals are already spoken for in O(1) sets, instead of re-scanning the whole board to answer "is this placement safe?" every single time.
- Why does a queen at
(row, col)always share the samerow - colvalue with every other queen on its↘diagonal, and the samerow + colvalue with every queen on its↙diagonal? -
solveNQueens(2)andsolveNQueens(3)both return zero solutions. Convince yourself (by reasoning about the board, not by running code) why no safe arrangement exists for either size. - If you removed the
columns/diagonals/antiDiagonalscleanup lines (the.remove(...)calls afterbacktrack(row + 1)) from the optimal version, what would go wrong — and would the bug show up immediately, or only on boards where backtracking actually has to happen?
⬅️ Previous: Letter Combinations of a Phone Number · Next: Number of Islands ➡️