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.

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})$ ...