0:20

There are holes in the belt for

Â placing gems in certain positions that would trigger the container to unlock.

Â These positions were determined by satisfying particular separation distances

Â between each type of gem.

Â For example, two consecutive blue gems needed to be one hole apart, and

Â two consecutive red gems needed to be two holes apart.

Â 0:41

Emperor Xian gave Liu Bei a belt that had eight holes with eight gems.

Â Noticing Liu Bei had received this gift, Cao Cao questioned him about it, but

Â failed to uncover anything unusual about the belt.

Â Later, in order to retrieve the emperor's secret message, Liu Bei took

Â out his magical tablet to ask for help for putting the gems in the desired pattern.

Â 1:23

So he has this belt and these precious gems, and he needs to

Â place them in the belt in a position that satisfies this set of constraints.

Â So the two gems, the blue gems have to be one apart,

Â and the red gems have to be two apart, and

Â the green gems three apart, and the last set of gems four apart.

Â So this is an example, this is our belt problem.

Â 1:56

And we need to find the sequence of these numbers

Â where there are k digits between every two consecutive copies of digit k.

Â So the example here we're looking at is, we've got two copies, so

Â this is B, two, three.

Â We've got two copies of each of the numbers 1 to 3, and so

Â there's a solution for B(2,3).

Â So the example that Liu Bei is looking at is B(2,4).

Â So he's got two copies, two gems of each of the colors from one to four.

Â 2:30

So how is this an assignment problem, for a start?

Â Well, we just have to think what we're trying to do here.

Â Our domain is the ordered copies of the digits.

Â We have 2 copies of the digit 1, 2 copies of the digit 2,

Â 2 copies of the digit 3, and 2 copies of the digit 4.

Â And the codomain is this position in the sequence of where do we put them in this

Â magic belt?

Â So again, it's an assignment problem, and indeed, it's a bijection.

Â 2:57

So we can build a MiniZinc model to do this.

Â So let's think about our data and decision.

Â So we have our n, different digits, and we our m copies, and

Â then l is the total number of digit copies that we have to brooch,

Â which is m times l, that's the number of positions that we're going to have to do.

Â And then we've got this array, so for each digit, for each copy of the digit,

Â which position does it go into, and there's basically just two constraints.

Â So for every digit, and for every copy except for the last one,

Â we need that the next copy has to take the position of the previous copy and

Â add d + 1 positions to get the next position, right?

Â because we need d intervening digits

Â before we get to the next copy of this digit.

Â So that basically means that if there's two digits one,

Â there's one person is the middle before get to the next copy of digit one.

Â And for a two digits two,

Â there's two people in the middle before we get to the next copy of digit two.

Â 4:05

And the other thing, of course, is that all these positions are different,

Â we only have one digit going into each position.

Â So that's all the constraints we need to write down this problem.

Â 4:23

So on the inverse viewpoint, the dom is the positions in the belt, and

Â the codomain is the digit copies.

Â So in order to model this in MiniZinc, we're going to have to map these digit and

Â copies to a single integer.

Â So we think about this digit copy kind of viewpoint as an integer, which is m,

Â number of copies, times d times run the digit, plus the copy.

Â So that'll map this digit copy things into the numbers one to eight.

Â And we'll think of digit copy these numbers from 1 to l,

Â obviously equal to the number of positions.

Â And then the decisions we're going to make are for

Â each position, what digit copy goes in that position.

Â 4:59

Now, the inverse alldifferent constraint is easy, of course.

Â Basically we're saying the digit copy that in each position,

Â there's a different digit copy.

Â 5:07

So that's straightforward.

Â Now, the hard part is the separation constraint.

Â So we think about how the separation constraint is done in the primal model,

Â the normal belt model.

Â We basically said that position of a digit copy, then we

Â added d to it plus 1, and that gave us the position of the next copy of that digit.

Â 5:28

Now we have to just think okay, well,

Â we know that if the position of this copy of this digit is p,

Â then that's the same as saying the digit copy in position p is equal to dc.

Â 5:40

So we can rewrite this constraint in terms of these variables by writing it this way.

Â Basically for every digit and for every copy, and

Â for every position, if the digit copy, p is equal to this one,

Â which is the same as writing this dc down, right?

Â Remember this is just our way of encoding dc.

Â Then that forces that the digit copy at p + d + 1,

Â so this is this position, remember.

Â So this is the digit copy for this guy, must be this digit,

Â which is this digit's copy, right, the same digit with the copy plus 1.

Â 6:23

So it's just writing down this constraint in terms of these digit copy variables.

Â Okay, but basically just saying, if position p has this digit copy,

Â then position p + d + 1 has this digit copy.

Â So it's a rather terrible encoding.

Â All right, you can see it's very, very large.

Â This one's quite compact, uses one single equation,

Â and this has got two equations joined by an if.

Â So we have to think about this a little bit carefully.

Â Notice that we can access positions outside the actual dc array.

Â So if we take l to be the position, right,

Â p to be l, and then we added d + 1 to it.

