Hello and welcome to the lesson Computer Search. To prove that an object satisfying some particular properties exists, it is actually enough to construct and present such an object. At the same time, there are cases when it is not so easy to do this by hand, and it is exactly the situation when it makes perfect sense to us, computers to help us. And this is exactly the thing that we're going to do in this lesson. Namely, what we will consider through challenging puzzles,namely n queens puzzles and 16 diagonals puzzle. If you try them, you will notice that it is indeed not so easy to find the solution. Instead of constructing such a solution by hand, we're going to implement this simple program that is going to help us to find a solution in a blink of an eye. So we start with the N Queens puzzle. Let me first remind you how the chess queen moves. So it moves horizontally, diagonally, and vertically. So, for example, the queen that you see here on the slide can move along either this vertical line or horizontal line or two diagonal lines. Okay. Then the natural question is the following. Given an n x n chessboard, your goal is to place exactly n queens on this board such that no two queens attack each other. Okay? So, first of all, we know that the solution for this puzzle exists whenever n is at least four. At the same time, if you try to solve this puzzle by hand, you will notice that already for n equals eight, it is not so easy to find it by hand. Not to say about n equals 20. So let's try to find a solution and let's try to find and implement a computer program that will find a solution almost immediately. First of all, let's try to understand how to represent a particular solution in our problem. And for this, let's notice that if there is a solution that in every column, there must be exactly one, one queen. Why is that? Well exactly, because if there are at least two queens in some column, then they definitely must attack each other. So there must be at most one queen in each column. At the same time, if there is a column without the queen, this means basically is that in total, there are strictly less than n queens. And similarly we conclude that in each rows there must be exactly one queen. Okay. Now let's consider the following solution for the case where n, the size of the board is equal to four. So in this case we have 4 x 4 board and there are four queens, exactly one queen in each row and exactly one queen in each column, such that they do not attack each other. So what the title of the slide claims here, is that this solution can be represented as a permutation. You see the left index of the columns and of the rows by numbers starting from zero to n minus one. So in this case n equals 4, so n minus one equals three. Okay, so now let's represent the corresponding placement of queens by the following permutation of the numbers 0, one, two, three. So how it is represented by this permutation? Well it is easy to see. So this is an array, right? It is of size four. This is its indices 0, one, two, three. So the contents of the cell one actually tells of that in the zero's column, this is the zero's column and this the zero cell, we have a queen in the first row. This is the queen in the first row, right? And this exactly corresponds to this one. For the second column, that is column number one because we start from zero, we have three in this cell and this exactly indicates the fact that for this column, we have a queen standing at the third row in this column and so on. So, at this point, it should be clear that every correct solution can be represented by a permutation. This is exactly because in every row and in every column, we have a single queen. At the same time, not every permutation defines a solution and this is shown here on the slide. And so in the left, we have our previous solution and in the right, we have also some permutation which defines some placement of queens such that in every row and in every column, there is exactly one queen. At the same time, it is not a solution, right? Because we have two queens here on the same diagonal. So they attack each other. So we definitely need some procedure that we'll check whether the given permutation is indeed a solution. So we need to implement the procedures that will be given a permutation and it will all prove true even though I believe in this permutation, in this placement of queens on the n by n board, there are no two queens that stay on the same diagonal. So let's try to design a formula which will tell us when two queens stay on the same diagonal. This is our initial picture, so it shows our initial queen and it shows all the positions where it can move. So when I claim in the following, two queens stay on the same diagonal, consider for example, this queen and for example this queen. So they stay on the same diagonal because this horizontal shape exactly equal its vertical shape, right? And this is true for all the positions shown here on the slide. So in this particular case we have four cells here and four cells here. Now let's consider for example this queen. So these two guys stay on the same diagonal exactly because the difference between their coordinates with respect to the columns is equal to the distance. It is equal to three. In this case, it is equal to three with respect to rows. And so right here, we see a formula. So, if we have two cells with coordinates I1 and J1 and I2 and J2, so this means that we have a queen standing at I's row and J's column and we have another queen standing at I2 row and J2 column. So then they stay on the same diagonal, if and only if, the absolute value between I1 and I2 is equal to the absolute value between J1 and J2. Right? So this is our formula and it allows us to immediately implement a simple program, just four lines of code that will check whether a given permutation is indeed a solution. So to check this, we do the following. We just, given the permutation, we go through all possible indices of rows, I1 and I2. So here we just iterate for all possible such queries using combinations from itertools. So then we just check whether the absolute value of I1 and I2 is equal to the absolute value of J1 and J2, where J1 is computed as permutation of I1. So this is J1 and J2 is computed as a permutation of I2. So if this absolute value is inside for at least for some pair of I1 and I2, this basically means that there are two queens that attack each other. In this case, we immediately return false. If there is no such player, we return true. So after this procedure is implemented, we do a small sanity check. We just check whether for the previously considered examples, the first one is indeed a solution and the second one is indeed not a solution. Okay. So when given such a check whether a given permutation is a solution or not, we can actually implement the whole program for finding a solution for the eight by eight board for example. So this is our procedure that checks whether a given permutation is a solution or not. And then what remains to be done is just to iterate through all possible permutations. And fortunately enough, in Python we can do this very easily. So we just iterate through all possible permutations and for each one we check whether it is a solution or not. If it is a solution, we print it and we stop immediately, okay? And this is basically it. So if you run this program, you will notice that it will find a solution for n equal to eight, almost immediately. At the same time, already for n equal to 13, for example, it takes a noticeable time. Okay. Not to say about n equal to 20, it will never stop for n equal to 20. In the next video, we will actually optimize our problem so that it works quite fast even for n equal to 20.
