✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-154

N-Queens Problem

The N-Queens problem asks how to place N queens on an N × N chessboard so that no two queens attack one another. Since a queen can attack along rows, columns, and diagonals, a valid arrangement must contain exactly one queen in each row and column, with no shared diagonal. Backtracking solves the problem by placing one queen at a time and abandoning placements that create conflicts.

Explanation

Overview

The N-Queens problem is a classic constraint-satisfaction and combinatorial search problem. Its objective is to find one or all arrangements of N queens on an N × N board such that no pair of queens occupies the same row, column, or diagonal.

Key concepts

name: Core idea; description: The central focus of n-queens problem is the capability described here: The N-Queens problem asks how to place N queens on an N × N chessboard so that no two queens attack one another. Since a queen can attack along rows, columns, and diagonals, a valid arrangement must contain exactly one queen in each row and column, with no shared diagonal. Backtracking solves the problem by placing one queen at a time and abandoning placements that create conflicts.; name: Problem context; description: N-Queens Problem is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using n-queens problem, check its assumptions, input requirements, expected output, and resource constraints.

Complexity

searchBound: A straightforward row-by-row implementation has an O(N!) upper bound on the number of partial arrangements explored when columns are chosen without repetition.; conflictChecking: Using sets for columns and diagonals gives expected O(1) conflict checks per candidate.; solutionStorage: Storing all solutions requires additional memory proportional to the number of solutions multiplied by the board representation size.; importantNote: The exact running time depends on whether the algorithm finds one solution or enumerates all solutions, and whether symmetry reduction or additional pruning is used.

Example

scenario: A software feature needs to use n-queens problem.; task: Design a small, testable solution that demonstrates n-queens problem while satisfying the requirements described in this entry.; approach: Identify the input and expected output, apply the central idea of n-queens problem, and trace the result with a small representative dataset.; learningPoint: This n-queens problem example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Applications

Designing and implementing solutions involving n-queens problem.; Teaching and assessing n-queens problem in computer-science courses and interviews.; Checking solutions that use n-queens problem against correctness and resource constraints.

Limitations

The suitability of n-queens problem depends on the exact problem requirements and the assumptions made about the input.; An implementation of n-queens problem can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For n-queens problem, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Common mistakes

Checking only rows and columns while forgetting diagonal attacks.; Using row + column for both diagonal directions.; Forgetting to remove a queen from the conflict sets during backtracking.; Saving a reference to a mutable board instead of copying it.; Treating mirrored or rotated boards as identical when the task requires all distinct arrangements.

Example or application

Scenario

A software feature needs to use n-queens problem.

Task

Design a small, testable solution that demonstrates n-queens problem while satisfying the requirements described in this entry.

Approach

Identify the input and expected output, apply the central idea of n-queens problem, and trace the result with a small representative dataset.

Learning Point

This n-queens problem example should be checked with ordinary inputs, boundary conditions, and a case that could expose an incorrect assumption.

Definition

The N-Queens problem is a classic constraint-satisfaction and combinatorial search problem. Its objective is to find one or all arrangements of N queens on an N × N board such that no pair of queens occupies the same row, column, or diagonal.

Constraints

  • Exactly one queen must be placed in each row.

  • No two queens may occupy the same column.

  • No two queens may share a diagonal.

  • Every queen must occupy a distinct square.

Diagonal Conflict Rule

For two queens at positions (r1, c1) and (r2, c2), they share a diagonal when |r1 - r2| = |c1 - c2|.

Backtracking Strategy

  • Start with an empty board.

  • Process the rows one at a time.

  • Try each column in the current row.

  • Check whether the column and both diagonals are free.

  • Place a queen if the position is safe.

  • Recursively process the next row.

  • If no safe position works, remove the previous queen and try another column.

  • When all N rows contain queens, record a complete solution.

Efficient Conflict Tracking

Columns

A boolean array or set records which columns already contain queens.

Descending Diagonals

The value row - column uniquely identifies one diagonal direction.

