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.

Â