Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Problem: N-Queens

Explore how to use recursive backtracking to solve the N-Queens puzzle, placing n queens on an n x n chessboard so that no two threaten each other. Understand how to use sets to track attacked columns and diagonals, implement backtracking to explore valid configurations, and analyze the time and space complexity of the solution.

We'll cover the following...

Statement

The N-Queens puzzle involves placing n queens on an n x n chessboard so that no two queens threaten each other. Two queens attack each other if they share the same row, column, or diagonal.

Given an integer n, return all distinct solutions to the N-Queens puzzle. The answer may be returned in any order.

Each solution should be represented as a list of strings, where each string corresponds to a row of the chessboard. In each string, 'Q' denotes a queen and '.' denotes an empty space.

Constraints:

  • 1≤1 \leq n ≤9\leq 9

Examples

canvasAnimation-image
1 / 3

Try it yourself!

Implement your solution in the following coding playground.

Python
usercode > Solution.py
def solveNQueens(n):
    # Replace this placeholder return statement with your code
    return []
N-Queens

Solution

The core idea behind solving the N-Queens problem is to use recursive backtracking to place queens one row at a time. Since each row must contain exactly one queen, we iterate through each column in the current row and attempt to place a queen there, but only if the column and both diagonals passing through that cell are not already under attack. To efficiently check whether a column or diagonal is occupied, we maintain three sets: cols for columns, posDiag for positive diagonals (identified by row + col), and negDiag for negative diagonals (identified by row - col). Cells sharing the same positive diagonal have the same row + col value, and cells sharing the same negative diagonal have the same row - col value, ...