Ascending Diagonals

The value row + column uniquely identifies the other diagonal direction.

Lookup

Three sets allow each candidate position to be checked in expected O(1) time.

Python Example

Code

def solve_n_queens(n):
solutions = []
columns = set()
diagonal1 = set()
diagonal2 = set()
board = [-1] * n

def backtrack(row):
if row == n:
solutions.append(board.copy())
return

for col in range(n):
if col in columns:
continue
if row - col in diagonal1:
continue
if row + col in diagonal2:
continue

board[row] = col
columns.add(col)
diagonal1.add(row - col)
diagonal2.add(row + col)

backtrack(row + 1)

board[row] = -1
columns.remove(col)
diagonal1.remove(row - col)
diagonal2.remove(row + col)

backtrack(0)
return solutions

print(solve_n_queens(4))

Output

[[1, 3, 0, 2], [2, 0, 3, 1]]

Output Explanation

The two lists represent the column chosen for each row. For N = 4, there are exactly two distinct solutions when reflected and rotated arrangements are counted separately.

Complexity

Search Bound

A straightforward row-by-row implementation has an O(N!) upper bound on the number of partial arrangements explored when columns are chosen without repetition.

Conflict Checking

Using sets for columns and diagonals gives expected O(1) conflict checks per candidate.

Solution Storage

Storing all solutions requires additional memory proportional to the number of solutions multiplied by the board representation size.

Important Note

The exact running time depends on whether the algorithm finds one solution or enumerates all solutions, and whether symmetry reduction or additional pruning is used.

Special Cases

  • N = 1 has one valid solution.

  • N = 2 and N = 3 have no solutions.

  • N = 4 has two solutions.

  • Larger boards can have many solutions, so storing every arrangement may require substantial memory.

Common Mistakes

  • Checking only rows and columns while forgetting diagonal attacks.

  • Using row + column for both diagonal directions.

  • Forgetting to remove a queen from the conflict sets during backtracking.

  • Saving a reference to a mutable board instead of copying it.

  • Treating mirrored or rotated boards as identical when the task requires all distinct arrangements.

Learning Tip

Start with N = 4 and represent the board as one column number per row. Trace each attempted placement and identify exactly when a column or diagonal conflict forces the algorithm to backtrack.

Key Concepts

NameDescription

Core idea

The central focus of n-queens problem is the capability described here: The N-Queens problem asks how to place N queens on an N × N chessboard so that no two queens attack one another. Since a queen can attack along rows, columns, and diagonals, a valid arrangement must contain exactly one queen in each row and column, with no shared diagonal. Backtracking solves the problem by placing one queen at a time and abandoning placements that create conflicts.

Problem context

N-Queens Problem is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using n-queens problem, check its assumptions, input requirements, expected output, and resource constraints.

Applications

  • Designing and implementing solutions involving n-queens problem.

  • Teaching and assessing n-queens problem in computer-science courses and interviews.

  • Checking solutions that use n-queens problem against correctness and resource constraints.

Limitations

  • The suitability of n-queens problem depends on the exact problem requirements and the assumptions made about the input.

  • An implementation of n-queens problem can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For n-queens problem, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Practice Questions

QuestionAnswer

What is the main purpose of n-queens problem?

The N-Queens problem asks how to place N queens on an N × N chessboard so that no two queens attack one another. Since a queen can attack along rows, columns, and diagonals, a valid arrangement must contain exactly one queen in each row and column, with no shared diagonal. Backtracking solves the problem by placing one queen at a time and abandoning placements that create conflicts.

What should be checked before applying n-queens problem?

For n-queens problem, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints.

How can an implementation of n-queens problem be validated?

Trace a representative n-queens problem case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline.

Learning Objectives

  • Explain the central idea and purpose of n-queens problem.

  • Identify the assumptions, inputs, and conditions relevant to n-queens problem.

  • Evaluate an application of n-queens problem for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Scienexy Computer Science Reference

Suggest a correction or source · More in Algorithms & Data Structures