1
00:00:00,270 --> 00:00:02,364
Okay guys. 
You know, I talked about the language of 

2
00:00:02,364 --> 00:00:05,883
constraint programming the last time and 
that I was presenting an overview of what 

3
00:00:05,883 --> 00:00:08,189
it is. 
You know, I lied. 

4
00:00:08,189 --> 00:00:10,320
Okay. 
So there is one more thing that I need 

5
00:00:10,320 --> 00:00:14,690
about, that I need to talk to you about 
and this is global constraints. 

6
00:00:14,690 --> 00:00:16,850
Okay? 
So global constraints are one really 

7
00:00:16,850 --> 00:00:21,104
important feature of the language of 
constraint programming. 

8
00:00:21,104 --> 00:00:25,124
They are part of this richness and the 
ability to express complex substructure, 

9
00:00:25,124 --> 00:00:27,650
okay. 
They are a critical path of any 

10
00:00:27,650 --> 00:00:31,570
constraint programming system and this is 
a very active, you know, research area in 

11
00:00:31,570 --> 00:00:34,900
the field, okay. 
So, what is the global constraints? 

12
00:00:34,900 --> 00:00:39,148
The global constraints capture the, the, 
the combinatorial substructure arising in 

13
00:00:39,148 --> 00:00:42,500
many applications. 
So, the good analogy here. 

14
00:00:42,500 --> 00:00:44,640
Is essentially Lego blocks. 
Okay? 

15
00:00:44,640 --> 00:00:47,608
So you, when, when you buy Legos, you 
have a big set of pieces that are 

16
00:00:47,608 --> 00:00:51,010
encapsulate things that you want to build 
from. 

17
00:00:51,010 --> 00:00:55,132
Global constraints are exactly like that. 
They are capturing substructure that are, 

18
00:00:55,132 --> 00:00:57,870
that are arising in a variety of 
application. 

19
00:00:57,870 --> 00:01:00,680
And we can use them directly. 
We don't have to express them in terms of 

20
00:01:00,680 --> 00:01:02,350
smaller blocks. 
Okay? 

21
00:01:02,350 --> 00:01:05,640
They make modeling, you know, easier, 
they are more natural. 

22
00:01:05,640 --> 00:01:09,880
They make the model easier to read, they 
make the model more concise. 

23
00:01:09,880 --> 00:01:13,479
But, the real, real interesting aspect of 
them is also the fact that these 

24
00:01:13,479 --> 00:01:17,770
combinatorial substructure are really 
given to the solver. 

25
00:01:17,770 --> 00:01:22,020
We capture this structure and we give 
them, you know, directly to the solver. 

26
00:01:22,020 --> 00:01:24,910
And then the solver has a lot of 
information to do interesting things. 

27
00:01:24,910 --> 00:01:28,420
And in particular, it gives the solver 
the ability to use dedicated algorithm 

28
00:01:28,420 --> 00:01:32,530
for each one of these substructure. 
So I'm going to give you examples. 

29
00:01:32,530 --> 00:01:35,421
First, you know, I'm going to show you 
the modeling and then I'm going to tell 

30
00:01:35,421 --> 00:01:39,910
you how these things can actually help 
you from a computational standpoint. 

31
00:01:39,910 --> 00:01:42,660
So, what you see here is probably the 
most famous, you know, global 

32
00:01:42,660 --> 00:01:45,477
constraints, the alldifferent 
constraints. 

33
00:01:45,477 --> 00:01:48,857
And these constraints is basically saying 
that the variable x1 to xn have to be 

34
00:01:48,857 --> 00:01:52,460
given a value, have to be given all 
different values. 

35
00:01:52,460 --> 00:01:56,355
So no two variables in x1 and xn can, can 
take the same value. 

36
00:01:56,355 --> 00:01:58,763
Okay? 
Now remember, you know, we had this 

37
00:01:58,763 --> 00:02:01,500
beautiful queens example in the previous 
lectures? 

38
00:02:01,500 --> 00:02:03,411
Okay? 
And what that was basically saying is 

39
00:02:03,411 --> 00:02:06,800
that all these queens, okay, have to be 
placed on the chessboard. 

40
00:02:06,800 --> 00:02:09,761
Such that they were not on the same row, 
the same upward diagonal and the same 

41
00:02:09,761 --> 00:02:11,655
downward diagonal. 
Okay? 

42
00:02:11,655 --> 00:02:14,625
Well, you can essentially express the 
same example with three constraints and 

43
00:02:14,625 --> 00:02:18,625
that's what you see there, okay. 
Same decision variable but now instead of 

44
00:02:18,625 --> 00:02:22,255
saying all these rows, you know, in which 
the, you know, the queens were placed, 

45
00:02:22,255 --> 00:02:27,536
had to be, you know, pairwise different. 
You just specify one constraint which 

46
00:02:27,536 --> 00:02:30,400
says all the rows have to be different. 
Okay. 

47
00:02:30,400 --> 00:02:33,040
That's what you said. 
That's what you are stating there. 

