N Queen Problem Explained Simply (Step-by-Step + Easy Logic)

If you’ve ever looked at the N Queen problem and felt completely lost, you’re not alone.

At first glance, it looks confusing, complex, and full of tricky logic. But once you understand the core idea, it becomes one of the most satisfying problems in DSA.

In this guide, you’ll finally understand N Queen in the simplest way possible.

What is the N Queen Problem?

The N Queen problem is a classic problem where:

You are given an N × N chessboard.

Your goal:

Place N queens on the board such that no two queens attack each other.

How Does a Queen Attack?

A queen can attack in:

• Same row
• Same column
• Diagonals

So your placement must ensure:

• No two queens share the same row
• No two queens share the same column
• No two queens are on the same diagonal

Simple Example (4 Queens)

Let’s understand with N = 4.

We need to place 4 queens on a 4×4 board.

Valid solution looks like this:

. Q . .
. . . Q
Q . . .
. . Q .

Each row has one queen

Each column has one queen

No diagonal conflicts

Why is This Problem Important?

This is not just a random puzzle.

It teaches:

• Backtracking (very important in interviews)
• Recursion thinking
• Constraint handling

It’s also asked in:

• Coding interviews
• Competitive programming

Core Idea (Understand This Clearly)

We place queens one row at a time.

For each row:

• Try placing a queen in every column
• Check if it is safe
• If safe → move to next row
• If not → try another column

If stuck:

Backtrack and change previous placement

Step-by-Step Solution

Let’s break it down into very simple steps.

Step 1: Start with Row 0

Try placing queen in:

• Column 0
• Column 1
• Column 2
• Column 3

Step 2: Check if Position is Safe

Before placing, check:

• Same column conflict
• Left diagonal conflict
• Right diagonal conflict

Step 3: Move to Next Row

If safe:

Place queen and move to next row

Step 4: Backtracking

If no position works:

• Go back to previous row
• Move queen to next column

Step 5: Repeat Until Solution Found

Once all queens are placed:

You found a valid solution

Visual Thinking (Very Important)

Think like this:

You are exploring a tree:

• Each row = level
• Each column = choice

You try all possibilities, but only keep valid ones.

Code (C++ Simple Version)

bool isSafe(vector<string>& board, int row, int col, int n) {
    for(int i = 0; i < row; i++)
        if(board[i][col] == 'Q')
            return false;

    for(int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--)
        if(board[i][j] == 'Q')
            return false;

    for(int i = row-1, j = col+1; i >= 0 && j < n; i--, j++)
        if(board[i][j] == 'Q')
            return false;

    return true;
}

void solve(int row, vector<string>& board, int n) {
    if(row == n) {
        // print solution
        return;
    }

    for(int col = 0; col < n; col++) {
        if(isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            solve(row + 1, board, n);
            board[row][col] = '.';
        }
    }
}

Real-Life Analogy (Makes It Easy)

Imagine:

• Each row is a person
• Each column is a seat

You must seat everyone such that:

• No one conflicts with others

If conflict happens:

You change seating (backtracking)

Pro Tips (To Master N Queen)

1. Always Think Row by Row

Never try random placements.

2. Optimize Checking

Use arrays to track:

• Columns
• Diagonals

3. Practice Smaller Inputs

Start with:

• N = 4
• N = 5

4. Understand Backtracking Pattern

This pattern is used in:

• Sudoku
• Permutations
• Combinations

Common Mistakes

Mistake 1: Not Understanding Diagonals

Most beginners ignore diagonal checks.

Mistake 2: Forgetting Backtracking

You must undo the move.

Mistake 3: Wrong Index Handling

Diagonal logic often causes errors.

Mistake 4: Trying Brute Force Without Pruning

This makes solution very slow.

Time Complexity

Worst case:

O(N!)

But with pruning, it becomes efficient enough for typical constraints.

Advanced Optimization (For Interviews)

Use:

• Hash arrays for columns
• Left diagonal array
• Right diagonal array

This reduces checking time to O(1)

Why This Problem Feels Hard (But Isn’t)

It feels hard because:

• Too many possibilities
• Requires recursive thinking

But in reality:

It’s just:

Try → Check → Move → Backtrack

Final Thoughts

The N Queen problem is one of the best problems to understand backtracking deeply.

Once you master this, many other problems become easier.

FAQ

Q1: Is N Queen problem important for interviews?

Yes, it is a standard backtracking problem frequently asked.

Q2: What algorithm is used in N Queen?

Backtracking with recursion.

Q3: Why is N Queen difficult?

Because it involves multiple constraints and recursion.

Q4: What is time complexity?

Approximately O(N!).

Q5: How to master N Queen?

Practice backtracking problems regularly.