What you can do for a simple case as in line drawing, you can do for other cases as well.

So what you typically have, we're going to only look at discrete variables even though

as always continuous variables are possibly more interesting.

But you can get quite far with discrete variables.

If they have finite domains, then you'll end up in your typical NP complete problem.

Essentially what you can do is you can kind of make the states black box again by essentially

restricting yourself to forms that have one slot with essentially one value to fill out.

That gives you essentially states you can't really look into.

So we degenerate to the stuff we already know.

So you essentially have something which is you could do by search, but you can do better.

Then you can generalize and as always it becomes worse from the complexity point of view.

But still constraint like techniques really help you there.

If you have number constraints for integers or strings or those kind of things, these

techniques are extremely helpful even though in the worst case, especially if you have

nonlinear constraints, you run into very bad worst case complexities including undecidability

quite often.

And you don't even want to think about the continuous case.

Again in the typical engineering case things work well.

If you do the complexity, all bets are off.

So if you look at the constraints, the constraints are the most interesting part.

We have unary constraints, which are things like southern Australia shouldn't be green.

You have binary constraints like southern Australia and western Australia shouldn't

actually have the same value because they share a border.

And then you have higher order constraints.

And then you can relax constraints because very often constraint problems don't have

a solution.

Almost all scheduling problems don't have a solution.

And you can find solutions by basically making the constraints soft, attaching a cost for

violating one of them, and then you can actually find the cheapest, less costly version of

those kind of things.

We're not going to go into this.

We're going to kind of encode away the higher order constraints even though that's going

to be bad.

And so we're going to be left with unary and binary constraints.

Only of these binary constraints are the only ones that really matter because unary constraints

you can do by changing the domain, restricting the domain of a variable.

So if you had three colors as a domain and if you have the constraint that southern Australia

shouldn't be green, you just make the domain from three colors to two colors.

So we'll concentrate on binary constraints.

But I would like to show you at least, we looked at a non-binary constraint.

We have this addition constraint is of order eight.

But what you can always do if you have an unary constraint, you can code it down by

encoding more constraints on the variables via this little idea.

So what you do is you just basically introduce something like function symbols and make more

and more and more constraints.

This is really terrible because this gets exponentially big in the worst case.

And also you lose structure.

So all the systems can natively deal with arbitrary order constraints.

We're not going to do that.

We're going to only do the theory with binary constraints.