48
00:02:33,040 --> 00:02:35,830
Now, if you look at the other 
constraints, these guys, okay. 

49
00:02:35,830 --> 00:02:40,810
So what you see once again is that, you 
know, you see row i plus i, row j plus j. 

50
00:02:40,810 --> 00:02:44,470
Essentially what it is that you have a 
bunch of expression row i plus i row j 

51
00:02:44,470 --> 00:02:48,190
plus j row k plus k and essentially all 
these things have to be different and 

52
00:02:48,190 --> 00:02:52,865
that's what you express in this 
constraint. 

53
00:02:52,865 --> 00:02:56,268
Okay? 
And so that's once again a-alldifferent 

54
00:02:56,268 --> 00:02:57,488
constraints. 
Okay? 

55
00:02:57,488 --> 00:03:00,816
And these all different constraints is 
going to capture the upper diagonal and 

56
00:03:00,816 --> 00:03:03,988
you'll have the last alldifferent 
constraint which is going to capture the 

57
00:03:03,988 --> 00:03:07,622
lower bound. 
Now you see that this operator all over 

58
00:03:07,622 --> 00:03:11,412
there, essentially this is [INAUDIBLE] 
comprehension, okay. 

59
00:03:11,412 --> 00:03:14,400
So essentially what it says is take all i 
in r, okay? 

60
00:03:14,400 --> 00:03:17,750
Take the, the collection of expressions 
that you see over there, which is in this 

61
00:03:17,750 --> 00:03:20,950
particular case, you know, row i plus i, 
and collect all these in an array, and 

62
00:03:20,950 --> 00:03:25,610
then that's, that's the array that you 
have as a result, okay? 

63
00:03:25,610 --> 00:03:27,966
In this particular case, this array's 
going to be passed to the alldifferent 

64
00:03:27,966 --> 00:03:30,408
constraints, okay? 
So, essentially, this is collecting a 

65
00:03:30,408 --> 00:03:33,060
bunch of things, and then saying that all 
these variables, or expression, in this 

66
00:03:33,060 --> 00:03:37,252
particular case, have to be different. 
Okay, so in a sense we can express this 

67
00:03:37,252 --> 00:03:40,306
screen problem with three constraints. 
Okay? 

68
00:03:40,306 --> 00:03:43,655
Now why would we ever do that? 
It seems more complicated and so on but 

69
00:03:43,655 --> 00:03:48,140
what I'm going to show you is that this 
has a lot of computational advantages. 

70
00:03:48,140 --> 00:03:50,900
Okay, so let's look. 
You know, you know from now on from, you 

71
00:03:50,900 --> 00:03:55,030
know, previous lecture that every 
constraints has two goals in life. 

72
00:03:55,030 --> 00:03:58,190
The first goal is to, is to do 
feasibility testing. 

73
00:03:58,190 --> 00:04:00,760
You want to know if the constraints is 
feasible. 

74
00:04:00,760 --> 00:04:02,799
Okay? 
Remember we had a constraints. 

75
00:04:02,799 --> 00:04:05,860
We have essentially for every one of the 
variables the domain. 

76
00:04:05,860 --> 00:04:08,360
Okay, so that's a set of values that a 
variable can take. 

77
00:04:08,360 --> 00:04:10,699
Okay? 
So, we often use this notation here, you 

78
00:04:10,699 --> 00:04:13,879
know, this is a constraint and then we 
said that d1 is the domain of x, of x1 

79
00:04:13,879 --> 00:04:17,570
and then d2 is the domain of x2 and so 
on. 

80
00:04:17,570 --> 00:04:19,690
Okay? 
So, what is feasibility? 

81
00:04:19,690 --> 00:04:22,940
Feasibility is finding a value in this 
domain such that when the variables are 

82
00:04:22,940 --> 00:04:26,390
assigned it's variables the constraint is 
satisfied and that's essentially what 

83
00:04:26,390 --> 00:04:32,139
this formula is basically telling you. 
Does there exist a value in the domain of 

84
00:04:32,139 --> 00:04:33,240
x1? 
Okay? 

85
00:04:33,240 --> 00:04:37,660
Such that, and there, there, such that if 
I, so that I can find another value for 

86
00:04:37,660 --> 00:04:43,360
the you know, v2 in the domain of x2, and 
v3 in the domain of x3. 

87
00:04:43,360 --> 00:04:46,150
Such that, when I assign all these values 
to the cons, to the variable of the 

88
00:04:46,150 --> 00:04:50,015
constraint, the constraint is true. 
That's feasibility testing. 

89
00:04:50,015 --> 00:04:52,322
Okay? 
Now, let's look at this constraint here, 

90
00:04:52,322 --> 00:04:54,935
okay? 
So, we have the alldifferent, okay, which 

91
00:04:54,935 --> 00:04:58,978
is on three variables, x1, x2, x3. 
You know, cannot be much simpler than 

92
00:04:58,978 --> 00:05:01,144
that, okay? 
And then, for every one of these 

