And the answer is, yes I can, okay? Why?

Well, we know because of this beautiful pigeonhole principle, that if I look only

at x1 and x2, I have two variables, and they can only take two value, 1 and 2,

okay? Therefore, if x3, the friendly x3,

actually take either 1 or 2. No, we won't find a solution, okay.

So what you have to, what you can deduce easily, is that x3 cannot be 1 and cannot

be 2 it has therefore to be 3, okay. And therefore, you reuse the search

space, you know. X1 and x2 can take either 1 or 2,

provided they have a different values, okay.

So the only pruning that you can get is remove the, removing the value from 1 and

2. Okay?

Now, that's the pruning that we can get. But once again, if you don't express the

global constraint, if you use the composition here in terms of pair wise

constraints, you would not prune anything.

Okay? Because essentially, for x3, you know,

when you look at x3. X3 and x1, well they can, you know, x, x3

can take the value 1 and x2 and x1 can take the value 2 and that's fine.

X3 can take the value 1 and x2 can take the value 2 and that's fine as well.

So you never detect that you actually have to remove the value one and two from

x3. So the second big benefits of global

constraints. Not only do they detect feasibility

sooner, but they also actually, make it possible to prune the search space more.

They remove value from the domain of the variable.

And why is that important? Because now the domain are smaller

another constraint can come in and do more reasoning and maybe find an

inconsistency or maybe prune new values from the domain which will in, in turn

probably find some inconsistency or some more values from the domain, okay.

So, this fixed point is very important. That's why you remove the search space as

much you can. Okay?

So the million dollar question though is what?

Can I actually, you know, detect feasibility and achieve this optimal

pruning for this global constraint? Okay.

And the answer to that sometimes we can, sometimes we cannot.

Okay. So sometimes we will able, we will be

able to detect feasibility and I will show you examples of that.

And sometimes you will have to relax your standards.

Okay, which basically means that you won't be able to prune everything or you

won't be able to detect insatisfiability all the time.

but, but you will still get some pruning and detect visibility early, okay.

the other thing that you can say is I'm going to sacrifice computation time and

essentially some of these algorithms and one of my students became an expert in

finding exponential algorithm from pruning constraints, okay?

And what, what you do there is you sacrifice time but you will have the

optimal pruning. You will detect infeasibility as soon as

you can, okay? So the answer here is sometimes some

global constraints you will be able to deal with very efficiently, sometimes you

will have to relax your standards. Okay, now I told you when, you know, in

the advertisement of this class that, you know, you will never have to solve a

sudoku in your life, okay? And I'm going to keep that promise, okay?

And so this is a sudoku and we want to solve it using constraint programming.

Okay? So this is a very simple model on how to

do that. Okay?

So the decision variables are very easy right?

So you look at everyone of these square, little square everywhere.

You know, there will be a decision variable associated with that and that

decision variable will be the number which is associated to that square.

Okay? The digit.

Okay? So essentially that's what you see there.

You know these are the decision variables over there.

Okay, they are basically [UNKNOWN] a matrix of, of, of variables, and these

variables take the value between one and nine.

Okay? Now, the constraints of these problems,

you will have different types of constraints.

The first set of constraints will be the fixed position.

Okay. So when you look at this thing, there are

a bunch of fixed positions all over the place.

We'll have to fix these values, these variables to these values.

And then once again, we have only three types of constraints, okay.

Well, actually one type of constraint but three different ways of stating that,

okay. So we have only alldifferent constraints,

but some of them are going to be on the rows, some of them are going to be down

the column and some of them are going to be on the squares, okay.

So when you look at the first one. Essentially that constraint, is basically

stating, that all the values on a particular row have to be different.

The second one is basically saying that all of the values in a column have to be

different. And the third one is basically, you know,

you look at the square, you know, three by three there, and you are expressing

that all these values have to be different.

These are the constraints of the Sudoku and that's all you have to do.

So this simple program. Is why is at least part of the reason why

I would never do a sudoku in my life, right?

You know it's so simple, right? So the next thing that I want to show you

is actually this is a very efficient way of actually solving this thing.

Okay, so look at this puzzle. Okay so the first time I run the program,

I traced it on this particular example. It deduced that, of course it, it fixed

all these position, and then it deduced that this value has to be 2, okay?

Now, that's very interesting, okay? So, I was like how did it do that?

Okay? And so you have to look at a couple of

things, okay? So, you see, you know, there is there is

a 2 over there. Right?

So, which basically means that I cannot put a 2 over here, okay?

There is no way I can do that. Okay, and then you have a two over here,

which basically means it can't have any two on this last line, okay?

So the tree position where I can actually put a two is here and these two gaps,

right? Okay?

So but look at, look at the, the square here in the middle.

Once again, I know that I have a two and therefore, I cannot put a value over

