In this video, we're going to further optimize our program

so that it is able to compute a solution for the N Queens Problem,

even four and equal to twenty.

The method that is going to help us is called Backtracking.

Its main idea is the following: we are going to construct our solution piece by piece.

What it means for the N Queens Puzzle is the following:

we're going to first place the queen in the first row.

Then, we're going to place a queen in the second row, then in the third one and so on.

If, at some point,

there is just no possibility to place the queen in the current row,

then we will get back and adjust the position of some of the previously placed queens.

And this step is called Backtracking.

Once again, it means the following.

If the current, partial solution cannot be extended to a solution,

then we get back and try to adjust our partial solution.

This is probably best illustrated with an example.

Let us prove that there is no solution for N Queens Problem when n is equal to three.

So, initially we have an empty board.

So our goal is to place three queens here.

We know for sure that we must place the queen in the first row somewhere.

So let's try the most obvious choice.

Let's try the leftmost position in the first row.

So, here we are.

We place the queen.

Then, we need to place a queen in the second row and the next one.

However, as we see,

these two cells are already attacked by the single queens that we have.

So, the only possibility where it still

makes sense to place a queen is the last cell in the second row.

So, we tried to do this,

but this cell is already attacked by this queen.

This cell is already attacked by this queen and this cell is also attacked by this queen.

Right?

Which means that we need to go back and this is what we do.

We go through.

We will come back here,

but remember that, in this case,

this cell is already attacked.

This cell is also already attacked.

So, the only possibility to place

a queen in the second row was to place it into this cell.

So, we tried this and it doesn't give a solution.

So, we get back even here.

And here, we try to place a queen into the second cell in the first row.

Okay, let's do this. So, here we are.

We placed the queen into the second position in the first row, but then,

we see that there is just no possible cell where we can place a queen in the next row.

Right? Because all of them are already attacked.

So, once again, we get back.

We Backtrack and then we try the last available option for the

first row--that is the rightmost cell.

Then again, we need to place a queen in the second row.

This cell is already attacked and this one is already attacked,

so we place a queen to this cell.

Okay? And in this case, again,

we have no choice for the last row,

because all the cells are already attacked.

This is attacked by this queen.

This cell is attacked by this queen and this cell is attacked by this queen.

Okay? So, what we've just proved is actually that there is

no solution for the 3 x 3 board.

Let's now consider a slightly more complicated example when n is equal to four.

So, once again, we try to place

a queen in the first of all the positions, in the first row.

This gives us the following picture.

So, in this case, this cell is already attacked in this one.

So, the first available cell in

the second row is the third one. So, we try to place a queen into this cell.