93
00:05:01,144 --> 00:05:04,731
variable, okay, so, we have a domain. 
And in this particular case, three 

94
00:05:04,731 --> 00:05:07,872
variables with a very simple domain, 
value 1 and value 2. 

95
00:05:07,872 --> 00:05:10,393
Okay? 
Now, so in a sense, all different and 

96
00:05:10,393 --> 00:05:13,105
then these other domains. 
Okay? 

97
00:05:13,105 --> 00:05:14,632
Is this feasible? 
Okay. 

98
00:05:14,632 --> 00:05:15,597
No, it's not. 
Okay. 

99
00:05:15,597 --> 00:05:18,861
Why is not feasible.Okay. 
It's not feasible because we have three 

100
00:05:18,861 --> 00:05:21,155
variables and we have two values. 
Okay? 

101
00:05:21,155 --> 00:05:24,438
So people in computer science code, that 
the pigeon hole principle, I have never 

102
00:05:24,438 --> 00:05:28,600
seen a pigeon in a hole but anyway. 
So this is the pigeon hole principle. 

103
00:05:28,600 --> 00:05:31,309
Probably pigeons are looking for holes 
and if you have three pigeons and two 

104
00:05:31,309 --> 00:05:34,440
holes, they can't all fit in the hole. 
Okay, in the holes. 

105
00:05:34,440 --> 00:05:37,640
Okay, so is, in a sense here what it's 
telling you, three variables two value, 

106
00:05:37,640 --> 00:05:40,630
impossible. 
You can't have feasibility. 

107
00:05:40,630 --> 00:05:42,848
Right? 
So we know that the global constraints is 

108
00:05:42,848 --> 00:05:45,790
going to say no, no, no, this is not 
feasible. 

109
00:05:45,790 --> 00:05:47,670
Okay. 
Now, if we look at, you know, the first 

110
00:05:47,670 --> 00:05:50,634
formulation that we had when we were 
using the queen's example we had 

111
00:05:50,634 --> 00:05:54,850
essentially three constraints to express 
the same thing. 

112
00:05:54,850 --> 00:05:57,360
Right? 
So we said x1 can not be equal to x2. 

113
00:05:57,360 --> 00:06:01,334
X2 cannot be equal to x3 and that x3 
cannot be equal to x1. 

114
00:06:01,334 --> 00:06:04,670
Now if you look at every one of these 
constraints independently. 

115
00:06:04,670 --> 00:06:06,514
Okay. 
Do the same test that we just did for the 

116
00:06:06,514 --> 00:06:08,737
that alldifferent. 
What do you get? 

117
00:06:08,737 --> 00:06:10,835
Well. 
For the first constraint I can take the 

118
00:06:10,835 --> 00:06:15,370
value 1 for x1 and the value 2 for X2 and 
this constraint is fine. 

119
00:06:15,370 --> 00:06:16,540
It's satisfied. 
Okay. 

120
00:06:16,540 --> 00:06:19,960
You look at the second constraint and you 
can do exactly the same trick. 

121
00:06:19,960 --> 00:06:22,830
Of course this time is the value x2 and 
the value x3. 

122
00:06:22,830 --> 00:06:25,070
Okay? 
But essentially it's true as well. 

123
00:06:25,070 --> 00:06:28,034
And the third constraint is true as well. 
So all these constraints, when you look 

124
00:06:28,034 --> 00:06:30,760
at them independently, they are fine. 
Okay? 

125
00:06:30,760 --> 00:06:33,887
So, the system is going to say, yeah, you 
know, the set of constraints look 

126
00:06:33,887 --> 00:06:35,680
satisfiable. 
Okay? 

127
00:06:35,680 --> 00:06:37,620
Although we know for sure that they are 
not. 

128
00:06:37,620 --> 00:06:40,072
Okay? 
So, that's one of the big impact of 

129
00:06:40,072 --> 00:06:42,730
global constraints. 
Okay? 

130
00:06:42,730 --> 00:06:46,340
They can actually detect infeasibility 
earlier in the search space. 

131
00:06:46,340 --> 00:06:49,315
Therefore, they make your search space 
smaller, and your search more efficient. 

132
00:06:49,315 --> 00:06:52,376
Okay? 
So, in a sense if you think about it, 

133
00:06:52,376 --> 00:06:55,240
this is the computation model of 
constraint programming. 

134
00:06:55,240 --> 00:06:56,483
Right? 
So, you have this domain store, it has 

135
00:06:56,483 --> 00:06:59,474
the domain of the variables. 
And gravitating around if you have all 

136
00:06:59,474 --> 00:07:02,190
the constraints. 
These constraints only talk to the domain 

137
00:07:02,190 --> 00:07:04,160
store. 
They don't talk about each other. 

138
00:07:04,160 --> 00:07:07,394
And because of that, if you handle them 
independently, they don't necessarily 

139
00:07:07,394 --> 00:07:08,820
communicate. 
Right? 

140
00:07:08,820 --> 00:07:11,330
So, they can talk to the same domain, and 
that's what you see. 

