Now we are going to try to implement this idea. And before doing this, we need to actually be able to generate all possible permutations. As you remember from the previous video, we were just using built in procedure for generating all possible permutations. But now, we need our own procedure because we would like to partially extend permutations. And for some partial permutations, we are going to just stop trying to extend them. Because they are not going to be extended to a solution drawn over n by n wins puzzle. Okay, so to generate all permutations, we will do the following. We are going to do this recursively. Meaning, we are going to implement the procedure that is going to call itself to generate all permutations. So this is called to generate permutations. Initially, we call this procedure with the parameter perm, which stands for permutation, of course, which is initially just an empty list. And the parameter of n, which is equal to 4. What this procedure is going to do is the following. First of all, if the length of the current permutation is equal to n. So remember that we are going to construct our permutations piece by piece. So first, we'll add the first element, and the second element, and the next element, and so on. So if it was over the extended to at list of size n, we just print it and return. We do not try to extend it to some other permutation anymore. Because it already contains n elements. If it contains less than n elements, we try to extend it by some new element. And this new element is denoted by k. And it ranges through all possible values from 0 to n- 1. First of all, we check whether k is present in the current permutation. If it is present, then, of course, we are not going to try to add it because we need a permutation. We want all the elements in our permutation to be different, right? So if k is not in the permutation, we add it to the current permutation. And we call the same procedure again. So we try to extend it piece by piece puzzle. And for this, we call just exactly the same procedure. And in the end when we made this call, we remove the just added element k from this permutation in order to add another element to it, right? And this is the output of the corresponding method. So indeed, it generates all possible permutations of 4 elements, 0, 1, 2, and 3, okay? Now what we are going to do is to combine two methods that we already implemented. So on one hand, we have this recursive generation of all possible permutations. On the other hand, we have a method which checks whether the permutation is a solution or not. And we can actually adjust it to just check whether if we have a partial permutation, whether it can be extended to our solution or not. And for this, it is actually enough to check whether when we extend the permutations, this actually corresponds to the case when we place a new queen to the current row on our board. And for this, it is enough to check whether this last queen actually attacks some of the previous queens. So we need to implement this check. We need to implement the check whether the current partial permutation can be extended to a solution of the nth queen's problem or not. So let's try to implement such a procedure. So we're given some partial permutation in this case. And we are implementing a procedure called can_be_extended_to_solution. So for this, we take the last queen. Okay, so we just compute the length of the permutation and subtract 1. So this is the last index of our permutation. Then we iterate through all possible previous indices. Okay, so j ranges from 0 to i- 1. And we check whether the last queen and some previous queen, they stay on the same diagonal. So for this, we check whether i- j is equal to absolute value of perm[ i ]- perm[ j ]. So we do not use absolute value of i- j here. Because we know that i is greater than j. Because i is the last element of our permutation. So if this equality holds, we return False immediately. Because this means, once again, that these two queens stay on the same diagonal. If there is no such pair, we return True. So this means that we still believe that the current permutation can be extended to a solution. At least there are no conflicts in the current permutation, okay? And then this allows us to implement the program as follows. This is just the combination of generating null permutations together with checking whether the current partial permutation can be extended through a solution or not. So let's see, so the procedure is called extend. Initially, it is given a partial permutation, which is empty, together with the parameter n = 20, okay? So we first check if the length of the permutation is n, we just print it and stop the whole program. So this means that we found the solution. Otherwise, we try to extend it. Once again, we try to extend it by an element k, which ranges through all values from 0 to n- 1. We only do this if k is not currently in permutation. And we append it. And then we check whether there is any conflict in the resulting partial permutation. So this has gone in this check. So if there are no conflicts, we try to extend this partial permutation further. And for this, we call the same procedure extend again, right? And then after we try to do this, we pop the last element k in order to try to add another element to this permutation. So if you run this program, you will notice that it computes a solution even for n = 20 on your laptop, okay? And this is the power of the backtracking method. So once again, its main idea is to construct a recursive tree of all possible solutions. But when we realize that our current partial solution cannot be extended to a solution, we cut the corresponding branch immediately. For this reason, it works pretty well in practice.
