Problem Statement

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 the number of distinct solutions to the n-queens puzzle.

LeetCode

• https://leetcode.com/problems/n-queens-ii/description/

Constraints

1 <= n <= 9

Examples

Example 1:

Input: n = 4
Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

Different Approaches

1️⃣ Recursion (Backtracking)

Code:

class Solution {
public:
    // Check upward column
    bool isValidUpward(vector<string>& board, int row, int col) {
        while (row >= 0) {
            if (board[row][col] == 'Q') return false;
            row--;
        }
        return true;
    }

    // Check upward-right diagonal
    bool isValidDiagonalRight(vector<string>& board, int row, int col, int n) {
        while (row >= 0 && col < n) {
            if (board[row][col] == 'Q') return false;
            row--;
            col++;
        }
        return true;
    }

    // Check upward-left diagonal
    bool isValidDiagonalLeft(vector<string>& board, int row, int col) {
        while (row >= 0 && col >= 0) {
            if (board[row][col] == 'Q') return false;
            row--;
            col--;
        }
        return true;
    }

    // Check if placing at (row, col) is safe
    bool isValid(vector<string>& board, int row, int col, int n) {
        return isValidUpward(board, row, col) &&
               isValidDiagonalRight(board, row, col, n) &&
               isValidDiagonalLeft(board, row, col);
    }

    // Backtracking function to count all valid boards
    void solve(int& count, vector<string>& board, int row, int n) {
        if (row == n) {
            count++;  // Found a valid configuration
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col, n)) {
                board[row][col] = 'Q';        // Place queen
                solve(count, board, row + 1, n);  // Recurse
                board[row][col] = '.';        // Backtrack
            }
        }
    }

    int totalNQueens(int n) {
        int count = 0;
        vector<string> board(n, string(n, '.'));  // n x n empty board
        solve(count, board, 0, n);
        return count;
    }
};

Complexity Analysis:

• Time Complexity:O(n!) — each queen has up to n choices, reduced as we go deeper.
• Space Complexity:O(n^2) for the board, O(n) recursion stack.