So the kind of simplest thing you can do is what we call forward checking. So same signature,

you get a description and a partial assignment and you essentially propagate known values

forward. So let me make an example first. Say in the first step we choose Western Australia

to be red. And now we actually look across all of our constraints from the variable we

have just chosen and knock out in this case everything that is inconsistent with the constraint.

So what we know here, Western Australia is red, these two cannot be red. This is Northern

Territory cannot be red, knock it out here. Southern Australia cannot be red, knock it

out here. Tightening the constraint. And what we can do once, we can do twice. So say, let

us say we choose this to be green. Queensland is green, that actually has three neighbours.

So we knock out green for Northern Territory, that's here. We knock out green for Southern

Australia and we knock out green for New South Wales. Okay? Well, whatever we can do twice,

we can do three times. Okay? We choose blue for Victoria, so we knock out all the neighbours,

we've knocked out completely everything for Southern Australia. It looks very, very similar

to what we've been doing, but this is inference. We've not actually made any choices yet. We

haven't changed the partial assignment. We've just taken our choice, or our three choices

here, and made the best possible out of them, tightening up. And we've seen early that this

is inconsistent and we could do nothing anymore. Three choices and we're actually changing

the constraint network. So don't be blinded by all these colours here. These are just

graphical representations of the changed problems. Read this as the domain of Western Australia

is red, the domain of Northern Territory is green or blue, the domain of Queensland is

red, green or blue and so on. And so we're getting more out of every choice than we're

putting into it. That's forward checking. That easy? Helps a lot. The good thing about

this is if we could afford the cost, because inference has a cost, in this case relatively

little cost, then we get much, much more constrained, much tighter networks that give us much better

utilisation of these heuristics. That's the thing you have to realise here. By doing inference,

the heuristics become much, much better. All three of our heuristics actually get more

constraints. If you think about minimum remaining value, that is going to be a much better heuristic

the more constraints you have. The degree heuristic counts constraints, gives you bigger

numbers, more differentiation if you have more constraints, which means a tighter thing.

And even the value heuristics by least constrained value becomes more meaningful, because if

you've done inference, you're much nearer to what is actually going to be the case and

what actually your choice is. Inference pays twice. It finds failure early and it makes

the heuristics better. The heuristics are the main deciding factor here. That's why

inference pays. Good. Now, forward checking. Just showing you a procedure, waved my hands

vigorously and told you this is a good thing to do. The question you want to ask yourselves

is is it really the case that this tightens up without losing equivalence? And in this

little thing here, it's relatively easy to see. Having one example where it works is

not enough of course. What you really want to do is you want to sit down and prove that

it's as we say sound. We're not losing any solutions. Why? Essentially because we're

just propagating values across constraints and then marking those by tightening the domains.

We're just computing. That's here the important one. Computing the domains that by tightening

the domains by the stuff that wouldn't be possible anyway. So we're not losing anything.

We're losing things that are illegal. We're losing those early. In practice, forward checking

is as you've seen relatively cheap. You always want to use it is the short story. The only

reason not to use it is if you have something better. It's kind of the baseline for any

kind of inference procedure. If it doesn't do forward checking, then you're doing something

completely wrong in practice.