N-Queens II - Practice Coding Problems

N-Queens II - Problem

Backtracking Hard

The N-Queens puzzle is a classic backtracking problem where you need to place n chess queens on an n × n chessboard such that no two queens can attack each other.

Two queens attack each other if they are:

On the same row
On the same column
On the same diagonal (both main diagonal and anti-diagonal)

Given an integer n, return the number of distinct solutions to the N-Queens puzzle.

Input & Output

Example 1 — Small Board

$ Input: n = 4

› Output: 2

💡 Note: There are exactly 2 distinct solutions for a 4×4 board. Solution 1: queens at positions (0,1), (1,3), (2,0), (3,2). Solution 2: queens at positions (0,2), (1,0), (2,3), (3,1).

Example 2 — Minimal Board

$ Input: n = 1

› Output: 1

💡 Note: For n=1, there's only one cell on the board, so exactly 1 solution: place the single queen at position (0,0).

Example 3 — Impossible Case

$ Input: n = 2

› Output: 0

💡 Note: On a 2×2 board, it's impossible to place 2 queens without them attacking each other. Any placement results in queens sharing a row, column, or diagonal.

Constraints

1 ≤ n ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

Board size n=4

Process

Find all valid queen placements

Output

Count of distinct solutions: 2

Key Takeaway

🎯 Key Insight: Use backtracking with sets to efficiently count all valid N-Queens arrangements

Asked in

G Google 25 a Amazon 20 M Microsoft 15 🍎 Apple 10

The key insight is using backtracking with efficient conflict detection. Track occupied columns and diagonals in sets for O(1) conflict checking. Best approach is optimized backtracking with sets. Time: O(n!), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Basic Backtracking	O(n!)	O(n)	Try placing queens row by row, backtrack when conflicts arise
Optimized Backtracking with Sets	O(n!)	O(n)	Use sets to track attacked columns and diagonals for O(1) conflict detection
Generate All Permutations	O(n!)	O(n)	Generate every possible placement of n queens and check validity

Basic Backtracking — Algorithm Steps

Place queen in current row
Check conflicts with previous queens
If valid, recurse to next row
If invalid or dead-end, backtrack

Visualization

Tap to expand

Step-by-Step Walkthrough

Place Row 0

Try each column in first row

Check Conflicts

Validate against previous queens

Backtrack

Remove queen if no valid placement found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isSafe(int* board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
            return false;
        }
    }
    return true;
}

int solve(int* board, int row, int n) {
    if (row == n) {
        return 1;
    }
    
    int count = 0;
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col;
            count += solve(board, row + 1, n);
        }
    }
    return count;
}

int solution(int n) {
    int* board = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        board[i] = -1;
    }
    
    int result = solve(board, 0, n);
    free(board);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

In worst case explores all permutations, but with pruning

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth n plus board state

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Basic Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler