1 00:00:06,610 --> 00:00:09,100 This is the end queen's problem. 2 00:00:10,570 --> 00:00:18,880 And I suppose we have a N by n chessboard and we want to put some queens on these chessboard without 3 00:00:18,880 --> 00:00:23,770 attacking each other and we want to maximize the number of queens that we put on these chessboard. 4 00:00:24,280 --> 00:00:34,780 OK, so suppose we want to start this problem and for solving that, what we need to use, uh, some 5 00:00:34,780 --> 00:00:35,950 binary variables. 6 00:00:36,220 --> 00:00:42,550 So UIGEA will tell us if, uh, Queen exists on the cell. 7 00:00:42,550 --> 00:00:43,340 I and J. 8 00:00:43,360 --> 00:00:47,720 Iris representing Rose and J is representing column. 9 00:00:48,160 --> 00:00:50,770 OK, and we want to maximize this summation. 10 00:00:51,430 --> 00:00:57,640 OK, so some rules and on each um column. 11 00:00:57,640 --> 00:00:59,080 For every given column. 12 00:00:59,080 --> 00:01:00,190 For every J. 13 00:01:00,760 --> 00:01:06,780 Um, we can't have more than one, uh, queen on the board. 14 00:01:06,820 --> 00:01:08,900 So this is written as follows. 15 00:01:09,220 --> 00:01:14,620 So the summation of over I over the rows and should be less than one. 16 00:01:15,140 --> 00:01:25,150 And also the same kind of, uh, similar constraint is um here uh, for every, um, given row and the 17 00:01:25,150 --> 00:01:31,870 summation of a J or over the columns should give us less than one queen on each row. 18 00:01:32,080 --> 00:01:34,570 OK, this is another rule, just rule. 19 00:01:34,810 --> 00:01:37,770 And the the other rule is the diagonal rules. 20 00:01:38,080 --> 00:01:45,880 So it means that on every diagonal or a. diagonal, we can't have more than one, uh, queen and some 21 00:01:45,880 --> 00:01:46,480 diagonals. 22 00:01:46,480 --> 00:01:48,830 We can have no queen as well. 23 00:01:48,850 --> 00:01:57,280 OK, so we want to solve these, um, optimization problem in a way that these four constraints are 24 00:01:57,280 --> 00:01:57,990 satisfied. 25 00:01:58,270 --> 00:02:00,100 So there's an objective function. 26 00:02:00,400 --> 00:02:10,570 And for every J and these constraints to satisfy every ideas exercise for every I n j if they are diagonal 27 00:02:10,580 --> 00:02:14,260 or diagonal, these constraints should be satisfied. 28 00:02:14,290 --> 00:02:21,580 OK, so let's have a look at, um, Python code developed for this purpose. 29 00:02:21,580 --> 00:02:22,950 Just a second. 30 00:02:23,020 --> 00:02:26,170 Uh, OK, so this is the Python code. 31 00:02:26,650 --> 00:02:34,420 OK, so first of all, I have to import the required packages like PI en masse, partly because at the 32 00:02:34,420 --> 00:02:36,340 end I want to plot the results. 33 00:02:36,790 --> 00:02:41,710 And also and I have to specify what is the dimension of the board. 34 00:02:41,710 --> 00:02:50,830 So I specify this like that, um, I have defined it mutable because, uh, maybe I need to change the 35 00:02:50,830 --> 00:02:52,180 size of the board. 36 00:02:52,570 --> 00:02:58,750 And also I is representing the set of keys, set of Rosary and J is the set of um. 37 00:02:59,860 --> 00:03:08,470 Columns, but since they are they have the same number of cells, then I have defined them as alias 38 00:03:08,680 --> 00:03:17,230 and model dots, you is a variable is a binary variable representing if a queen exists in that cell 39 00:03:17,230 --> 00:03:18,070 or not. 40 00:03:18,080 --> 00:03:20,280 And I have initialized that with one. 41 00:03:20,800 --> 00:03:26,370 OK, and and we have two rules, one for row, one for column. 42 00:03:26,650 --> 00:03:37,690 So the summation of um uh model does you ija for every J in model J should be less than equal to one 43 00:03:37,690 --> 00:03:41,980 on this row is defined over every eye. 44 00:03:42,610 --> 00:03:51,410 OK, for a given I that summation should be valid and the same, um a similar concept is for every column. 45 00:03:52,000 --> 00:03:57,760 So for every column J summation over I should be less than one. 46 00:03:57,790 --> 00:04:05,320 OK, these two rules and the other two rules are representing the um diagonal and uh on the diagonal. 47 00:04:06,700 --> 00:04:07,570 Um. 48 00:04:09,440 --> 00:04:10,830 A set of rules. 49 00:04:10,920 --> 00:04:21,660 OK, so, um, model, uh, C Diag one is here and it is represented over I and J, but not for every 50 00:04:21,660 --> 00:04:28,410 IFJ those I enjoyed that satisfied this specific, um, relation. 51 00:04:28,890 --> 00:04:36,110 OK, and this is Phosphorylation is, uh, representing the the other diagonal of the uh board. 52 00:04:36,150 --> 00:04:44,370 OK, and the objective function is defined as the summation of the UIGEA for every I and J in the model 53 00:04:45,870 --> 00:04:47,820 and the sense is the maximization. 54 00:04:47,850 --> 00:04:53,550 OK, I rondi cell and then I specify the value of. 55 00:04:53,550 --> 00:04:56,460 And how many cells do we have on all. 56 00:04:56,460 --> 00:05:02,190 Chessell On each side of chessboards we can have a bigger chessboards and then try to solve it. 57 00:05:03,350 --> 00:05:12,590 I solve this problem and show you the results so you can see here that, um, these are the locations 58 00:05:12,590 --> 00:05:14,520 of the Queens on the board. 59 00:05:15,080 --> 00:05:22,730 So here we have only one queen on this row, one queen on this column, one queen on the stroll along, 60 00:05:22,730 --> 00:05:25,880 queen on this column on the final and. 61 00:05:27,190 --> 00:05:35,030 Uh, Taib will save that, um, figure as a pound you find in your directory. 62 00:05:35,100 --> 00:05:40,660 OK, so I can test it for a bigger kind of chessboard, let's say 16. 63 00:05:40,930 --> 00:05:41,220 Mm. 64 00:05:41,930 --> 00:05:42,530 OK. 65 00:05:42,640 --> 00:05:43,780 And if I. 66 00:05:44,910 --> 00:05:53,760 Plotted, you can see here that this is the new kind of, um, allocation of the Queen's thank you very 67 00:05:53,760 --> 00:05:54,090 much.