141
00:07:11,330 --> 00:07:12,864
Right? 
So this is the first constraint, talking 

142
00:07:12,864 --> 00:07:15,361
to this two domain. 
The second constraints have a domain in 

143
00:07:15,361 --> 00:07:18,355
common, and another one. 
The two constraints have again another 

144
00:07:18,355 --> 00:07:22,090
domain in common and another one. 
And so you see that they are all linked. 

145
00:07:22,090 --> 00:07:24,100
The path can be long, but they are all 
linked. 

146
00:07:24,100 --> 00:07:27,510
But when you reason about them 
independently, you lose that length. 

147
00:07:27,510 --> 00:07:29,848
Okay? 
What the global constraints is saying, 

148
00:07:29,848 --> 00:07:33,040
okay, so let's encapsulate all these 
constraints inside one global 

149
00:07:33,040 --> 00:07:36,680
constraints, which talks to all the these 
domains at the same time and now I can 

150
00:07:36,680 --> 00:07:40,665
actually detect infeasibility. 
Okay? 

151
00:07:40,665 --> 00:07:44,493
So, so now we have done only the first 
thing that a constraint does for a 

152
00:07:44,493 --> 00:07:46,330
living. 
Right? 

153
00:07:46,330 --> 00:07:48,970
Which is testing feasibility. 
The other thing a constraint does for 

154
00:07:48,970 --> 00:07:51,561
living is pruning. 
We want to look at these domains and see 

155
00:07:51,561 --> 00:07:54,520
if we can knock down some of these 
values, okay? 

156
00:07:54,520 --> 00:07:57,800
Because that reduces search space, also 
make the search more effiecient. 

157
00:07:57,800 --> 00:08:01,582
Okay, so the question that we have is 
given a variable a value vi inside the 

158
00:08:01,582 --> 00:08:05,740
domain of variable x i. 
Okay, can I use sin, the value of vi to 

159
00:08:05,740 --> 00:08:09,083
xi and still find the solution to that 
constraint. 

160
00:08:09,083 --> 00:08:11,120
Okay? 
So in a sense what that means is that I'm 

161
00:08:11,120 --> 00:08:14,750
assigning vi to xi but I want to find out 
if that value seems dominant of the other 

162
00:08:14,750 --> 00:08:17,335
variables such that the overall 
constraints is going to be 

163
00:08:17,335 --> 00:08:21,360
satisfied.Okay? 
So how do I do that? 

164
00:08:21,360 --> 00:08:25,000
This is the formula right? 
So I'm assigning xi to the i, okay? 

165
00:08:25,000 --> 00:08:27,380
And then I want to find a value v1 for 
v1. 

166
00:08:27,380 --> 00:08:31,070
Value v, i minus 1. 
Inside, you know? 

167
00:08:31,070 --> 00:08:34,710
For, for the variable xi minus one. 
And so on and so forth, such that this 

168
00:08:34,710 --> 00:08:39,030
constraint is true, okay? 
So I pick up one variable, one value. 

169
00:08:39,030 --> 00:08:41,730
And then I see if I can verify find 
values in the other domain of the 

170
00:08:41,730 --> 00:08:44,406
variable. 
In the domain of the other variable such 

171
00:08:44,406 --> 00:08:47,650
that the constraint is satisfied, okay? 
So look at this, okay? 

172
00:08:47,650 --> 00:08:49,720
So this is once again alldifferent 
constraints. 

173
00:08:49,720 --> 00:08:53,624
Now I have three domains, one two for 
variable x1, one two for variable x2, and 

174
00:08:53,624 --> 00:08:57,480
then one through three for variable x3, 
okay? 

175
00:08:57,480 --> 00:09:01,729
And I'm asking you, can I actually prune 
the search space, okay? 

176
00:09:03,230 --> 00:09:06,910
And the answer is, yes I can, okay? 
Why? 

177
00:09:06,910 --> 00:09:10,854
Well, we know because of this beautiful 
pigeonhole principle, that if I look only 

178
00:09:10,854 --> 00:09:14,392
at x1 and x2, I have two variables, and 
they can only take two value, 1 and 2, 

179
00:09:14,392 --> 00:09:18,533
okay? 
Therefore, if x3, the friendly x3, 

180
00:09:18,533 --> 00:09:23,240
actually take either 1 or 2. 
No, we won't find a solution, okay. 

181
00:09:23,240 --> 00:09:26,620
So what you have to, what you can deduce 
easily, is that x3 cannot be 1 and cannot 

182
00:09:26,620 --> 00:09:30,940
be 2 it has therefore to be 3, okay. 
And therefore, you reuse the search 

183
00:09:30,940 --> 00:09:33,315
space, you know. 
X1 and x2 can take either 1 or 2, 

184
00:09:33,315 --> 00:09:36,130
provided they have a different values, 
okay. 

185
00:09:36,130 --> 00:09:39,705
So the only pruning that you can get is 
remove the, removing the value from 1 and 

186
00:09:39,705 --> 00:09:41,110
2. 
Okay? 

