Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Recursion & Backtracking

N-Queens Count

Hard · Recursion & Backtracking · Asked at Amazon, Google, Microsoft, Adobe

Count the ways to place n queens on an n × n chessboard so that no two queens attack each other.

Input

One integer n.

Output

The number of solutions.

Constraints

Place one queen per row; track used columns and both diagonals.

Example 1

Input

4

Output

2

Example 2

Input

1

Output

1

Hints

  1. Each row must contain exactly one queen — place them row by row.
  2. A square (r, c) is attacked if its column, its "r − c" diagonal or its "r + c" anti-diagonal is already used. Track all three with boolean arrays.

Approach

place(row): if row == n, one full solution is found. Otherwise try each column c where col[c], diag[row − c + n − 1] and anti[row + c] are all free. Mark them, recurse to the next row, then unmark (backtrack). The boolean arrays make each safety check O(1), and pruning keeps the search small: n = 10 has 724 solutions.

Complexity: O(n!) worst-case time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int n, solutions = 0;
vector<bool> col, diag, anti;

void place(int row) {
    if (row == n) {
        solutions++;
        return;
    }
    for (int c = 0; c < n; c++) {
        if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
        col[c] = diag[row - c + n - 1] = anti[row + c] = true;
        place(row + 1);
        col[c] = diag[row - c + n - 1] = anti[row + c] = false;
    }
}

int main() {
    cin >> n;
    col.assign(n, false);
    diag.assign(2 * n, false);
    anti.assign(2 * n, false);
    place(0);
    cout << solutions << "\n";
    return 0;
}

Python solution

n = int(input())
col, diag, anti = [False] * n, [False] * (2 * n), [False] * (2 * n)


def place(row):
    if row == n:
        return 1
    count = 0
    for c in range(n):
        d, a = row - c + n - 1, row + c
        if col[c] or diag[d] or anti[a]:
            continue
        col[c] = diag[d] = anti[a] = True
        count += place(row + 1)
        col[c] = diag[d] = anti[a] = False
    return count


print(place(0))

Java solution

import java.util.*;

public class Main {
    static int n, solutions = 0;
    static boolean[] col, diag, anti;

    static void place(int row) {
        if (row == n) {
            solutions++;
            return;
        }
        for (int c = 0; c < n; c++) {
            if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
            col[c] = diag[row - c + n - 1] = anti[row + c] = true;
            place(row + 1);
            col[c] = diag[row - c + n - 1] = anti[row + c] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        col = new boolean[n];
        diag = new boolean[2 * n];
        anti = new boolean[2 * n];
        place(0);
        System.out.println(solutions);
    }
}

Solve N-Queens Count online · All practice problems