This is the ninetieth ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra
Today we’re going to solve MacMahon Squares. Let’s see the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
var elements = new []{ new [] {0, 0, 0, 0}, new [] {1, 0, 0, 0}, new [] {1, 1, 0, 0}, new [] {1, 0, 1, 0}, new [] {1, 1, 1, 0}, new [] {1, 1, 1, 1}, new [] {1, 2, 0, 0}, new [] {1, 0, 2, 0}, new [] {1, 0, 0, 2}, new [] {1, 2, 2, 0}, new [] {1, 2, 0, 2}, new [] {1, 2, 2, 2}, new [] {1, 1, 2, 0}, new [] {1, 1, 0, 2}, new [] {1, 1, 2, 2}, new [] {0, 2, 2, 1}, new [] {1, 0, 1, 2}, new [] {1, 2, 1, 2}, new [] {1, 1, 1, 2}, new [] {2, 0, 0, 0}, new [] {2, 2, 0, 0}, new [] {2, 0, 2, 0}, new [] {2, 2, 2, 0}, new [] {2, 2, 2, 2} }; int width = 6; int height = 4; int rotations = elements[0].Length; int elementsCount = elements.Length; var fields = Enumerable.Range(0, height).Select(h => Enumerable.Range(0, width).Select(w => Enumerable.Range(0, elementsCount).Select(e => Enumerable.Range(0, rotations).Select(r => solver.CreateAnonymous(Domain.BinaryInteger) ).ToArray() ).ToArray() ).ToArray() ).ToArray(); // Make sure that each element is selected only once and in only one rotation for(int element=0;element < elementsCount;++element){ var flags = Enumerable.Range(0, height).SelectMany(h => Enumerable.Range(0, width).SelectMany(w => Enumerable.Range(0, rotations).Select(r => fields[h][w][element][r] ) ) ).ToArray(); solver.Operation<Addition>(flags).Set<Equal>(solver.FromConstant(1)); } // Make sure that each field has exactly one element assigned for(int h = 0; h < height; ++h){ for(int w = 0; w < width; ++w){ var flags = Enumerable.Range(0, elementsCount).SelectMany(e => Enumerable.Range(0, rotations).Select(r => fields[h][w][e][r] ) ).ToArray(); solver.Operation<Addition>(flags).Set<Equal>(solver.FromConstant(1)); } } // Make sure that edges match going right for(int h = 0; h < height; ++h){ for(int w = 0; w < width - 1; ++w){ for(int element = 0; element < elementsCount;++element){ for(int element2 = 0; element2 < elementsCount; ++ element2){ if(element == element2){ continue; } for(int rotation = 0; rotation < rotations;++rotation){ for(int rotation2 = 0; rotation2 < rotations; ++ rotation2){ if(elements[element][(rotation + 1) % rotations] != elements[element2][(rotation2 + 3) % rotations]){ solver.Set<Equal>( fields[h][w][element][rotation].Operation<Conjunction>(fields[h][w+1][element2][rotation2]), solver.FromConstant(0) ); } } } } } } } // Make sure that edges match going down for(int h = 0; h < height - 1; ++h){ for(int w = 0; w < width; ++w){ for(int element = 0; element < elementsCount;++element){ for(int element2 = 0; element2 < elementsCount; ++ element2){ if(element == element2){ continue; } for(int rotation = 0; rotation < rotations;++rotation){ for(int rotation2 = 0; rotation2 < rotations; ++ rotation2){ if(elements[element][(rotation + 2) % rotations] != elements[element2][(rotation2) % rotations]){ solver.Set<Equal>( fields[h][w][element][rotation].Operation<Conjunction>(fields[h+1][w][element2][rotation2]), solver.FromConstant(0) ); } } } } } } } var goal = solver.FromConstant(0); solver.Solve(); for(int i=0;i<height;++i){ // Top row for(int j=0;j<width;++j){ for(int element = 0; element < elementsCount;++element){ for(int rotation = 0; rotation < rotations;++rotation){ if(solver.GetValue(fields[i][j][element][rotation]) > 0.5){ Console.Write(" " + elements[element][rotation] + " "); } } } } Console.WriteLine(); // Left and right for(int j=0;j<width;++j){ for(int element = 0; element < elementsCount;++element){ for(int rotation = 0; rotation < rotations;++rotation){ if(solver.GetValue(fields[i][j][element][rotation]) > 0.5){ Console.Write(elements[element][(rotation + 3) % rotations] + " " + elements[element][(rotation + 1) % rotations]); } } } } Console.WriteLine(); // Bottom row for(int j=0;j<width;++j){ for(int element = 0; element < elementsCount;++element){ for(int rotation = 0; rotation < rotations;++rotation){ if(solver.GetValue(fields[i][j][element][rotation]) > 0.5){ Console.Write(" " + elements[element][(rotation + 2) % rotations] + " "); } } } } Console.WriteLine(); } Console.WriteLine(); for(int i=0;i<height;++i){ for(int j=0;j<width;++j){ for(int element = 0; element < elementsCount;++element){ for(int rotation = 0; rotation < rotations;++rotation){ if(solver.GetValue(fields[i][j][element][rotation]) > 0.5){ Console.Write(element + "_" + rotation + ","); } } } } Console.WriteLine(); } Console.WriteLine(); |
Let’s start with elements. We take the following image and want to encode is an array of integers (lines 1-26). Each square has four triangles: the top one, the right one, the bottom one, and the left one. We then number colors, so white is assigned 0, red is 1, blue is 2. So numbers 1, 0, 2, 0 represent a square that is white on the top, blue on the bottom, and has white sides (second square from the left in the second row).
We then define some helper variables for the board size (lines 28-31).
Next, we define the board a four-dimensional array. First dimension is the Y axis (height), then X axis (width), number of square, and finally its rotation. So element fields[y][x][element][rotation] indicates whether we decided to put element element rotated rotation times in field x, y.
Okay, now we need to encode rules. We start with the requirement that each element must be placed on the board just once. So for each element we take all the fields for all the positions and all the rotations, sum all of that, and make sure it’s equal to one – lines 43-53.
Now we do the same for all fields. So we iterate over fields, and for every one of them we take all the elements in all the rotations, sum the variables, and set to one – lines 55-65.
Now we need to match the edges. We iterate over all fields that have right edge and some other field on the right. We then iterate over all elements, and check all of their rotation combinations. We take every combination for which edges do not match, and then we make sure that such a combination cannot be selected for these two fields. This is in line 68-89. We then do the same for bottom and top endges – lines 91-113.
That’s it. Now the output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
Tried aggregator 1 time. MIP Presolve eliminated 668917 rows and 227244 columns. MIP Presolve modified 11663 coefficients. Reduced MIP has 11711 rows, 1920 columns, and 231308 nonzeros. Reduced MIP has 1920 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 5.44 sec. (2525.73 ticks) Probing time = 0.03 sec. (3.43 ticks) Tried aggregator 1 time. Reduced MIP has 11711 rows, 1920 columns, and 231308 nonzeros. Reduced MIP has 1920 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.56 sec. (285.78 ticks) Probing time = 0.06 sec. (3.44 ticks) Clique table members: 11711. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 2.78 sec. (1115.33 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 0.0000 0.0000 10 0.00% 0 0 cutoff 0.0000 0.0000 10 0.00% 0 0 cutoff 0.0000 0.0000 10 0.00% Elapsed time = 9.94 sec. (4355.76 ticks, tree = 0.00 MB, solutions = 1) Root node processing (before b&c): Real time = 9.98 sec. (4362.11 ticks) Parallel b&c, 8 threads: Real time = 0.00 sec. (0.00 ticks) Sync time (average) = 0.00 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 9.98 sec. (4362.11 ticks) 0 1 1 2 1 1 2 22 00 00 11 11 2 0 0 1 1 0 2 0 0 1 1 0 2 1 00 00 22 11 22 1 0 0 0 1 0 2 0 0 0 1 0 2 1 00 22 11 11 22 2 1 0 1 1 2 0 1 0 1 1 2 0 0 22 00 22 22 22 2 1 2 2 1 2 1 21_1,8_0,3_0,13_3,4_1,14_1, 1_1,0_0,6_0,18_0,7_1,11_3, 2_2,19_3,12_3,5_0,15_0,22_1, 16_2,20_2,9_0,17_0,23_0,10_2, |
So we can see, that in the top right corner we selected element number 21 (it’s 0-based) in first rotation (again, 0-based). And so on.