Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Solution: N-Queens II

Explore the backtracking approach to solve the N-Queens II problem by placing queens one row at a time on an n by n board. Learn how to efficiently track columns and diagonals to find all valid arrangements without conflicts. Understand how backtracking prunes invalid paths and counts all unique solutions.

We'll cover the following...

Statement

Given an integer, n, representing the size of an n x n chessboard, return the number of distinct ways to place n queens so that no two queens attack each other. A queen can attack another queen if they are in the same row, column, or diagonal.

Constraints:

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

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive solution

In order to find the optimal placement of the queens on a chessboard, we could find all configurations with all possible placements of nn queens and then determine for every configuration if it is valid or not.

However, this would be very expensive, since there would be a very large number of possible placements and only a handful of valid ones. For example, when trying to place 66 queens on a 6×66 \times 6 chessboard using brute force, suppose we place the first two queens side by side on the first two squares, there still remain 34×33×32×31=111302434 \times 33 \times 32 \times 31 = 1113024 ...