LearnViz CompSci
Home / Learn / Algorithms / N-Queens Problem

Intermediate Topic 30 of 51 Algorithms

N-Queens Problem

Placing queens on a board so none attack each other.

How it works

The N-Queens problem asks for a placement of N queens on an N by N chessboard so that no two attack each other, meaning no two share a row, column or diagonal. A backtracking solution places one queen per row and tests columns, using sets or bit masks for used columns and the two diagonal directions, abandoning rows where no safe column remains.

Step-by-step walkthrough

  1. Place one queen per row on a 4 by 4 board.
  2. Row 1 gets a queen in column 2.
  3. Row 2 can only use column 4.
  4. Row 3 has no safe column, so backtrack and move the row 2 queen.
  5. Eventually the layout columns 2 4 1 3 puts every queen safely.

Where it is used

It is a classic exercise for backtracking, constraint satisfaction and parallel search, and has been used to benchmark solvers. The number of solutions grows quickly, for example 92 for N equal to 8.

Common pitfall

Checking safety by scanning the whole board each time is slow; track columns and diagonals in constant time. Diagonal indexes are computed with row minus column and row plus column. Counting versus printing all solutions changes the memory needed. Exploit symmetry to halve the work.

Where it fits in the course

N-Queens Problem is topic 30 of 51 in Algorithms, rated Intermediate. It follows Backtracking. The next topic is Breadth-First Search.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Algorithms quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is N-Queens Problem?
Placing queens on a board so none attack each other. It belongs to Algorithms and is an intermediate-level topic.
Where do people use N-Queens Problem?
It is a classic exercise for backtracking, constraint satisfaction and parallel search, and has been used to benchmark solvers.
What is the most common mistake with N-Queens Problem?
Checking safety by scanning the whole board each time is slow; track columns and diagonals in constant time.
What should I learn before this topic?
Start with Backtracking, the topic just before it in Algorithms.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Algorithms quiz.
Is N-Queens Problem hard to learn?
It is an Intermediate topic. Be comfortable with the Beginner topics in this area first, then read the common pitfall carefully, since it is where most mistakes happen.
How long does it take to learn N-Queens Problem?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to N-Queens Problem?
Backtracking, Breadth-First Search, Edit Distance are closely connected. The full list is in the related topics section of this page.
What should I study after N-Queens Problem?
Continue with Breadth-First Search, the next topic in Algorithms.

Related topics