Solution: N-Queens

Statement

Given a chessboard of size $n \times n$, determine how many ways $n$ queens can be placed on the board, such that no two queens attack each other.

A queen can move horizontally, vertically, and diagonally on a chessboard. One queen can be attacked by another queen if both share the same row, column, or diagonal.

Constraints:

• $1 \leq n \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 $n$ 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 $6$ queens on a $6 \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 \times 33 \times 32 \times 31 = 1113024$ possible ways to place the remaining $4$ queens. All of these ways are invalid since placing two queens next to each other is invalid. The time complexity of this solution would be $O(\binom{n^2}{n})$ and the space complexity would be $O(n)$, where $n$ is the dimension of the chessboard.

Optimized solution using backtracking

A better and more optimized approach would be to only check for valid placements. This can be achieved by backtracking to a previously valid state in case there is no safe move left. Through backtracking, we avoid an exhaustive search and thus improve the algorithm’s performance. Therefore, this problem is a great fit for the backtracking pattern.

Problem analysis

As stated in the problem statement, we have an $n \times n$ chessboard to place the queens such that no two queens attack each other. Let’s understand the implications of these two conditions:

1. Once we place the first queen anywhere in the first row, no other queen may be placed in that row. Therefore, the search for a safe position for the next queen starts from the next row. This gives us a simple means to store a solution: we simply need to store the column for each row, that is, an array of $n$ column indices, each representing a safe placement.
2. As there are $n$ rows in the given board, and each row may safely hold just one queen, in any valid solution, all $n$ rows would be used, each holding exactly one queen. This gives us both a condition to check the validity of a solution, as well as a way to check whether a solution is complete.

Solution 1

The backtracking algorithm to solve the $n-$queens problem is very similar to a depth-first search of a tree.

There are two conditions that cause us to backtrack, but for two different purposes:

• When we find that we cannot place the current queen in a particular row, we have to backtrack and alter the position of the queen whose position was decided before the current one. Next, we move forward again to find a safe position for the current queen.
• Once we find a valid solution, we still have to identify all the other valid solutions. So, we backtrack by removing the last queen placed on the board and resuming our search for solutions from that point. In order to be sure to find all possible solutions, we’ll need to backtrack, row by row, all the way back to the first queen placed on the board, changing its position and then looking for alternative solutions.

Let’s run our example on a $4 \times 4$ board with $4$ queens: