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.