Welcome back. So I'm quite happy that today we're going to start talking about my favorite

subject and the one where I actually know what I'm talking about, i.e. formal logic.

But before we come to that, let's briefly recap what we talked about yesterday. We're

on the topic of constraint satisfaction problems and we started with the naive approach of

basically just trying to solve them doing a tree search and then we considered various

ways of improving that. The most important ones being either doing inference, which means

during our search procedure we replace our current constraint network by an equivalent

constraint network that has the same solutions but has stronger constraints, thus ruling

out partial assignments early and pruning branches in our search tree. The second one

being decomposing our constraint network into several smaller networks that we can then

solve independently and then compose the solutions for the smaller networks to one global solution

for the whole network. The easiest way of doing inference is by just doing forward checking

which basically just means if we assign a value to some variable we rule out all values

for the other variables that break the constraints between them and R consistency is the concept

that we're going to use to improve forward checking immensely. So the notion of R consistency

subsumes forward checking and is based on the notion that we say a variable in our constraint

network is R consistent relative to some other variable if for every value in the first variable

there is guaranteed to be at least one value in the domain of the other variable such that

the two don't break any of the constraints. Violate, that's the word I was looking for,

that don't violate any of our constraints. Naturally we call the whole network R consistent

if every variable is R consistent with respect to every other variable and clearly that's

a consistent way to do things in the sense of it really does yield an equivalent network

and nicely it subsumes forward checking as well. So the only question is how do we go

about doing that? Here's the basic revised algorithm that makes two variables, that makes

one variable R consistent with respect to some other variable. We literally just check

is it already R consistent? If no, if there's some value that makes it not being R consistent

we just throw out that value of our domain. Now of course we can think about, here's just

one example of how this works. We have the small network with three nodes. We want to

make V3 R consistent with respect to V2 given this constraint between V2 and V3 so we just

check for every one of those values if there is one value over there that violates the

constraint for the value 1 in V3 that does violate R consistency so we get rid of 1.

For 2 that as well breaks R consistency so we get rid of 2 as well and now V3 is R consistent

relative to V2. So the most naive way of implementing things this is to basically just write a function

AC1 that enforces R consistency from every variable with respect to every other variable

and do that basically in each recursion step of our backtracking algorithm. We can do that,

it's not exactly efficient but it's basically the first naive way we would go about doing

this. The problem here is that it leads to a lot of redundant computations because basically

every time we change any variable we have to reconsider every pair of variables and

make sure that they are still R consistent. That's kind of a pointless overhead so we

have this new algorithm AC3 that tries to be smarter about this. What AC3 does is basically

just keeps track of all the pairs of variables we already have considered for R consistency

and then we are smart about which pairs of variables we reconsider every time we delete

values in one of our domains. This is what happens here, we have this set M that starts

with being the full set of all pairs of variables and then every time we change any domain during

the call to revise we only consider those pairs of variables where the second variable

is the one where we just changed the domain. This also enforces R consistency. Here is

one example, we again have this network of three nodes, this time we use the constraint

that the value of V1 has to divide the value of V2 and the value of V1 also has to divide

the value of V3. Here is our stack of pairs of variables and now we basically just enforce

R consistency from V1 to V3, from V3 to V1, from V1 to V2, from V2 to V1. So we go about