Cao Cao and the Sun-Liu alliance were both gathering their armies at Xubi where they were going to have a battle. To create a distraction, Cao Cao sent Xiahou Dun to assault Liu Bei's base, Xia Co. Zhuge Liang had been expecting this, and planned to establish crossbow traps along the roads towards Xia Co, that Cao Cao's army would pass through. The crossbows were delicately designed so that each of them could fire arrow shots in eight directions at once. A trap was made up of multiple crossbows arranged in a square grid. If the crossbows were poorly positioned, there was a risk they could strike and destroy each other if releasing arrows at the same time. This would need to be avoided when setting up the traps. [SOUND] To reduce the risk of Cao Cao's army being able to identify the traps, Liu Bei needed to configure them in different ways. Zhuge Liang stressed that at least four different configurations were needed. He pulled out the tablet to work these out. [SOUND] >> So, Zhuge Liang is going to set some traps to catch Cao Cao's army, and he's going to use these wonderful eight-way crossbow bolt traps. So an eight-way crossbow fires in eight directions at once. So, it fires in all of those cardinal directions, north, south, east, west, and northeast, southeast, southwest and northwest. And so, basically, if we're thinking about covering this grid, it covers these squares, it'll be fatal to be in any of these squares where it can reach. [COUGH] So if we place an 8-way crossbow trap down on the map, then these are the squares that it's going to be able to cover in this position. And if there's a soldier caught there when the trap goes off, of course they're going to be killed, and if there's soldiers in these other positions, they're going to be killed. And [COUGH] now, when we configure the two traps, we don't want to have two of them be able to shoot each other, because that would make them malfunction. And so, we can't have them so they can shoot each other. So, that would be not allowed. And we need to put lots of traps in there to catch as many soldiers as we can. And so, if we do this configuration, for example, obviously many of the traps are going to shoot other traps. That's not allowed. But if we look at this configuration, then this trap can't shoot any others. This one can't, this one can't, that one can't. So, all five of them can't shoot any opponents. So, that's a proper configuration. It's got the maximum number of crossbows trapped in there to cause the maximum havoc. So [COUGH] basically our problem is going to be setting up seven crossbow traps on the 7 by 7 grid. Now, Zhuge Liang realizes that he needs to put these in different fields, and he needs at least four different solutions, so, because if he uses the same solution for how he places the traps, then once Cao Cao's army hits the first field, then they'll be able to work out where the traps are in the second field and avoid them. So, this is the summary of our problem. We need to put these armed crossbow traps in an n x n field of battle. Each of the crossbow traps fires in these eight directions. And we can't have it that any crossbow trap could hit another. And we need four different configurations to use in different fields, all right. So, let's start with our model of the decisions. The model's fairly simple in terms of decisions. We have the size of the field, n, so n by n field, and then we've got this array of Booleans telling us where do we place the trap. So is a trap placed in this position i,j if t of i j is true? And we need that there's n of those traps, because we know already, that that's the maximum number of traps we could fit in an n by n field, otherwise, there would be two in the same column or two in the same row for sure. So, there's a very simple model. Now we need the constraints, of course, so we're. We want no two traps on the same row. We're just looking across every row, and we're summing up the number of traps in that row. It has to be less than or equal to one. And similarly, no two traps on the same column. We just look at every column, sum up the number of traps on that column, has to be less than or equal to one. And we need no two traps on the same diagonals. This is a bit more complicated, but basically, we can number the diagonals in this direction, from 1 minus n to n minus 1. And make sure that there's only one trap on each of those diagonals, and number the diagonals in the other direction, and make sure there's only one trap on each of those diagonals. So, if we run this model with n equals 7, the four first solutions that pop out are these ones. And unfortunately, you can see that they're not really that different. If I take this solution here, and look at it this way, then I'm going to see this solution here. And similarly, if I take that solution and look at it that way, I'll see that solution here. So really, once Cao Cao sees this layout, they'll be able to deduce this layout. So, this is not good enough for Zhuge Liang. So what we're talking about here is geometric symmetries. So, if we take a solution to the crossbow trap problem, and we do any of these symmetric style operations, we rotate it 90 or 180 or 270 degrees, or we flipped it, so we can flip it on the y axis, we can flip it on the x axis, we can flip it in this diagonal and flip it on that diagonal. Then we're also guaranteed to get another solution to the crossbow trap problem, because obviously if we change these things here, of course, the rotations actually give you a back up, exactly the same thing. The flips give you a different pattern, but you can see that none of the crossbow traps here can hide each other, so it's still a good solution to the problem. So, really, because we don't care of which rotation or flip of the field that we see, it's really the same arrangement. And so, what we've got here is an example of variable symmetries. So, variable symmetries of a problem means that if we take a solution and we map the variables in a bijection, so we map each index variable to a different index, right? Make this, so g of i is a permutation, then we give them the values of these in the same order, that's still going to give us the solution. And so, these geometric symmetries we looked at in the previous slide are all examples of bijections which map the 16 variables of the 4 by 4 into another arrangement of the same 16 variables. So, interchanging the values of the variables in these solutions by rotation gives us another solution. And, of course, symmetries is problematic. So, the last two arrangements, 4 and 3, are symmetric to the first two using this rotate 90 operation, whereas, these two arrangements are distinct. There's no way you can take this and rotate it or flip it and get this one. And so, what we're seeing here is a notion of symmetry classes. So, all the solutions that can be contained from it can get from one solution to another are in the same symmetry class. So, these two solutions here are in the same symmetry class, we can go from this one to this one by r90, we can go from this one to this one by r270. And similarly, for these two. So, these are two separate symmetry classes, and we've got two examples of each of the classes. For the 4 Crossbow Trap problem, there's actually only two solutions, we saw them already. And there's only one symmetry class, because we can obviously get from each of these to each by any flip. And they stay the same by rotation. So, what Zhuge Liang wants is only one solution in each symmetry class. And so, we're going to try to have a way of doing that. So, what we're going to do is choose the lexicographical least solution. And so, we can think about each of these layouts as a list of zeros and ones, for where the traps are. So, the first one is these 16 numbers. Right? So 0010, and then 1000, etc, and the second the 16 numbers, so 0100 etc, and we can see that this solution is lexicographically less solution. So this is the one we're going to prefer. So basically, we're going to pick. Out of the symmetry class, we're going to just try to pick lexicographically least solution, so that we only get one solution for each symmetry clause. So, that's the one we're going to pick. So, what we're going to do is going to use what's called LexLeader symmetry breaking. We're going to add constraints, which are going to force that the solution is lexicographically smaller than any other solution symmetric class. And the way we do this is basically a constraint saying x1 to xn is the thing that we're trying to make lex least, is lex less than this permuted version of the variables? So, for example, we take, here's our original variables, and we rotate them 90, here's the new variables, we just want this, think of this array from there, long like this whole array. In row order, is less than this array in lexigraphic order. So, we're going to add a lexigraphic constraint between those. So, we can easily enough do that using Minizinc. So here is how we add the constraint to make sure that the solution is lex less than its rotated version. [COUGH] So, we're going to build up this s array, which is the lexicographically rotated 90 degrees version of what's going on. So basically, every i, j position here is given by the j, n plus 1 i position in the original array. And then we just add a lex_lesseq constraint saying that this array, so we're converting it to one-dimensional, just using this coercion here. This two-dimensional array, which we're putting in row-wise order as a one-dimensional array, is lexicographically less than this two-dimensional array, again, put into one dimension by row order. And so, you can see how we could do that for each of the others, right? So, here's the symmetry computation. So, this is working out where would i and j go. So this is what goes into position i, j in the rotated 90 version from the original array? And here's our lexicographically less than constraint. So, we're using our global lex_lesseq for lexicographic order, and we can do the same for the other symmetries, the six other symmetries that we want to remove. So we need to add seven symmetry breaking constraints for each of the seven different translations that are possible. And then once we do that, when we run the solution, now the first four solutions that pop out are these four. And you can see that none of them can be obtained from the others by rotation or translation, etc. They're all in a different symmetry class, and therefore, they're going to suit Zhuge Liang because once Cao Cao sees any of these patterns, they won't be able to discern the outer pattern. So, each solution is in a different symmetry class, and that's the key, because we added constraints to force that we only get the lexicographically least solution out of every symmetry class. So, MiniZinc has a library for common symmetries, so rather than defining your own, you can use that library. So for example, the var_sqr_sym constraint enforces that a square array of integers, we just get the lexicographically least version with respect to all the reflection and rotation symmetries. So, we could have easily changed our model, removing all of these constraints that looked like this. We had to add seven things that looked like that, and just replaced them with this var_sqr_sym constraint. Now, what we see here is the symmetries arise, and they rose actually because they're a representation of the problem. Sometimes we can get away without having to worry about symmetry breaking. So, if you think back to an earlier problem, we talked about representing a fixed cardinality set, so this is a set of size three of values from 1 to 10. [COUGH] And when we add it, we have to add these constraints saying that none of these two values in the array are the same. Otherwise, it wouldn't be a set of cardinality three. And if you look at what happens, we end up with basically a number of different arrays that all correspond to the same set. And we had to add symmetry-breaking constraints. Again, and basically, if you think about this is a lex leader about all of the different possible ways to represent this set. But if we could do it a different way, we can use a set variable. So, if we just use the var set from 1 to 10 and added the cardinality constraint, now, the set variable itself takes care of that symmetry for us, and there's no symmetric solutions. And so, sometimes if we think about using a different representation of the model, we can actually not have to worry about symmetries. But of course, there's this tradeoff. So, does our solver actually natively handle set variables? If it doesn't, then possibly using set variable is going to be expensive. Even if it does natively handle set variables, maybe it's going to be slower than integral variables, which much more core to a discreet optimization solver. But we get rid of this symmetric solutions problem, or part of it, perhaps. So, in summary, symmetries occur frequently in discrete optimization, we've already talked about symmetries earlier in the course. And we can add symmetry breaking constraints to get rid of them to avoid them. So, variable symmetry, that's where we can take the solution and permute the variables and get another solution, are very common and we use this LexLeader symmetry breaking. Basically, adding lexicographical constraints, forcing that we only get the lexicographical least solution out of any solution class. And you can use the MiniZinc Symmetry Library, we shall have definitions for most of the common symmetries you'll come across. And indeed, the Crossbow Trap Problem here is a version of the well studied n-queens problems. So finally, we talk briefly about the fact that problems can have different models, you've already seen that. Lots of ties in this course, and some might have symmetries which we need to break, and others do not. And then we have to think about the tradeoffs between using, say ,set variables where we don't have to worry about symmetries, or some of the symmetries of the problem, or using a representation of set variables where we do have to model that symmetric problem, as well.
