0:00

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.

Â