Hey there and welcome back!
We have developed a solid understanding of backtracking and we have already solved hard problems, and
I'm sure they must have seemed easy to you in this video, let's start with another hard problem, which
is called the N-queens problem.
And I'm sure that you will be able to solve this one as well.
Easily.
Given that we have already developed a solid understanding of backtracking.
Let's get started.
The N-queens puzzle is the problem of placing n queens on an n into n chessboard, such that no two
queens attack each other.
So this is the criteria.
No two queens attack each other.
Given an integer n, return all distinct solutions to the n queen puzzle over here.
Notice it's asked to return all the possible solutions, and this is a very strong indication that probably
we can use backtracking to solve this question.
You may return the answer in any order.
Each solution contains a distinct board configuration of the n queens placement, where q and dot both
indicate a queen and an empty space, respectively.
Now let's say that n is equal to four, and let's use this to understand this problem thoroughly.
Now, if n is equal to four, then we have a 4x4 chess board.
Now, before we go ahead and see what would be valid solutions for this, let's take a moment to think
about the possible movements of a queen on a chess board.
For this.
Let's say a queen is placed over here.
Now, the queen over here can move horizontally and vertically.
So that's these two directions.
And it can move also diagonally.
So if you place a queen over here and because the criteria in the question says that no two queens should
attack each other, you cannot place any queen in these cells.
Because this queen would be attacking it.
So if you have a queen over here, you will not be able to place any other queen in all these cells.
Now let's take a look at what would be the solution if n is equal to four.
So if n is equal to four we can have these two combinations.
Notice over here this queen does not attack any other queen.
And that's true for all these queens.
So we have four queens in four rows and no queen attacks any other queen.
And then this is another combination which is possible.
And the question asks us to identify all distinct solutions for the given n n is the input parameter.
So if n is equal to four this is the desired output.
So over here we have a dot indicating that this is empty.
Then we have a queen.
Then we have a dot and another dot.
So that's this row over here.
And this is the second row.
We have dot dot dot indicating that these three positions are empty.
And then we have a queen.
So again this over here, this row over here is one solution.
And then this second row over here is this solution over here.
So this is the desired output when n is equal to four.
So we have understood the question in the next video.
Let's think about solving this question.