there, okay? Now I also know, what do I know?

Okay. So I know that I have a 2 over here.

So these guys here, cannot get a value of 2.

So the only two positions where I can get a 2 here, is these two guys.

Okay. These 2 guys can take a two.

I don't know which one, right? Okay?

But at least one of them has to take a 2. Therefore what I know is this guy, cannot

have a 2 over here. Okay?

And therefore, the last position at which it's get a, get a 2 is over there.

That's what the system did. That's what this pruning for the all

different constraints were able to do. It's magical, right?

Okay, so if you do that, then it's going to know, going to continue deriving

all these values all over the place. That's what it gets, just propagating

these constraints, okay? And then, the system will make a choice.

It will assign the value 5 at the top over there.

Choop! Here.

And that it will make more deduction than when you assign one more value over here,

okay? So there's a value of 4.

And then propagate and find a solution, and that's it.

Two choice, no back-track, solution immediately.

Okay. Now you have to know that sudokus are

easy for us, and the reason is that they have to be easy for human, which

basically means that human don't like to make choices, so these sudoku are

actually designed so that you can mostly deduce the solution and don't go into

exploring a huge tree. That's why these things are really easy

for constraint programming in general. Okay, so, so we have seen now essentially

global constraints and global constraints are these very important area of

constraint programming. There are a lot of people actually

exploring this. Okay?

And, I want, I want to show you one more type of constraint which is the table

constraint. And it's probably the simplest global

constraint, okay? And so this is an example for you to

understand. I have three variables okay?

x, y, and z, okay? This is the domain of the variable 1, 2

1, 2, and then 3 ,4 ,5 for, for z. Okay?

And then essentially one of the things we can think of is, you know, what are the

possible combination of all these variables, okay?

What are the total possibilities? And essentially there are 12 of them,

okay? So you could see each product between,

you know, the domain of x, the domain of y, and the domain of z, okay?

So that's what we have, okay? So in this particular case there are 12

possibilities. So what a table constraints is doing, is

actually specify a subset of these possibilities as the legal, you know,

assignment of these variables. So, in this particular case, we have four

of them, okay. So you see that the first one is 1, 1, 5.

X is equal to 1, Y is equal to 1, and Z is equal to 5.

The second one is 1, 2, 4. That's what you see here, okay.

And so in this particular case, the legal combination is 1 for x, 2 for y, and 4

for z. Okay.

And so once again what is interesting to see is what happens when you get more

information. Okay.

So assume that I have more information about z.

What's going to happen? Well, I know that z cannot be equal to 5.

What does that mean? Okay, so the value z there is not legal

anymore. I have to remove that combination.

I have to remove all the combinations where I have actually z is equal to 5.

There is only one here, okay? And now, essentially, I look at the, I

look at the other variables, and what do I see?

Look at this guy, look at y. The only value which is left in the

column of y is 2. So I can immediately deduce that, in a

sense, y has to be 2 and the value, you know, and this is what this reflect here,

okay? So, so, in a sense, y has to be different

from y, it can only be 2, okay? So that's essentially the table

constraints. Once again, it's a very useful

constraint. It always specify a subset of a cartesian

product. For all the variables.

Okay? So let me conclude this lecture by one

more thing, okay? which is how can we find optimal solution

in using a constraint programming? So remember we discuss graph coloring or

map coloring actually In the first two lectures, okay?

And so what, what I'm doing here is generalizing a little bit of that

example, okay? And instead of using colors, I'm using a

number from 1 to 4, and what I'm going to do now is not only color this country

such that they get a different color, in particular, in this particular case a

number between 1 and 4. But I also want to minimize the number of

colors that I'm using. Okay?

So basically here, I'm basically saying, okay, minimize, okay, what the maximum

color that this variables can subject to the fact that two adjacent countries have

to be colored differently, okay? So, I can do that.

Okay, so that's a model which is essentially optimizing the number of

colors that I have to use. In all the possit-.

Selecting essentially the solution, the feasible solution, which uses the, the

fewest colors, okay? How do I do that?

In constraint programming, as I told you, the focus is on feasibility.

And what you do when you're trying to optimize is you're trying to reduce

optimization problem to feasibility. You essentially solve a sequence of

feasibility problems. You find a solution and then you put an

additional constraint which says, oh, but the next solution is to be better than

the one that I just found. Okay so when we find a solution with four

color we are going to say I want to find a solution which you're only using three

colors. Okay, so we are guaranteed to find an

optimal solution. You know, theoretically.

You know, in practice it may take too long, okay and this is going to be a

strong method when essentially the constraints are too hard, that you add as

essentially a strong pruning, okay, and this happens in a variety of problems in

results, allocation and scheduling, and we'll come to these problems at some

point in this class. Okay.

Thank you. That's it for today.