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. Now, this cell is attacked by this queen. This cell is attacked by this queen. This cell is attacked and this cell is attacked by the second queen. So, this cell is the death range. So we did not try to continue, because definitely it will not lead us to a solution. Right? Because just because, for this particular row, we cannot place a queen. So, we get back here and we try to place a queen in the second row in some different position. And the different position is the only remaining position in this cell. Right? So let's try to do this. We place a queen here. So, for the next row we will place a queen here and then we see that, for the last row, all the cells are attacked. So, we get back here. We place the queen in the last available position. So, again, we get back and then we get back here and then we adjust the position of the first queen. Okay? Then, let me proceed. Let me proceed faster. What we see here, in this branch, is that we were actually able to extend the solution to the four queens. Okay? So, what we get here is actually a solution. So, at this point, we actually might want to stop and to report that this is a solution. But if you would like to find all possible solutions, then we can continue this process in a similar fashion. So, we get back to the initial stage and then we try to place a queen in the first row in a different position. For example, in this case, in the third position. And then we do essentially the same. We try to expand it. And then we try to place a queen into the rightmost available position in the first row and then we began to enumerate all possible cases. So what we see here now on this slide is a complete recursion tree of all possible, partial solutions. All the final solutions are shown here on the last row and all these guys are actually dead ends. So, these are solutions or partial solutions that cannot be extended. So, in this case, for example, we cannot place a queen into the next available row just because all the cells are already attacked. In this case, we cannot place a queen to the next available row which is last row, because, again, all the cells of this row are already attacked. Okay? So this is the main idea of Backtracking it is traded on this 4 x 4 queens puzzle.