187
00:09:41,110 --> 00:09:44,586
Now, that's the pruning that we can get. 
But once again, if you don't express the 

188
00:09:44,586 --> 00:09:47,706
global constraint, if you use the 
composition here in terms of pair wise 

189
00:09:47,706 --> 00:09:51,100
constraints, you would not prune 
anything. 

190
00:09:51,100 --> 00:09:53,584
Okay? 
Because essentially, for x3, you know, 

191
00:09:53,584 --> 00:09:57,030
when you look at x3. 
X3 and x1, well they can, you know, x, x3 

192
00:09:57,030 --> 00:10:02,020
can take the value 1 and x2 and x1 can 
take the value 2 and that's fine. 

193
00:10:02,020 --> 00:10:06,310
X3 can take the value 1 and x2 can take 
the value 2 and that's fine as well. 

194
00:10:06,310 --> 00:10:09,510
So you never detect that you actually 
have to remove the value one and two from 

195
00:10:09,510 --> 00:10:11,810
x3. 
So the second big benefits of global 

196
00:10:11,810 --> 00:10:14,170
constraints. 
Not only do they detect feasibility 

197
00:10:14,170 --> 00:10:19,160
sooner, but they also actually, make it 
possible to prune the search space more. 

198
00:10:19,160 --> 00:10:21,480
They remove value from the domain of the 
variable. 

199
00:10:21,480 --> 00:10:24,512
And why is that important? 
Because now the domain are smaller 

200
00:10:24,512 --> 00:10:27,876
another constraint can come in and do 
more reasoning and maybe find an 

201
00:10:27,876 --> 00:10:31,646
inconsistency or maybe prune new values 
from the domain which will in, in turn 

202
00:10:31,646 --> 00:10:38,000
probably find some inconsistency or some 
more values from the domain, okay. 

203
00:10:38,000 --> 00:10:40,968
So, this fixed point is very important. 
That's why you remove the search space as 

204
00:10:40,968 --> 00:10:42,700
much you can. 
Okay? 

205
00:10:42,700 --> 00:10:44,620
So the million dollar question though is 
what? 

206
00:10:44,620 --> 00:10:47,806
Can I actually, you know, detect 
feasibility and achieve this optimal 

207
00:10:47,806 --> 00:10:50,790
pruning for this global constraint? 
Okay. 

208
00:10:50,790 --> 00:10:53,890
And the answer to that sometimes we can, 
sometimes we cannot. 

209
00:10:53,890 --> 00:10:55,620
Okay. 
So sometimes we will able, we will be 

210
00:10:55,620 --> 00:10:59,520
able to detect feasibility and I will 
show you examples of that. 

211
00:10:59,520 --> 00:11:01,790
And sometimes you will have to relax your 
standards. 

212
00:11:01,790 --> 00:11:05,822
Okay, which basically means that you 
won't be able to prune everything or you 

213
00:11:05,822 --> 00:11:10,120
won't be able to detect insatisfiability 
all the time. 

214
00:11:10,120 --> 00:11:15,020
but, but you will still get some pruning 
and detect visibility early, okay. 

215
00:11:15,020 --> 00:11:18,188
the other thing that you can say is I'm 
going to sacrifice computation time and 

216
00:11:18,188 --> 00:11:21,356
essentially some of these algorithms and 
one of my students became an expert in 

217
00:11:21,356 --> 00:11:25,760
finding exponential algorithm from 
pruning constraints, okay? 

218
00:11:25,760 --> 00:11:28,781
And what, what you do there is you 
sacrifice time but you will have the 

219
00:11:28,781 --> 00:11:32,271
optimal pruning. 
You will detect infeasibility as soon as 

220
00:11:32,271 --> 00:11:34,520
you can, okay? 
So the answer here is sometimes some 

221
00:11:34,520 --> 00:11:37,036
global constraints you will be able to 
deal with very efficiently, sometimes you 

222
00:11:37,036 --> 00:11:41,085
will have to relax your standards. 
Okay, now I told you when, you know, in 

223
00:11:41,085 --> 00:11:45,117
the advertisement of this class that, you 
know, you will never have to solve a 

224
00:11:45,117 --> 00:11:51,210
sudoku in your life, okay? 
And I'm going to keep that promise, okay? 

225
00:11:51,210 --> 00:11:54,475
And so this is a sudoku and we want to 
solve it using constraint programming. 

226
00:11:54,475 --> 00:11:56,738
Okay? 
So this is a very simple model on how to 

227
00:11:56,738 --> 00:11:58,170
do that. 
Okay? 

228
00:11:58,170 --> 00:12:00,400
So the decision variables are very easy 
right? 

229
00:12:00,400 --> 00:12:03,160
So you look at everyone of these square, 
little square everywhere. 

230
00:12:03,160 --> 00:12:05,905
You know, there will be a decision 
variable associated with that and that 

231
00:12:05,905 --> 00:12:09,760
decision variable will be the number 
which is associated to that square. 

