N-Queens (Part 1): Describing the Problem
The N-Queens problem is a classic CS problem that is normally tackled through recursion and backtracking. If you are new to CS, these two concepts are probably foreign and unfamiliar to you.
The purpose of this article is to help you understand this infamous problem and prescribe you a general approach to find solutions to this problem. In short, you do not need recursion or backtracking to read my article.
For now, let’s focus on understanding the problem and exploring a way to find possible solutions.
So what is the N-Queens Problem?
The N-Queens problem is based off the most powerful character in chess: the Queen chess piece. A Queen can attack any chess piece in its horizontal, vertical and diagonal sight.
Don’t fret, we will have a visual below!
The N-Queens problem tackles the following questions:
- Given an n x n chessboard, are you able to fit n queens?
- If so, how many permutations are there?
If that doesn’t make, let’s go over a visual for the n=1 and n=3 cases together.
The n=1 case:
For the n=1 case, we have a 1x1 chess board.
Now, ask yourself: can I fit an n-number of queen without attacking other queens? The answer is obviously YES.
But the n=1 case is pretty boring. For this case, this is the only solution since there is only one spot to put 1 Queen. In short, there is only one unique solution for n=1.
The n=3 case:
For the n=3 case, we have a 3x3 chess board.
Now, let’s ask ourselves: are we able to fit 3 queens?
To answer this question, let’s play with some moves: for the first permutation, let’s place the first queen to the top left.
For the second row, we only have one spot — the far right — to place the queen without the two queens attacking each other.
But then: are we able to fit a third queen in the third row? The answer is clearly no.
Placing a Queen in any of the columns in row 3 would create a conflict with other Queens. So we do not have a valid solution for permutations starting with row 1, column 1.
So far, we’ve only explored the permutations with the first piece in row 1 column 1. We could have started with row 1 column 2 or row 1 column 3. And if you were to explore the permutations using these alternative first steps, you would find that none of the resulting permutations will yield a solution.
In conclusion, there is no solution for the N-Queen problem when n=3. Simply put, there’s no possible way to fit 3 queens in a 3x3 chess board without creating any conflict.
Try doing what I did here for n=2. But after traversing the logic and steps prescribed above, you will find that there is no solution for n=2 as well!
Thank you for reading!