LESSON 293 OF 414 · BACKTRACKING

N Queens in Rust: Backtracking Row by Row

Practice O(n!) Read the full explanation

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, and is represented as an array containing the column for each row of the matrix.

Example:

Input: n = 4
Output: [[1, 3, 0, 2], [2, 0, 3, 1]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Constraints:

1 <= n <= 9

STEP 1 OF 15

Guided

Ctrl + Enter to check

RUST · BACKTRACKING

N Queens in Rust, explained

Problem overview

The function solve_n_queens receives an i32, n (from 1 to 9), and must place n queens on an n by n chessboard so that no two attack each other. Queens attack along their row, their column and both diagonals. The function returns every distinct solution, in any order.

A solution is written as a vector of n numbers: entry r is the column of the queen in row r. For n = 4 there are two solutions, [1, 3, 0, 2] and [2, 0, 3, 1]. In the first, the queens sit at row 0 column 1, row 1 column 3, row 2 column 0 and row 3 column 2.

Approach: place one queen per row and undo bad choices

Every row must contain exactly one queen, since two queens in a row would attack each other and n queens must fit in n rows. So the search can go row by row, and for each row only the column is a choice. That cuts the search space from every placement on the board to at most n^n sequences of columns.

The technique is backtracking:

For the current row, try each column in turn.
If a queen at that square is attacked by one placed earlier, skip the column.
Otherwise place the queen, move on to the next row, and when that call comes back, remove the queen so the next column can be tried.
When the current row equals n, every row has a queen. Save a copy of the placement as a solution.

Checking a square only needs the earlier rows. A queen at (row, col) conflicts with one at (i, placement[i]) if they share a column, or if they are on the same diagonal. Two squares are on a diagonal when the row distance equals the column distance, in absolute value. The rows are different by construction, so that case needs no check.

The pruning is what makes the search small. In the 4-queens puzzle, a queen at row 0 column 0 leaves columns 2 and 3 for row 1 (column 0 shares the column and column 1 shares the diagonal). If row 1 takes column 2, every column of row 2 is attacked, so that branch is abandoned after a few steps.

Step by step

In solve_n_queens, create placements, a mutable Vec::new() that will hold every solution.
Create placement the same way: the columns chosen so far.
Start the search with Self::backtrack(n, 0, &mut placement, &mut placements), from row 0, and return placements as the final expression.
Declare backtrack with n: i32, row: usize (it indexes placement), and both vectors as mutable references so that changes are visible across calls.
Base case. If row == n as usize, push placement.clone() into placements and return. The copy is a snapshot: the original keeps changing as the search continues. The cast is needed because Rust won't compare a usize with an i32.
Loop over the columns, for col in 0..n. Since n is an i32, col is one too, matching the type stored in placement.
Test the square with Self::is_valid(placement, row, col).
Choose, explore, undo. Inside the if, placement.push(col), then Self::backtrack(n, row + 1, placement, placements), then placement.pop().
Write is_valid with the signature (placement: &[i32], row: usize, col: i32) -> bool. Loop i over 0..row and return false if placement[i] == col (same column) or the row distance equals the column distance. Cast both row and i to i32 before subtracting, and compare with .abs().
If no conflict is found, the loop ends and true is the final expression.

The solution in Rust

impl Solution {
    fn is_valid(placement: &[i32], row: usize, col: i32) -> bool {
        for i in 0..row {
            if placement[i] == col || (row as i32 - i as i32).abs() == (col - placement[i]).abs() {
                return false;
            }
        }
        true
    }

    fn backtrack(n: i32, row: usize, placement: &mut Vec<i32>, placements: &mut Vec<Vec<i32>>) {
        if row == n as usize {
            placements.push(placement.clone());
            return;
        }
        for col in 0..n {
            if Self::is_valid(placement, row, col) {
                placement.push(col);
                Self::backtrack(n, row + 1, placement, placements);
                placement.pop();
            }
        }
    }

    fn solve_n_queens(n: i32) -> Vec<Vec<i32>> {
        let mut placements = Vec::new();
        let mut placement = Vec::new();
        Self::backtrack(n, 0, &mut placement, &mut placements);
        placements
    }
}

The Rust details worth a closer look:

Type inference for the empty vectors. Vec::new() doesn't say what it holds. The compiler works it out from how the vectors are used: placements is returned as a Vec<Vec<i32>> and placement is passed where a &mut Vec<i32> is expected.
Passing &mut down. In solve_n_queens the vectors are owned, so the call uses &mut placement. Inside backtrack they are already mutable references, and they are passed to the next call as they are. Rust lends them for the call and takes them back afterwards.
A &mut Vec<i32> where a &[i32] is expected. is_valid only reads, so it takes a slice. Passing placement converts it automatically into a read-only slice, and the call compiles without any extra syntax.
clone() makes a snapshot. Pushing placement itself isn't possible, because it is a borrowed reference that keeps changing. clone() copies the numbers into a new vector, so later push and pop calls don't affect the saved solution.
pop() returns an Option. The returned value is ignored here, which the compiler allows. The vector is never empty at that point, since the push just before it added an element.
Signed arithmetic for the diagonal test. row and i are usize, so i - row would underflow, and row - i is fine only because i < row. The code casts both to i32 first, so the difference is a plain signed number and .abs() applies.
for i in 0..row. The range excludes row, so it covers exactly the rows already filled. For row 0 it is empty and the square is always valid.

Complexity

Time: exponential, with heavy pruning. Without pruning there would be n^n column sequences. The validity check cuts most branches early. Each call tests up to n columns, each test costing O(n). The number of solutions itself grows quickly: 1, 0, 0, 2, 10, 4, 40, 92 and 352 for n from 1 to 9. That is why the input is limited to 9.

Space: O(n) besides the output. The recursion is n calls deep, and placement holds at most n numbers. The output holds all the solutions, each of length n.

Edge cases and common mistakes

n = 1. One queen on a 1x1 board: the result is [[0]].
n = 2 and n = 3. No arrangement exists. The result is an empty vector, [].
Forgetting pop(). The undo step is what makes the search try other columns. Without it, the leftover queens make most squares look attacked and solutions are missed.
Checking only the column. Without the diagonal test, the search would return permutations of the columns, many of them invalid.
Diagonal test with a signed difference. Comparing row - i with col - placement[i] without .abs() catches only one of the two diagonal directions.
Order of results. Trying columns from 0 upward gives the solutions in sorted order, for example [[1, 3, 0, 2], [2, 0, 3, 1]] for n = 4. Any order is accepted.

Testing

n = 1 gives [[0]].
n = 2 gives [].
n = 4 gives [[1, 3, 0, 2], [2, 0, 3, 1]].
n = 5 gives 10 solutions, the first being [0, 2, 4, 1, 3].
n = 8 gives 92 solutions.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free