Â So we can take this to be, l plus d plus 1,

Â it would be accessing outside that array's bounds.

Â What's going to happen?

Â Well, this will actually be correct.

Â Why?

Â 7:29

We know that the last copy of a digit.

Â Only the last copy of a digit can occur in the last d positions of the sequence,

Â because if the last copy didn't occur, if it was not the last copy,

Â then the last copy would have to occur even later.

Â So if we tried to put anything but the last copy in the last d positions of

Â the sequence, then we'd be forcing the next copy of that digit to be even later.

Â So what happens here is this,

Â if we try to take a later version, the constraint will fail.

Â The relationships semantics would say once this goes out of scope, this will make

Â this whole constraint false, which will make this constraint false.

Â And what will that do?

Â That'll say that the position of that digit copy,

Â the non-last position can't be in this last part of the sequence.

Â So in fact, the relational semantics here will force that you can't put a non-last

Â copy of a digit in this last part of this sequence, which is exactly what we want.

Â 8:32

So here we're actually using the relation semantics to our advantage,

Â actually making this array out of bounds is doing exactly what we want.

Â In fact, it's causing this constraint to become false which is causing

Â this constraint to be forced to be false, which is exactly what we want.

Â Now, we can avoid it in this case.

Â Right, it's always safer to avoid this array

Â out of access problems by putting this test in here.

Â If this thing would be out of access, so we can just check, if it would be

Â outside of the domain of this array, then we can just say it's false,

Â right, and that would have exactly the same effect.

Â And in this case, we'd never get any out of array accesses.

Â But we'll have exactly the same effect because that's

Â exactly what the relational semantics is going to do.

Â So in this case, we can avoid this out of array behaviour,

Â but all we'd be doing is replacing one expression,

Â which the relational semantics would make equivalent as this expression, and so

Â there's no great benefit in this particular case.

Â But we have to be careful, and we have to think about these things,

Â when we're building these models where we make indexes which

Â go outside the array index that we want.

Â So let's look at the inverse belt model in total.

Â For each position, we're going to pick which digit copy we're going to do.

Â We have our complicated constraint, which maps the fact that two digit copies

Â are the right distance apart, they have the right number of intervening digits.

Â We have alldifferent constraint just as before, and

Â we're solving a satisfaction problem, so we have two distinct models.

Â 10:14

We've got our belt model, the original model where we have for

Â each digit copy which position it's in, and our inverse belt model,

Â which is saying for each position, what's the digit copy, which is in that position.

Â 10:28

So which runs faster?

Â Well, in this case, we can use this succinctness argument,

Â to say that we couldn't really write this constraint about the distance between

Â the digital copies very well in the inverse model.

Â And the rest all being the same, actually the original belt model is going

Â to run faster, so it's likely to be the best in this case.

Â Now which one is easier to print out the belt sequencing?

Â Remember what we finally want to do is actually to put the gems in the belt.

Â In fact, it's the inverse model,

Â which is going to give us the right way to print out the belt sequence, right?

Â That's going to give us, for

Â each position which is the digit copy that goes in that position.

Â So there's a minor benefit to the inverse belt for this particular problem.

Â And there we are, there's a solution for loop a.

Â So the combined model, of course, we can combine them.

Â We can omit the alldifferent constraint, because that's kind of be again implied by

Â these inverse channeling constraint, which joins the two models together.

Â So once we put those two models together with the inverse constraint,

Â then that's going to make sure that the alldifferent constraint holds.

Â And again, the CP model can solve the combined model better in this case,

Â because it can search both on these position variables and

Â these digit copy variables.

Â So the combined model, even though it won't actually have any constraints

Â more than what's in the belt model, will actually solve better than the belt model.

Â 12:04

So that shows you another example about why combined models can be more efficient.

Â It turns out it can be more efficient to search on the digit copy variables,

Â rather than the belt models, even though the digit copy variables aren't

Â very useful for stating the problem.

Â So here's our combined model.

Â We have both the position variables and the digit copy variables.

Â The constraint about the positions of the two digit copies is used in the belt

Â model, because that's the easier way to do it.

Â We have our inverse constraint that maps the two functions to be inverses, and

Â that will force the alldifferent constraint.

Â We have solve satisfy and the output, of course, using the digit copy variables,

Â because that gives us the output in the way we want it.

Â And this model will actually solve faster than the belt model,

Â because it actually helps the, at least, constraint programming solvers

Â to make use of these digit copy variables in their search.

Â 12:58

So what we've got here is a further example of modelling from different

Â viewpoints, multiple modelling.

Â The belt problem itself is an adaptation,

Â a generalisation of the Langford's problem, which is a mathematical puzzle,

Â which is an application in circuit design and other places.

Â And here's an example of where we can model it both from either viewpoints.

Â We can model the belt program just from the primal viewpoint,

Â the position viewpoint, or from the digit copy viewpoint, and it's very natural

Â from the belt viewpoint, but still there was an advantage in a combined model.

Â