232
00:12:09,760 --> 00:12:11,430
Okay? 
The digit. 

233
00:12:11,430 --> 00:12:13,460
Okay? 
So essentially that's what you see there. 

234
00:12:13,460 --> 00:12:15,495
You know these are the decision variables 
over there. 

235
00:12:15,495 --> 00:12:19,779
Okay, they are basically [UNKNOWN] a 
matrix of, of, of variables, and these 

236
00:12:19,779 --> 00:12:23,790
variables take the value between one and 
nine. 

237
00:12:23,790 --> 00:12:26,050
Okay? 
Now, the constraints of these problems, 

238
00:12:26,050 --> 00:12:27,890
you will have different types of 
constraints. 

239
00:12:27,890 --> 00:12:29,730
The first set of constraints will be the 
fixed position. 

240
00:12:29,730 --> 00:12:31,558
Okay. 
So when you look at this thing, there are 

241
00:12:31,558 --> 00:12:33,540
a bunch of fixed positions all over the 
place. 

242
00:12:33,540 --> 00:12:36,790
We'll have to fix these values, these 
variables to these values. 

243
00:12:36,790 --> 00:12:39,890
And then once again, we have only three 
types of constraints, okay. 

244
00:12:39,890 --> 00:12:42,704
Well, actually one type of constraint but 
three different ways of stating that, 

245
00:12:42,704 --> 00:12:45,052
okay. 
So we have only alldifferent constraints, 

246
00:12:45,052 --> 00:12:47,446
but some of them are going to be on the 
rows, some of them are going to be down 

247
00:12:47,446 --> 00:12:51,310
the column and some of them are going to 
be on the squares, okay. 

248
00:12:51,310 --> 00:12:54,447
So when you look at the first one. 
Essentially that constraint, is basically 

249
00:12:54,447 --> 00:12:58,660
stating, that all the values on a 
particular row have to be different. 

250
00:12:58,660 --> 00:13:01,412
The second one is basically saying that 
all of the values in a column have to be 

251
00:13:01,412 --> 00:13:04,170
different. 
And the third one is basically, you know, 

252
00:13:04,170 --> 00:13:07,050
you look at the square, you know, three 
by three there, and you are expressing 

253
00:13:07,050 --> 00:13:10,110
that all these values have to be 
different. 

254
00:13:10,110 --> 00:13:13,410
These are the constraints of the Sudoku 
and that's all you have to do. 

255
00:13:13,410 --> 00:13:17,028
So this simple program. 
Is why is at least part of the reason why 

256
00:13:17,028 --> 00:13:20,790
I would never do a sudoku in my life, 
right? 

257
00:13:20,790 --> 00:13:23,680
You know it's so simple, right? 
So the next thing that I want to show you 

258
00:13:23,680 --> 00:13:26,990
is actually this is a very efficient way 
of actually solving this thing. 

259
00:13:26,990 --> 00:13:30,509
Okay, so look at this puzzle. 
Okay so the first time I run the program, 

260
00:13:30,509 --> 00:13:35,044
I traced it on this particular example. 
It deduced that, of course it, it fixed 

261
00:13:35,044 --> 00:13:40,630
all these position, and then it deduced 
that this value has to be 2, okay? 

262
00:13:40,630 --> 00:13:44,938
Now, that's very interesting, okay? 
So, I was like how did it do that? 

263
00:13:44,938 --> 00:13:46,466
Okay? 
And so you have to look at a couple of 

264
00:13:46,466 --> 00:13:49,834
things, okay? 
So, you see, you know, there is there is 

265
00:13:49,834 --> 00:13:51,930
a 2 over there. 
Right? 

266
00:13:51,930 --> 00:13:54,770
So, which basically means that I cannot 
put a 2 over here, okay? 

267
00:13:54,770 --> 00:13:57,711
There is no way I can do that. 
Okay, and then you have a two over here, 

268
00:13:57,711 --> 00:14:01,410
which basically means it can't have any 
two on this last line, okay? 

269
00:14:01,410 --> 00:14:05,505
So the tree position where I can actually 
put a two is here and these two gaps, 

270
00:14:05,505 --> 00:14:08,080
right? 
Okay? 

271
00:14:08,080 --> 00:14:11,400
So but look at, look at the, the square 
here in the middle. 

272
00:14:11,400 --> 00:14:14,938
Once again, I know that I have a two and 
therefore, I cannot put a value over 

273
00:14:14,938 --> 00:14:18,940
there, okay? 
Now I also know, what do I know? 

274
00:14:18,940 --> 00:14:21,850
Okay. 
So I know that I have a 2 over here. 

275
00:14:21,850 --> 00:14:24,240
So these guys here, cannot get a value of 
2. 

276
00:14:24,240 --> 00:14:27,050
So the only two positions where I can get 
a 2 here, is these two guys. 

277
00:14:27,050 --> 00:14:28,858
Okay. 
These 2 guys can take a two. 

278
00:14:28,858 --> 00:14:30,754
I don't know which one, right? 
Okay? 

