1 00:00:00,180 --> 00:00:06,480 OK, this example is referring to the problem of minimum queen to cover the whole chessboard. 2 00:00:06,930 --> 00:00:14,070 OK, suppose we have a chess board with a given size special given size. 3 00:00:14,070 --> 00:00:19,170 As you know, chess boards are eight by eight, but suppose a very special case. 4 00:00:19,740 --> 00:00:21,210 It is four by four. 5 00:00:22,080 --> 00:00:32,850 And we want to know what is the minimum number of queens required to protect all of the cells, OK? 6 00:00:33,030 --> 00:00:35,720 And these queens should not attack each other. 7 00:00:35,730 --> 00:00:38,620 So one of the configuration is shown on this graph. 8 00:00:38,640 --> 00:00:41,730 So here you can see that there are three queens. 9 00:00:42,070 --> 00:00:48,330 This is the minimum number of queens required and all of the rows are protected. 10 00:00:48,330 --> 00:00:53,490 For example, this row, the D row and this column are protected by this one. 11 00:00:54,270 --> 00:00:59,940 This column and this row is protected by this one and also. 12 00:01:00,860 --> 00:01:09,500 And you can see here that this guy is protecting this column and Israel and also these two cells and 13 00:01:09,500 --> 00:01:10,530 this cell and this. 14 00:01:10,760 --> 00:01:14,540 OK, so we treat acquis queens. 15 00:01:14,540 --> 00:01:16,920 I have covered all the cells. 16 00:01:16,970 --> 00:01:21,280 OK, but how can we solve this in general mode? 17 00:01:21,290 --> 00:01:26,710 So if you are given in by any chess board, how many queens are required? 18 00:01:26,720 --> 00:01:28,490 What is the minimum number of them required? 19 00:01:28,520 --> 00:01:31,450 OK, so we want to minimize the number of them. 20 00:01:31,490 --> 00:01:40,970 So I have to define a binary value called UIGEA, which is telling us at Cell I and J if there is a 21 00:01:40,970 --> 00:01:43,040 queen or there is not a queen. 22 00:01:43,120 --> 00:01:45,820 OK, so here I am. 23 00:01:46,200 --> 00:01:50,600 This is what we are doing for every given column. 24 00:01:50,600 --> 00:01:53,180 J summation over. 25 00:01:53,360 --> 00:01:56,000 I should be less than equal to one. 26 00:01:56,000 --> 00:02:00,080 It means they are not more than one queen can exist on each column. 27 00:02:00,470 --> 00:02:07,160 Not more than one queen can exist in each row and also on each diagonal. 28 00:02:07,460 --> 00:02:12,530 The number of queens should be less than one, one or less than equal to one. 29 00:02:12,680 --> 00:02:14,210 So it can be won or not. 30 00:02:14,210 --> 00:02:14,700 Nobody. 31 00:02:15,350 --> 00:02:17,420 And also, um. 32 00:02:19,220 --> 00:02:20,150 Um. 33 00:02:21,310 --> 00:02:23,060 For every, um. 34 00:02:26,070 --> 00:02:31,790 Every effort for the anti diagonal cells, the same condition should happen as well. 35 00:02:33,000 --> 00:02:35,970 OK, so let's continue. 36 00:02:38,990 --> 00:02:43,840 The last condition, so whatever we talked about is, um. 37 00:02:50,060 --> 00:02:54,510 This problem is called minimum queen to uncover the chessboard. 38 00:02:54,770 --> 00:02:56,800 So it is a specific problem. 39 00:02:56,810 --> 00:03:02,630 We are trying to find out what is the minimum number of queen required for protecting or covering all 40 00:03:02,630 --> 00:03:03,200 the cells. 41 00:03:03,890 --> 00:03:11,720 And I suppose this example is going to be solved for a very special case of an chessboard with four 42 00:03:11,720 --> 00:03:13,040 by four dimensions. 43 00:03:13,430 --> 00:03:15,620 As we know, usually they have eight by eight. 44 00:03:15,620 --> 00:03:17,300 But this is a special case. 45 00:03:17,780 --> 00:03:24,560 And so you can see here by only three screens located at this specific location, all of the cells are 46 00:03:24,830 --> 00:03:25,460 protected. 47 00:03:25,470 --> 00:03:34,220 For example, this cell is being protected by these two queens and no two ones are attacking each other. 48 00:03:35,740 --> 00:03:41,800 Then we need to define it as an optimization problem, and if we want to solve it for general case, 49 00:03:42,160 --> 00:03:44,970 so we do the summation over IFJ. 50 00:03:45,620 --> 00:03:45,840 Hmm. 51 00:03:46,360 --> 00:03:56,080 And, um, UIGEA is a binary variable and representing the fact that if a queen exists on the cell, 52 00:03:56,080 --> 00:04:05,320 I and J and also for every um, um, given column like J. 53 00:04:05,850 --> 00:04:14,100 Um, if we do the summation over the rows then there will be not more than one queen on each column 54 00:04:15,190 --> 00:04:21,370 and also and there will be not more than one queen on each row on on each a.. 55 00:04:21,370 --> 00:04:23,560 Diagonal, on each diagonal. 56 00:04:23,890 --> 00:04:25,190 Uh, rows of cells. 57 00:04:25,260 --> 00:04:33,060 OK, and and so these four conditions are designed for Queenie's not to attack each other. 58 00:04:33,640 --> 00:04:35,860 And also we need another one. 59 00:04:36,490 --> 00:04:45,220 OK, so if we just use these four, then, um, the obvious solution to this problem will be no queen 60 00:04:45,220 --> 00:04:45,610 at all. 61 00:04:45,680 --> 00:04:52,570 OK, so we need another kind of, um, uh, constraint saying that for every IFJ. 62 00:04:54,180 --> 00:05:06,870 Um, if we do the summation of why you see an R and then, um, for every, um, diagonal or A. diagonal 63 00:05:06,870 --> 00:05:13,890 or every row or every column passing through that cell, the summation should be bigger than equal to 64 00:05:14,220 --> 00:05:14,670 one. 65 00:05:15,240 --> 00:05:23,010 OK, so it means that, um, it should be protected by at least one, um, queen. 66 00:05:24,260 --> 00:05:34,790 OK, so, um, if we solve that, we can see the results for the four by four, uh, case, so if N 67 00:05:34,800 --> 00:05:42,290 is for, then the solution is done and also we can test it for a bigger chessboards, six by six or 68 00:05:42,290 --> 00:05:44,380 eight by eight, the traditional one. 69 00:05:44,390 --> 00:05:49,700 So the eight by eight, uh, chessboard can be protected by only five queens. 70 00:05:50,030 --> 00:05:50,280 Hmm. 71 00:05:50,650 --> 00:05:57,800 And if we make it bigger, let's make it ten then it can be protected by six queens. 72 00:05:57,860 --> 00:06:05,960 OK, so I'll show you the Python code for solving this specific optimization problem, which is a linear 73 00:06:05,960 --> 00:06:07,900 programming mix in a linear programming. 74 00:06:08,210 --> 00:06:11,570 As usual, we import the required packages. 75 00:06:12,020 --> 00:06:12,350 Mm. 76 00:06:13,760 --> 00:06:21,320 And is representing the size of size and dimension of the chessboard, I is representing the queens, 77 00:06:21,320 --> 00:06:27,410 different queens and is the areas of I you is a binary variable defined or I and J. 78 00:06:28,390 --> 00:06:34,470 Um, so we need to define some rules for not attacking to each other. 79 00:06:34,490 --> 00:06:41,510 So these three rules are, um, designed in order to um. 80 00:06:42,420 --> 00:06:46,350 Um, sorry, the first one. 81 00:06:46,500 --> 00:06:55,200 Let's have a look at this one first, so the first one is telling us that each cell I and J should be 82 00:06:55,200 --> 00:06:57,660 protected by at least one of these conditions. 83 00:06:58,050 --> 00:07:05,430 So there should be a crane on the diagonal or a. diagonal or is equal to or J is equal to see or from 84 00:07:05,430 --> 00:07:06,210 the same roll. 85 00:07:06,210 --> 00:07:10,110 From the same column or from the diagonal or a. diagonal. 86 00:07:10,590 --> 00:07:17,970 Um, and also the remaining ones are designed in order to not the queen. 87 00:07:17,970 --> 00:07:19,040 Do not attack each other. 88 00:07:20,640 --> 00:07:27,900 As I explained, and the objective function is the summation over UIGEA for every eye in model eye and 89 00:07:27,900 --> 00:07:29,810 for every J in Model J. 90 00:07:31,010 --> 00:07:41,290 The solver is chosen to be good pick because it's integer programming, and then we provide the and 91 00:07:41,580 --> 00:07:49,100 the model to the, um, instance creation, the instance will be created and the results are obtained 92 00:07:49,100 --> 00:07:49,890 after the solve. 93 00:07:50,240 --> 00:07:56,100 And finally, the, uh, solutions are graphically shown here. 94 00:07:56,570 --> 00:08:06,110 OK, and finally, it can be saved somewhere on your machine as a, um, Jimin and Queen Dot PJI, for 95 00:08:06,110 --> 00:08:06,590 example. 96 00:08:06,920 --> 00:08:09,170 OK, so I run the code for you. 97 00:08:12,070 --> 00:08:14,110 Um, it is raining now. 98 00:08:19,630 --> 00:08:23,200 So for simplicity, we have assumed that, um. 99 00:08:24,190 --> 00:08:28,580 Uh, and it's changing between four, six, eight and 10. 100 00:08:28,600 --> 00:08:30,550 You can change that number as well. 101 00:08:31,030 --> 00:08:35,140 OK, I hope you learned something useful in this lecture. 102 00:08:35,260 --> 00:08:36,160 Thank you very much.