The young Emperor Xian grow up, but it was Cao Cao who was really in control on the Han nation. Unhappy with this, Emperor Xian wanted to pass a secret order to Liu Bei requesting Cao Cao be removed. The order was locked in a golden container within a specially designed belt. 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. 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. So the emperor has given Liu Bei a belt and some gems, and he really wants to test that Liu Bei is intelligent enough to be an ally, but also give him the secret message. 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. So we're giving m copies of each of the numbers 1 to n. 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. 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. 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. 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. So the belt problem is an assignment problem and a bijection, and so it must have an inverse viewpoint. 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. 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. 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. 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. 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. 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? 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. 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. 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. 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. 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. 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.