279
00:14:30,754 --> 00:14:34,394
But at least one of them has to take a 2. 
Therefore what I know is this guy, cannot 

280
00:14:34,394 --> 00:14:36,260
have a 2 over here. 
Okay? 

281
00:14:36,260 --> 00:14:39,370
And therefore, the last position at which 
it's get a, get a 2 is over there. 

282
00:14:39,370 --> 00:14:41,790
That's what the system did. 
That's what this pruning for the all 

283
00:14:41,790 --> 00:14:45,600
different constraints were able to do. 
It's magical, right? 

284
00:14:45,600 --> 00:14:47,978
Okay, so if you do that, then it's 
going to know, going to continue deriving 

285
00:14:47,978 --> 00:14:51,372
all these values all over the place. 
That's what it gets, just propagating 

286
00:14:51,372 --> 00:14:54,820
these constraints, okay? 
And then, the system will make a choice. 

287
00:14:54,820 --> 00:14:57,035
It will assign the value 5 at the top 
over there. 

288
00:14:57,035 --> 00:14:58,480
Choop! 
Here. 

289
00:14:58,480 --> 00:15:01,472
And that it will make more deduction than 
when you assign one more value over here, 

290
00:15:01,472 --> 00:15:04,480
okay? 
So there's a value of 4. 

291
00:15:04,480 --> 00:15:06,910
And then propagate and find a solution, 
and that's it. 

292
00:15:06,910 --> 00:15:10,020
Two choice, no back-track, solution 
immediately. 

293
00:15:10,020 --> 00:15:11,950
Okay. 
Now you have to know that sudokus are 

294
00:15:11,950 --> 00:15:14,792
easy for us, and the reason is that they 
have to be easy for human, which 

295
00:15:14,792 --> 00:15:17,830
basically means that human don't like to 
make choices, so these sudoku are 

296
00:15:17,830 --> 00:15:21,015
actually designed so that you can mostly 
deduce the solution and don't go into 

297
00:15:21,015 --> 00:15:25,788
exploring a huge tree. 
That's why these things are really easy 

298
00:15:25,788 --> 00:15:29,248
for constraint programming in general. 
Okay, so, so we have seen now essentially 

299
00:15:29,248 --> 00:15:32,576
global constraints and global constraints 
are these very important area of 

300
00:15:32,576 --> 00:15:35,838
constraint programming. 
There are a lot of people actually 

301
00:15:35,838 --> 00:15:38,000
exploring this. 
Okay? 

302
00:15:38,000 --> 00:15:40,790
And, I want, I want to show you one more 
type of constraint which is the table 

303
00:15:40,790 --> 00:15:43,766
constraint. 
And it's probably the simplest global 

304
00:15:43,766 --> 00:15:46,298
constraint, okay? 
And so this is an example for you to 

305
00:15:46,298 --> 00:15:48,390
understand. 
I have three variables okay? 

306
00:15:48,390 --> 00:15:51,464
x, y, and z, okay? 
This is the domain of the variable 1, 2 

307
00:15:51,464 --> 00:15:55,100
1, 2, and then 3 ,4 ,5 for, for z. 
Okay? 

308
00:15:55,100 --> 00:15:58,285
And then essentially one of the things we 
can think of is, you know, what are the 

309
00:15:58,285 --> 00:16:01,670
possible combination of all these 
variables, okay? 

310
00:16:01,670 --> 00:16:04,871
What are the total possibilities? 
And essentially there are 12 of them, 

311
00:16:04,871 --> 00:16:07,076
okay? 
So you could see each product between, 

312
00:16:07,076 --> 00:16:11,200
you know, the domain of x, the domain of 
y, and the domain of z, okay? 

313
00:16:11,200 --> 00:16:14,034
So that's what we have, okay? 
So in this particular case there are 12 

314
00:16:14,034 --> 00:16:17,330
possibilities. 
So what a table constraints is doing, is 

315
00:16:17,330 --> 00:16:20,990
actually specify a subset of these 
possibilities as the legal, you know, 

316
00:16:20,990 --> 00:16:25,328
assignment of these variables. 
So, in this particular case, we have four 

317
00:16:25,328 --> 00:16:28,860
of them, okay. 
So you see that the first one is 1, 1, 5. 

318
00:16:28,860 --> 00:16:32,390
X is equal to 1, Y is equal to 1, and Z 
is equal to 5. 

319
00:16:32,390 --> 00:16:35,220
The second one is 1, 2, 4. 
That's what you see here, okay. 

320
00:16:35,220 --> 00:16:38,811
And so in this particular case, the legal 
combination is 1 for x, 2 for y, and 4 

321
00:16:38,811 --> 00:16:41,420
for z. 
Okay. 

322
00:16:41,420 --> 00:16:44,318
And so once again what is interesting to 
see is what happens when you get more 

323
00:16:44,318 --> 00:16:45,990
information. 
Okay. 

324
00:16:45,990 --> 00:16:48,760
So assume that I have more information 
about z. 

