0:21

This left part of his calculation unknown.

Zhang Fei knew how many once were involved in the calculation, yet

he had no idea how to recover his work.

This calculation was important for future reference,

so this confused Zhang Fei told Liu Bei about the accident.

0:38

Liu Bei then took out his magical tablet to see if

it could help them to recover the calculation.

>> [SOUND] So, Zhang Fei is in charge of accounting for

the army, and he's sitting there doing his accounting

when a cat jumps in and messes up the figures.

Now the point is, he's doing accounting using a system of counting rods.

And after he sees the cat and bounces around,

he can see that 12 rods have been knocked off the table and not in their position.

And he remembers that all of the digits in these positions were different.

So basically he has to solve a problem of working out what

were the digits that have gone missing that the cat has mixed up?

So, just a briefly word about counting rod representation.

So this is a way of representing digits using up to 5 counting rods.

And there's two different ways, vertical and horizontal.

And in fact that's a very neat trick where you can keep vertical and

horizontal alternating so you can leave out digits while doing that.

Although we won't use that in this example here.

1:45

So he's got,

here is the representation of what those counting rod digits actually meant.

So he was in Arabic numerals, basically, the arithmetic that's going on here.

And of course this arithmetic should hold, so that's another part of the problem.

2:00

So let's look at building a model for that problem.

So what do we have?

We have a set of digits from 1 to 9,

and then we've got this array of how many rods it takes to represent each digit.

So the digit 1 is only 1, and 2 and 3 and 4 and

5 for representing the digits 1 to 5.

But then you need 2 digits to represent 6 and 3 for 7, 4 for 8, and 5 for 9.

You can look back, if you look here and number representations for

6 is 2, and 3 and 4 and 5.

2:32

Okay, so

that's basically telling us how many rods we require to represent each digit.

And then we have five different things we need to know,

basically each of the five messed up digits.

So if you look back at the example here we have one, two, three, four, five,

messed up digit positions.

2:51

And then we got our constraint.

Well we know the number rods in the digits that are messed up sum up to 12.

Okay, and then we're trying to make sure that the constraint holds.

So if we take the first number, it would be 2,303 * M1 * 10, because M1,

that's the missing digit here, if it's in the ten digits position.

So that's going to give us the value of the first expression.

And we take the second expression,

which is 980 + M2 * 1000 + M3 because here's M2.

That's in the thousands position and M3 is in the ones position.

3:30

So that'll give us the sum of the top two numbers and

then we have to add up to get the right value underneath.

Which are 301, which are the digits are given,

times M4 * 1,000 because the M4 is in the thousands position.

And M5 * 10 because it's in the tens position.

But one thing we should note here is we are looking up

using a decision variable into an array, all right?

So this is a very powerful modeling ability of things like MiniZinc.

We can use a variable here, we're going to look up using the digits here which is

the decision, how many rods it takes for that decision.

4:07

Now, we got to continue,

we know that each of the five missing digits are all different.

We could write down all of these not equal constraints to make sure that all

five of those digits are different.

So that tedious, it's long.

It's also prone to error.

You can leave off one.

So let's do it a different way.

The way we're going to do this is by introducing and aldifferent constraint.

So this is an example of a global constraint,

which is what we're going to talk about a lot in this course.

So here's the aldifferent constraint saying, everything in this list of digits,

M1 to M5 has to be different.

So it's just a shorthand way of writing down all of this information in one go.

4:55

And then here's our global constraint, the use of the alldifferent.

And since the problem is just to find a solution,

we're just running solve satisfy to find what is the solution for these variables?

There's nothing to optimize here.

So we've seen a few new things in this model.

So we had a set of type, so here, rather than use a numerator type,

we used the digits from one to nine.

So here was our, we gave a name to that.

We called digit this name from one to nine, right?

So this can be used in place of any fixed set.

So that's often what we'll do.

Also is build ranges and give them names and

use those just like we used enumerated types.

We also variable lookups.

As I said here, we can use decision variables as part of an index expression.

And this is going to give us a very powerful modeling capability,

which isn't in many other modeling languages.

So here we're using it very, very simply.

Basically for each missing digit, we're using this array lookup to look up

how many rods it took to represent that digit.

We'll see many more examples of this later on.

5:58

So we also saw an include statement here.

So include just has include and then a file-name.

That's all you need for the include statement.

And basically, it takes the contents of this file and

just imports them directly into your MiniZinc model.

And it'll look in the current directory.

So you can use it to break a model into parts.

Or it'll look in the MiniZinc library path, whose what we're doing here.

Is looking up, finding the definition of all different, and

including it in our model.

So include statements allow us to break larger models into small pieces.

Although we won't do so much of that during this course.

But when you're building large real world models is very useful.

It allows you to load library definitions of global constraints and

that's what we're doing here.

We're loading a library definition of the order for constraint into our model.

And the nice thing about this is this global constraint definition we

load will be different depending on which solver you choose to use.

This is one of the key things that global constraints allow us to do,

is allows us to give a version of the constraint which is specialized for

the particular solver we're going to use for running the model.

So even though we write the model with one or

different solvers may see a different way of representing that all different.

Okay, and global constraints.

So technically a global constraints is any constraint which is

unbounded number of variables as input, and so we've already seen a linear

constraint like some expressions are kind of global constraints.

But here, global constraints typically will be a name of the special constraint

and then some arguments,

usually with arrays because they they attain unbounded numbers of variables.

So global constraints are used to store constraints that arise in many problems.

And using the global constraints makes the model smaller.

You can see here once were used alldifferent

we’ve made a much smaller model.

And it does more than that, it makes solving easier.

7:48

So typically, here we pass the alldifferent constraint to the solver,

the solver will know especially how to solve that constraint.

So basically we are recognizing some structure of the problem, which occurs

commonly in many problems, and passing that information to the solver, and

then that solver can use that information to solve the problem more effectively.

8:09

So if we run our model we're going to get an answer here.

So here you can see you can see each of the digits is different and if we count

the number of rods in these blue missing digits, you'll see they add up to 12.

So we've got our solution to our problem.

8:23

So in summary, we've introduced global constraints.

That's one of the most powerful concepts we'll see in this course.

It's a way of recognizing and

naming common tutorial substructure which occurs frequently in many problems and

dealing that information to then to the solver to be able to allow it

to do the best job it can on that particular common tutorial substructure.

8:42

Another powerful modeling approach we've seen here is the ability to use a decision

variable as an index into an array expression.

And this will allow us to build very very complex constraints while building up

arrays and using decisions to look into those arrays to find the appropriate

path that we need for the model.

So here we're just using a very simple example, but

we'll see much more complicated uses of this later on.