But this works rather nicely.

And now the idea is, since we know that acyclic constraint graphs can be solved rather efficiently,

the goal is to find a cut set, which means a subset of our variable set, such that if

we get rid of that set, the resulting network will be acyclic.

This is what happens in this case if I just get rid of South Australia here.

Once I do that, the remaining network is acyclic.

So the idea is, if we can find such a cut set, and of course, ideally we want to find

a minimal cut set, then we do our usual backtracking algorithm with forward checking, starting

with the variables in our cut set.

And once we have assigned values to all of the variables in our cut set, we can go over

to the algorithm for acyclic graphs and do the remainder of the graph using that algorithm.

That also gives us a huge speed up.

This is the resulting algorithm.

You note that this is basically just the backtracking algorithm with forward checking here.

And then once we have assigned all variables in our cut set v0, we just go over to the

acyclic algorithm two slides prior.