325
00:16:48,760 --> 00:16:52,230
What's going to happen? 
Well, I know that z cannot be equal to 5. 

326
00:16:52,230 --> 00:16:54,831
What does that mean? 
Okay, so the value z there is not legal 

327
00:16:54,831 --> 00:16:58,240
anymore. 
I have to remove that combination. 

328
00:16:58,240 --> 00:17:01,490
I have to remove all the combinations 
where I have actually z is equal to 5. 

329
00:17:01,490 --> 00:17:05,083
There is only one here, okay? 
And now, essentially, I look at the, I 

330
00:17:05,083 --> 00:17:08,040
look at the other variables, and what do 
I see? 

331
00:17:08,040 --> 00:17:10,992
Look at this guy, look at y. 
The only value which is left in the 

332
00:17:10,992 --> 00:17:15,202
column of y is 2. 
So I can immediately deduce that, in a 

333
00:17:15,202 --> 00:17:19,810
sense, y has to be 2 and the value, you 
know, and this is what this reflect here, 

334
00:17:19,810 --> 00:17:23,912
okay? 
So, so, in a sense, y has to be different 

335
00:17:23,912 --> 00:17:27,374
from y, it can only be 2, okay? 
So that's essentially the table 

336
00:17:27,374 --> 00:17:29,470
constraints. 
Once again, it's a very useful 

337
00:17:29,470 --> 00:17:32,338
constraint. 
It always specify a subset of a cartesian 

338
00:17:32,338 --> 00:17:34,930
product. 
For all the variables. 

339
00:17:34,930 --> 00:17:37,216
Okay? 
So let me conclude this lecture by one 

340
00:17:37,216 --> 00:17:40,679
more thing, okay? 
which is how can we find optimal solution 

341
00:17:40,679 --> 00:17:44,806
in using a constraint programming? 
So remember we discuss graph coloring or 

342
00:17:44,806 --> 00:17:48,140
map coloring actually In the first two 
lectures, okay? 

343
00:17:48,140 --> 00:17:51,276
And so what, what I'm doing here is 
generalizing a little bit of that 

344
00:17:51,276 --> 00:17:54,345
example, okay? 
And instead of using colors, I'm using a 

345
00:17:54,345 --> 00:17:57,045
number from 1 to 4, and what I'm going to 
do now is not only color this country 

346
00:17:57,045 --> 00:17:59,970
such that they get a different color, in 
particular, in this particular case a 

347
00:17:59,970 --> 00:18:04,390
number between 1 and 4. 
But I also want to minimize the number of 

348
00:18:04,390 --> 00:18:06,150
colors that I'm using. 
Okay? 

349
00:18:06,150 --> 00:18:10,026
So basically here, I'm basically saying, 
okay, minimize, okay, what the maximum 

350
00:18:10,026 --> 00:18:13,959
color that this variables can subject to 
the fact that two adjacent countries have 

351
00:18:13,959 --> 00:18:18,370
to be colored differently, okay? 
So, I can do that. 

352
00:18:18,370 --> 00:18:21,096
Okay, so that's a model which is 
essentially optimizing the number of 

353
00:18:21,096 --> 00:18:25,505
colors that I have to use. 
In all the possit-. 

354
00:18:25,505 --> 00:18:30,061
Selecting essentially the solution, the 
feasible solution, which uses the, the 

355
00:18:30,061 --> 00:18:33,450
fewest colors, okay? 
How do I do that? 

356
00:18:33,450 --> 00:18:36,600
In constraint programming, as I told you, 
the focus is on feasibility. 

357
00:18:36,600 --> 00:18:39,300
And what you do when you're trying to 
optimize is you're trying to reduce 

358
00:18:39,300 --> 00:18:43,680
optimization problem to feasibility. 
You essentially solve a sequence of 

359
00:18:43,680 --> 00:18:46,484
feasibility problems. 
You find a solution and then you put an 

360
00:18:46,484 --> 00:18:49,432
additional constraint which says, oh, but 
the next solution is to be better than 

361
00:18:49,432 --> 00:18:53,109
the one that I just found. 
Okay so when we find a solution with four 

362
00:18:53,109 --> 00:18:55,818
color we are going to say I want to find 
a solution which you're only using three 

363
00:18:55,818 --> 00:18:58,885
colors. 
Okay, so we are guaranteed to find an 

364
00:18:58,885 --> 00:19:01,900
optimal solution. 
You know, theoretically. 

365
00:19:01,900 --> 00:19:04,756
You know, in practice it may take too 
long, okay and this is going to be a 

366
00:19:04,756 --> 00:19:08,020
strong method when essentially the 
constraints are too hard, that you add as 

367
00:19:08,020 --> 00:19:11,437
essentially a strong pruning, okay, and 
this happens in a variety of problems in 

368
00:19:11,437 --> 00:19:14,752
results, allocation and scheduling, and 
we'll come to these problems at some 

369
00:19:14,752 --> 00:19:19,420
point in this class. 
Okay. 

370
00:19:19,420 --> 00:19:21,250
Thank you. 
That's it for today.