The following content has been provided by the University of Erlangen-Nürnberg.

We graduated from straight-on search procedures,

which have the main characteristic that the states are atomic and black box,

meaning we cannot look into them.

We graduated from that to algorithms where we use a factored state representation.

And the state representation is essentially, we have a couple of slots,

and the values are from some kind of, usually in our case, discrete domains.

Anything you can do by filling out fixed forms intuitively.

And this allows us to guide the search as we'll see, much better.

There will still be search in AI, there's no real way of getting around search,

but we'll have search algorithms that take advantage of the fact that we can look into the states.

So, our main example, or one of the main examples, was scheduling problems,

like this one where we have features like when, where, who, I don't know, those kind of things.

And that led us to the idea of having a constraint satisfaction problem,

which is really, we're giving ourselves a set of slot names, which we will call variables,

and all of them range over their own domains.

Just like, imagine if you will, a form with drop-down menus,

where we have a finite number of values that are acceptable,

and the values might really be different per slot. That's the idea.

Another example is Sudoku, where the variables are essentially the cell names,

and the domains all are the same, having digits from 1 to 9,

and we have a couple of constraints that say what we can actually fill in, or not fill in,

and here it's, you can't have duplications on any diagonal rows or columns or blocks.

The constraints is usually what makes the whole thing fun, and difficult.

Okay, the example we'll use most because it's so simple is map colouring in Australia.

Again, we have a couple of variables, each one of these seven or so territories,

and the values are the colours, and the constraints are no co-colouring if there's a common border.

That's longer than a point.

Again, we looked at all of this, one of the things that can be, scheduling can be expressed like that.

So, we kind of quickly convinced ourselves that if you do things naively, then you're in trouble.

Quite generally, for many of these things, we have extremely powerful constraint solvers,

and you may remember that I told you about this, sorry about the prologue and the Singapore harbour.

The main thing there was that you use something called constraint logic programming,

which is essentially programming, where instead of trying to make things equal,

remember when we did programming with our finger on the blackboard, we always try to make things equal.

What you do in constraint logic programming is that instead of trying to make things equal,

which is a constraint of course, you allow other constraints as well.

What you do is you just basically, whenever there is a constraint that comes up,

you feed it to the constraint logic, to the constraint solver, and the constraint solver basically says yes or no,

saying essentially there are solutions other than there are no solutions.

If there are solutions, you can actually do the prologue step, and if there are no solutions, you fail.

It's kind of a generalisation of these equality constraints.

Can I make those things the same by substitution to much, much richer and much more interesting domains?

The thing in this logic programme that solved the problem for Singapore harbour was essentially to cleverly

put some of the problem into a high-level description of the world, of Singapore harbour,

and part of the problem into constraints.

You can imagine that we have all kinds of constraints that if there is a ship in a position,

there cannot be another ship there that's different from this one, and if something is moving out,

you have to have enough places free and those kind of things.

Those are things that can be very well expressed in constraints, and that led to the efficient solution,