1 00:00:00,310 --> 00:00:04,358 Okay guys, the last thing I want to talk about is this Puzzle Challenge, okay? 2 00:00:04,358 --> 00:00:08,450 So this Puzzle Challenge is one way for you to get a better grade, so I guess 3 00:00:08,450 --> 00:00:10,520 we're going to give you this puzzles, okay? 4 00:00:10,520 --> 00:00:13,590 And they are in Extra Credit. It means that essentially you can get 5 00:00:13,590 --> 00:00:18,980 more points, okay? such that you you can you know, increase 6 00:00:18,980 --> 00:00:21,550 your grade. So I, I've always done that everywhere I, 7 00:00:21,550 --> 00:00:24,388 I, I've been teaching. You know, so that you know, I can't have 8 00:00:24,388 --> 00:00:27,280 an average which is actually, well I can have a very high average. 9 00:00:27,280 --> 00:00:30,730 And at the same time, you know, I can actually find out the people who are 10 00:00:30,730 --> 00:00:34,420 really, really good, okay? So, so I'm, we're going to look at 11 00:00:34,420 --> 00:00:40,010 basically four four puzzles here, okay? And the challenge here is going to find 12 00:00:40,010 --> 00:00:44,930 the largest size that you know, that you can solve then, okay? 13 00:00:44,930 --> 00:00:47,880 we're going to talk about some simple ones like the N-Queens, okay? 14 00:00:47,880 --> 00:00:51,800 Some interesting ones like the old interval series, and then the magic 15 00:00:51,800 --> 00:00:55,600 series, and then the magic square. Now there are different degrees of 16 00:00:55,600 --> 00:00:58,440 difficulty here on how you can scale them up. 17 00:00:58,440 --> 00:01:02,200 But, you know, every one of them is some interesting challenge, okay? 18 00:01:02,200 --> 00:01:05,370 So, and the, the, kind of, the grade here, you know, we'll talk about that 19 00:01:05,370 --> 00:01:08,720 later, is, is basically, you know, the largest, you know, solutions that you 20 00:01:08,720 --> 00:01:10,910 give us. You know, the higher the extra credit 21 00:01:10,910 --> 00:01:13,140 that you get, okay? So, you know, the N-Queens we have talked 22 00:01:13,140 --> 00:01:15,850 about. You know, this problem, you know you know 23 00:01:15,850 --> 00:01:18,390 a lot. And the basic idea is you want to place 24 00:01:18,390 --> 00:01:19,970 these queens so that they don't attack each other. 25 00:01:19,970 --> 00:01:23,080 You know, instead of looking at a board of eight by eight, we want to see if you 26 00:01:23,080 --> 00:01:25,616 can solve problems with, let's say, a million queens, right? 27 00:01:25,616 --> 00:01:29,589 That would be really nice, okay? So, so basically Xi, you know the 28 00:01:29,589 --> 00:01:34,929 decision variable Xi is basically the, the role of, in which we are placing 29 00:01:34,929 --> 00:01:39,010 Queens, the Queen which is on column i. We have these constraints that we have to 30 00:01:39,010 --> 00:01:41,040 satisfy. I won't go over them, I have been over 31 00:01:41,040 --> 00:01:46,620 them for many, many times, okay? and so the output format here is going to 32 00:01:46,620 --> 00:01:49,410 be very simple right? The input is you know, we, we don't care. 33 00:01:49,410 --> 00:01:54,950 We want just the output and the is the largest value N that you can you know 34 00:01:54,950 --> 00:01:57,130 find. And then obviously you want to give a 35 00:01:57,130 --> 00:02:01,200 solution such that we can check it okay? So basically give the value of every one 36 00:02:01,200 --> 00:02:04,730 of these decision variable which is basically the row in which column, the, 37 00:02:04,730 --> 00:02:08,630 the column. The row in which the queen on column i is 38 00:02:08,630 --> 00:02:11,740 basically placed, okay? So you give us, you know, column, the row 39 00:02:11,740 --> 00:02:15,530 of queen, of queen on column zero, the row of queens on column one and so on and 40 00:02:15,530 --> 00:02:18,930 so forth, okay? A long list, hopefully this is like, 41 00:02:18,930 --> 00:02:21,930 billions, a billion, billion value, right? 42 00:02:21,930 --> 00:02:27,070 so this is one of the, one, this is one of the output for this particular Queens. 43 00:02:27,070 --> 00:02:29,280 It's the best you can do is solve five Queens, okay? 44 00:02:29,280 --> 00:02:33,769 So you can tell us, yes, I solved five Queens, and these are the results, 0, 2, 45 00:02:33,769 --> 00:02:38,210 4, 1, 3, okay? I don't think that will get you very far, 46 00:02:38,210 --> 00:02:40,662 in the kind of extra credit that you will have, okay? 47 00:02:40,662 --> 00:02:44,810 so that's the first problem. The second problem is really interesting, 48 00:02:44,810 --> 00:02:47,734 it's called the interval, all interval series, okay? 49 00:02:47,734 --> 00:02:51,406 And the key idea is that you have a number between 0 and n-1, okay? 50 00:02:51,406 --> 00:02:55,486 And you want a permutation of them, so that when you look at it as a sequence, 51 00:02:55,486 --> 00:02:57,520 okay? The difference between two elements in 52 00:02:57,520 --> 00:03:00,250 the sequence, all of the, you know, you look at the difference between two 53 00:03:00,250 --> 00:03:03,550 elements in the sequence. And all of them have to be all different, 54 00:03:03,550 --> 00:03:07,730 and the, the sequence, well, these absolute val, all these absolute value 55 00:03:07,730 --> 00:03:10,170 have to be all different. They have to have all different values, 56 00:03:10,170 --> 00:03:13,032 okay? So so this is how you can state it a 57 00:03:13,032 --> 00:03:17,946 little bit more mathematically, okay? So you have this Xi which is telling you 58 00:03:17,946 --> 00:03:21,360 element i of the sequence, okay? So what you want to be sure is, that 59 00:03:21,360 --> 00:03:25,530 let's say element i of the sequence, Xi. You know, and then the previous, the 60 00:03:25,530 --> 00:03:29,080 previous element of this sequence. the next element of this sequence Xi 61 00:03:29,080 --> 00:03:31,340 minus 1. You take the difference between these two 62 00:03:31,340 --> 00:03:34,674 values. And then you take it to you take Xj and 63 00:03:34,674 --> 00:03:38,590 take Xj plus 1, and make sure that j and i are different. 64 00:03:38,590 --> 00:03:42,000 So these two values, these two difference have to be different, okay? 65 00:03:42,000 --> 00:03:45,280 So, so you don't want the same value for these differences, okay? 66 00:03:45,280 --> 00:03:48,990 And you want that for all the successive elements, okay? 67 00:03:48,990 --> 00:03:53,610 And so, and, and obviously the Xi have to be a permutation between 0 and, and, and 68 00:03:53,610 --> 00:03:56,880 minus 1, okay? So the output once again is going to be 69 00:03:56,880 --> 00:04:00,514 what is the launchers own interval series that you can built, okay? 70 00:04:00,514 --> 00:04:03,190 you can always see that you know there is a symmetry here. 71 00:04:03,190 --> 00:04:06,990 I you have one series, you can reverse it and that's still a solution. 72 00:04:06,990 --> 00:04:10,040 So there are some symmetry. I'm giving you some hint here, okay? 73 00:04:10,040 --> 00:04:13,460 And then the value is basically you know the length of the sequence and then all 74 00:04:13,460 --> 00:04:16,580 the elements in the sequence, okay? The way we check this is we going to 75 00:04:16,580 --> 00:04:20,130 compute all the differences here and make sure that they are all different, okay? 76 00:04:20,130 --> 00:04:26,000 So this is for instance an output, okay? Which is a popular value for this for 77 00:04:26,000 --> 00:04:29,380 this puzzle, okay? So the, the length here is 5 and the 78 00:04:29,380 --> 00:04:34,650 value of 04132, okay? and so when you look at the difference, 79 00:04:34,650 --> 00:04:36,590 okay? So you take 0 and 4, what is the 80 00:04:36,590 --> 00:04:39,969 difference between these two? That's 4, the difference between 4 and 1, 81 00:04:39,969 --> 00:04:44,300 that's 3, okay? 1 and 3 is 2 and, 3 and 2 is 1, okay? 82 00:04:44,300 --> 00:04:50,560 So you have difference of 4, 3, 2 and 1, all these differences are different so 83 00:04:50,560 --> 00:04:53,490 this is a solution, okay? So how far can you go? 84 00:04:53,490 --> 00:04:58,380 What is the largest interval series that you can actually produce? 85 00:04:58,380 --> 00:05:03,070 Okay, very interesting example, okay? Magic Series, we saw this is one of the 86 00:05:03,070 --> 00:05:06,140 examples that I used for rarefied constraints when I was talking about 87 00:05:06,140 --> 00:05:09,218 constraint programming. You know, a sequence of magic, a sequence 88 00:05:09,218 --> 00:05:16,160 X0, X1, Xn is magic, if Xi represents the number of operands of i inside the 89 00:05:16,160 --> 00:05:19,400 series, okay? So, we basically, you know, everyone of 90 00:05:19,400 --> 00:05:23,704 these elements is telling you how many times is 0, appearing in the sequence. 91 00:05:23,704 --> 00:05:26,020 How many there 1 appearing 2 appearing and so on. 92 00:05:26,020 --> 00:05:30,110 Okay, so this is so you can model these constraints using array 5 constraints. 93 00:05:30,110 --> 00:05:32,605 I've covered this, so I won't go into the detail, okay? 94 00:05:32,605 --> 00:05:38,599 But Xi is the sum for all element of the series of the, of basically the rarefied 95 00:05:38,599 --> 00:05:41,760 constraints which tells you if Xi is equal to i, okay? 96 00:05:41,760 --> 00:05:45,100 And when you sum all these things that's the number of occurrences of I and that 97 00:05:45,100 --> 00:05:48,760 is to be equal to Xi, okay? So, the output format once again is 98 00:05:48,760 --> 00:05:51,570 going to be very easy. The length of the series, and then all 99 00:05:51,570 --> 00:05:56,190 the values of the series, okay? So this is a particular Magic Series, 100 00:05:56,190 --> 00:05:58,060 right? So you have two occurrences of 0, one 101 00:05:58,060 --> 00:06:01,125 occurrence of 1, two occurrences of 2, and then 0, 0, okay? 102 00:06:01,125 --> 00:06:05,210 zero occurrences of 3, zero occurrences of 5. 103 00:06:05,210 --> 00:06:10,570 This is a Magic Series, and this is the output format, for that particular 104 00:06:10,570 --> 00:06:14,750 series, okay? So last example, okay? 105 00:06:14,750 --> 00:06:17,730 but not least. This is the Magic Square, actually it's a 106 00:06:17,730 --> 00:06:22,010 variation of the magic square to make it a little bit more interesting, okay? 107 00:06:22,010 --> 00:06:27,300 So you have a square n by n, okay? And you have the values that you give to 108 00:06:27,300 --> 00:06:31,210 every one of these squares is going to be between 1 and n square, okay? 109 00:06:31,210 --> 00:06:35,370 And you have a magic number which is given by this expression here, n times n 110 00:06:35,370 --> 00:06:40,930 square plus 1 divided by 2, okay? So that's the number in which every one 111 00:06:40,930 --> 00:06:45,710 of the sum, and the, the rows and the columns and the diagonals should be equal 112 00:06:45,710 --> 00:06:48,400 to, okay? We're going to put one more constraint 113 00:06:48,400 --> 00:06:53,361 which is basically saying that the value on the diagonal are increasing, okay? 114 00:06:53,361 --> 00:06:55,140 So we're going to see that in a moment, okay? 115 00:06:55,140 --> 00:06:58,370 So that's just to make the problem a little bit harder for you, okay? 116 00:06:58,370 --> 00:07:03,860 So what you see there is basically all the constraints telling you that the row 117 00:07:03,860 --> 00:07:06,800 has to be magic. The column has to be magic. 118 00:07:06,800 --> 00:07:11,264 The diagonals have to be magic. And then the diagonal is increasing, 119 00:07:11,264 --> 00:07:15,020 okay? And obviously all the elements inside the 120 00:07:15,020 --> 00:07:18,380 square have to be different so you have a, you have a permutation. 121 00:07:18,380 --> 00:07:23,350 you have a permutation constraints on every one, on all the numbers 122 00:07:23,350 --> 00:07:26,900 essentially, okay? So this is a, this is a formulation of 123 00:07:26,900 --> 00:07:30,240 the problem here. And so the key point is how big this or 124 00:07:30,240 --> 00:07:34,730 how large a square can you you actually or how large magic squares can you 125 00:07:34,730 --> 00:07:38,970 actually can you actually find, okay? So, the spec here is a little bit more 126 00:07:38,970 --> 00:07:41,050 complicating. It's not a series, it's a square. 127 00:07:41,050 --> 00:07:44,430 So, you would have to say what is the largest size of this square, and then you 128 00:07:44,430 --> 00:07:49,170 will have basically to specify the various, roles of the square, okay? 129 00:07:49,170 --> 00:07:53,790 So, this is going to be a row 1. Row 2, row you know, row N. 130 00:07:53,790 --> 00:07:58,280 And then every one of these row is going to have N elements, if N is the 131 00:07:58,280 --> 00:08:00,890 largest, is the size of the square that you found, okay? 132 00:08:00,890 --> 00:08:04,830 So once again you know in all of these puzzles okay the spec. 133 00:08:04,830 --> 00:08:09,040 The output is really easy, it's just a series or just square or something like 134 00:08:09,040 --> 00:08:12,350 this, okay? So this is a Magic Square of size 3, you 135 00:08:12,350 --> 00:08:16,810 see the value 3 over there and then you see 2, 7, 6 that's basically the first 136 00:08:16,810 --> 00:08:18,890 row. The second one is 9, 5, 1, and the third 137 00:08:18,890 --> 00:08:24,930 one is 4, 3, 8, okay? So that's how you can specify it once 138 00:08:24,930 --> 00:08:26,210 again. You know, you see the square you know 139 00:08:26,210 --> 00:08:33,070 being specified there. Okay, so, assignment three tricks, well, 140 00:08:33,070 --> 00:08:35,815 tips, hints. a lot of, so CP is designed for 141 00:08:35,815 --> 00:08:41,299 feasibility problems, so you may think these problems are good for CP. 142 00:08:41,299 --> 00:08:44,390 So many of these problems have symmetries, not all of them but some of 143 00:08:44,390 --> 00:08:47,350 them have symmetries. You can start breaking it, okay? 144 00:08:47,350 --> 00:08:50,270 Local search you know can also solve feasibility problem, okay? 145 00:08:50,270 --> 00:08:54,820 So you know that, and the way to do that is basically by looking at violations and 146 00:08:54,820 --> 00:08:57,940 decreasing violations. So they maybe, that maybe a technology 147 00:08:57,940 --> 00:09:00,660 which is very appropriate for these particular puzzles. 148 00:09:00,660 --> 00:09:04,410 Integer programming you can think about in terms of violation as well. 149 00:09:04,410 --> 00:09:08,405 You can use these models you know minimizing violation and you can see the 150 00:09:08,405 --> 00:09:10,700 MIP problem. You know a MIP solver can actually 151 00:09:10,700 --> 00:09:14,540 decrease these violations to 0 to satisfy this problem as well. 152 00:09:14,540 --> 00:09:16,400 So you can model them in that particular way. 153 00:09:16,400 --> 00:09:20,130 Once again if you use some of these models local search or MIP you can choose 154 00:09:20,130 --> 00:09:22,550 which constraints are hard and which constraints are soft, okay? 155 00:09:22,550 --> 00:09:27,766 What are you relaxing into the objective function essentially, okay? 156 00:09:27,766 --> 00:09:32,909 have fun, the way we grade this is going to be, is interesting, okay? 157 00:09:32,909 --> 00:09:36,460 So we'll, we'll basically look at the size and if we have a beautiful, 158 00:09:36,460 --> 00:09:40,300 extremely complex formula. To decide how much points you get based 159 00:09:40,300 --> 00:09:42,630 on the size that you are actually contributing. 160 00:09:42,630 --> 00:09:43,560 Okay, great. Thank you. 161 00:09:43,560 --> 00:09:45,170 Have fun. These are fun assignments.