Now you can hear me?

Yeah.

It would be very fair to give this thing a chance of working by turning it on.

Good.

Okay.

So now that we've solved this problem, let me remind you what we were doing.

Right?

We had started with constraint satisfaction, and we gave a very general search-based algorithm

where we used the fact that in our factored representation of states, we have variables

with domains, and that basically tells us that solutions are just variable assignments.

You give every variable a value, and you do it in a way that you're not violating any

constraints.

Good.

So that gives us a first algorithm for solving the problem, namely backtracking search.

The good thing is we can just do depth first because the search depth is finite.

Right?

We have finitely many variables, and if we in every step choose a value for one variable,

we're done after n steps.

The search steps is depth n, when n is our number of variables.

But even for Sudoku, we have 81 and a nine ways branching trees of depth 81, we're not

going to be able to search.

So we have to do something clever.

Okay?

What did we do clever?

We had clever heuristics.

And with that, Sudoku is no problem anymore.

A thousand queens is not a problem anymore.

Okay?

So much, much, much, much better than the unfactored black box states we had before.

Okay?

But we can do even better.

The speed up we see with CSPs is largely due to the fact that if you look at the actions,

they go from groups of atomic states to groups of atomic states.

So we're doing macro operations.

Okay?

That's why it's so much better.

And we have structures for good heuristics.

Now, if we want to not only do groups to groups action, but even groups of actions, then we

have to completely do something completely different.

And that is inference.

Inference basically says we're not actually doing group of states to group of states search.

We're doing computation on the space of all descriptions, of CSP descriptions.

Completely different animal.

And it just turns out that this works extremely well for CSPs.

Okay?

So the idea is that we have a procedure like magic that massages our CSP descriptions into

a form that is easier to solve.

And it just so happens that this is very effective.

And now, in the worst case, inference, even though it's on the average very effective,

does nothing.