Okay guys, the last thing I want to talk 
about is this Puzzle Challenge, okay? 
So this Puzzle Challenge is one way for 
you to get a better grade, so I guess 
we're going to give you this puzzles, 
okay? 
And they are in Extra Credit. 
It means that essentially you can get 
more points, okay? 
such that you you can you know, increase 
your grade. 
So I, I've always done that everywhere I, 
I, I've been teaching. 
You know, so that you know, I can't have 
an average which is actually, well I can 
have a very high average. 
And at the same time, you know, I can 
actually find out the people who are 
really, really good, okay? 
So, so I'm, we're going to look at 
basically four four puzzles here, okay? 
And the challenge here is going to find 
the largest size that you know, that you 
can solve then, okay? 
we're going to talk about some simple 
ones like the N-Queens, okay? 
Some interesting ones like the old 
interval series, and then the magic 
series, and then the magic square. 
Now there are different degrees of 
difficulty here on how you can scale them 
up. 
But, you know, every one of them is some 
interesting challenge, okay? 
So, and the, the, kind of, the grade 
here, you know, we'll talk about that 
later, is, is basically, you know, the 
largest, you know, solutions that you 
give us. 
You know, the higher the extra credit 
that you get, okay? 
So, you know, the N-Queens we have talked 
about. 
You know, this problem, you know you know 
a lot. 
And the basic idea is you want to place 
these queens so that they don't attack 
each other. 
You know, instead of looking at a board 
of eight by eight, we want to see if you 
can solve problems with, let's say, a 
million queens, right? 
That would be really nice, okay? 
So, so basically Xi, you know the 
decision variable Xi is basically the, 
the role of, in which we are placing 
Queens, the Queen which is on column i. 
We have these constraints that we have to 
satisfy. 
I won't go over them, I have been over 
them for many, many times, okay? 
and so the output format here is going to 
be very simple right? 
The input is you know, we, we don't care. 
We want just the output and the is the 
largest value N that you can you know 
find. 
And then obviously you want to give a 
solution such that we can check it okay? 
So basically give the value of every one 
of these decision variable which is 
basically the row in which column, the, 
the column. 
The row in which the queen on column i is 
basically placed, okay? 
So you give us, you know, column, the row 
of queen, of queen on column zero, the 
row of queens on column one and so on and 
so forth, okay? 
A long list, hopefully this is like, 
billions, a billion, billion value, 
right? 
so this is one of the, one, this is one 
of the output for this particular Queens. 
It's the best you can do is solve five 
Queens, okay? 
So you can tell us, yes, I solved five 
Queens, and these are the results, 0, 2, 
4, 1, 3, okay? 
I don't think that will get you very far, 
in the kind of extra credit that you will 
have, okay? 
so that's the first problem. 
The second problem is really interesting, 
it's called the interval, all interval 
series, okay? 
And the key idea is that you have a 
number between 0 and n-1, okay? 
And you want a permutation of them, so 
that when you look at it as a sequence, 
okay? 
The difference between two elements in 
the sequence, all of the, you know, you 
look at the difference between two 
elements in the sequence. 
And all of them have to be all different, 
and the, the sequence, well, these 
absolute val, all these absolute value 
have to be all different. 
They have to have all different values, 
okay? 
So so this is how you can state it a 
little bit more mathematically, okay? 
So you have this Xi which is telling you 
element i of the sequence, okay? 
So what you want to be sure is, that 
let's say element i of the sequence, Xi. 
You know, and then the previous, the 
previous element of this sequence. 
the next element of this sequence Xi 
minus 1. 
You take the difference between these two 
values. 
And then you take it to you take Xj and 
take Xj plus 1, and make sure that j and 
i are different. 
So these two values, these two difference 
have to be different, okay? 
So, so you don't want the same value for 
these differences, okay? 
And you want that for all the successive 
elements, okay? 
And so, and, and obviously the Xi have to 
be a permutation between 0 and, and, and 
minus 1, okay? 
So the output once again is going to be 
what is the launchers own interval series 
that you can built, okay? 
you can always see that you know there is 
a symmetry here. 
I you have one series, you can reverse it 
and that's still a solution. 
So there are some symmetry. 
I'm giving you some hint here, okay? 
And then the value is basically you know 
the length of the sequence and then all 
the elements in the sequence, okay? 
The way we check this is we going to 
compute all the differences here and make 
sure that they are all different, okay? 
So this is for instance an output, okay? 
Which is a popular value for this for 
this puzzle, okay? 
So the, the length here is 5 and the 
value of 04132, okay? 
and so when you look at the difference, 
okay? 
So you take 0 and 4, what is the 
difference between these two? 
That's 4, the difference between 4 and 1, 
that's 3, okay? 
1 and 3 is 2 and, 3 and 2 is 1, okay? 
So you have difference of 4, 3, 2 and 1, 
all these differences are different so 
this is a solution, okay? 
So how far can you go? 
What is the largest interval series that 
you can actually produce? 
Okay, very interesting example, okay? 
Magic Series, we saw this is one of the 
examples that I used for rarefied 
constraints when I was talking about 
constraint programming. 
You know, a sequence of magic, a sequence 
X0, X1, Xn is magic, if Xi represents the 
number of operands of i inside the 
series, okay? 
So, we basically, you know, everyone of 
these elements is telling you how many 
times is 0, appearing in the sequence. 
How many there 1 appearing 2 appearing 
and so on. 
Okay, so this is so you can model these 
constraints using array 5 constraints. 
I've covered this, so I won't go into the 
detail, okay? 
But Xi is the sum for all element of the 
series of the, of basically the rarefied 
constraints which tells you if Xi is 
equal to i, okay? 
And when you sum all these things that's 
the number of occurrences of I and that 
is to be equal to Xi, okay? 
So, the output format once again is 
going to be very easy. 
The length of the series, and then all 
the values of the series, okay? 
So this is a particular Magic Series, 
right? 
So you have two occurrences of 0, one 
occurrence of 1, two occurrences of 2, 
and then 0, 0, okay? 
zero occurrences of 3, zero occurrences 
of 5. 
This is a Magic Series, and this is the 
output format, for that particular 
series, okay? 
So last example, okay? 
but not least. 
This is the Magic Square, actually it's a 
variation of the magic square to make it 
a little bit more interesting, okay? 
So you have a square n by n, okay? 
And you have the values that you give to 
every one of these squares is going to be 
between 1 and n square, okay? 
And you have a magic number which is 
given by this expression here, n times n 
square plus 1 divided by 2, okay? 
So that's the number in which every one 
of the sum, and the, the rows and the 
columns and the diagonals should be equal 
to, okay? 
We're going to put one more constraint 
which is basically saying that the value 
on the diagonal are increasing, okay? 
So we're going to see that in a moment, 
okay? 
So that's just to make the problem a 
little bit harder for you, okay? 
So what you see there is basically all 
the constraints telling you that the row 
has to be magic. 
The column has to be magic. 
The diagonals have to be magic. 
And then the diagonal is increasing, 
okay? 
And obviously all the elements inside the 
square have to be different so you have 
a, you have a permutation. 
you have a permutation constraints on 
every one, on all the numbers 
essentially, okay? 
So this is a, this is a formulation of 
the problem here. 
And so the key point is how big this or 
how large a square can you you actually 
or how large magic squares can you 
actually can you actually find, okay? 
So, the spec here is a little bit more 
complicating. 
It's not a series, it's a square. 
So, you would have to say what is the 
largest size of this square, and then you 
will have basically to specify the 
various, roles of the square, okay? 
So, this is going to be a row 1. 
Row 2, row you know, row N. 
And then every one of these row is 
going to have N elements, if N is the 
largest, is the size of the square that 
you found, okay? 
So once again you know in all of these 
puzzles okay the spec. 
The output is really easy, it's just a 
series or just square or something like 
this, okay? 
So this is a Magic Square of size 3, you 
see the value 3 over there and then you 
see 2, 7, 6 that's basically the first 
row. 
The second one is 9, 5, 1, and the third 
one is 4, 3, 8, okay? 
So that's how you can specify it once 
again. 
You know, you see the square you know 
being specified there. 
Okay, so, assignment three tricks, well, 
tips, hints. 
a lot of, so CP is designed for 
feasibility problems, so you may think 
these problems are good for CP. 
So many of these problems have 
symmetries, not all of them but some of 
them have symmetries. 
You can start breaking it, okay? 
Local search you know can also solve 
feasibility problem, okay? 
So you know that, and the way to do that 
is basically by looking at violations and 
decreasing violations. 
So they maybe, that maybe a technology 
which is very appropriate for these 
particular puzzles. 
Integer programming you can think about 
in terms of violation as well. 
You can use these models you know 
minimizing violation and you can see the 
MIP problem. 
You know a MIP solver can actually 
decrease these violations to 0 to satisfy 
this problem as well. 
So you can model them in that particular 
way. 
Once again if you use some of these 
models local search or MIP you can choose 
which constraints are hard and which 
constraints are soft, okay? 
What are you relaxing into the objective 
function essentially, okay? 
have fun, the way we grade this is 
going to be, is interesting, okay? 
So we'll, we'll basically look at the 
size and if we have a beautiful, 
extremely complex formula. 
To decide how much points you get based 
on the size that you are actually 
contributing. 
Okay, great. 
Thank you. 
Have fun. 
These are fun assignments.