This is the ninetieth eighth 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 Horrendum 2. We have a rectangular board. We need to fill the board with numbers from zero to four in a way that each row and column has 5 numbers and 3 empty fields. Also, each field with arrow indicates how many fields are filled in the rest of the row/column according to the direction of the arrow.
Solution:
|
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 |
var board = new [] { " R ", "D D L ", " U U ", "D U R ", " D D", " L D R ", " R D ", " " }; int height = board.Length; int width = board[0].Length; var fields = Enumerable .Range(0, height) .Select(h => Enumerable .Range(0, width) .Select(w => solver.CreateAnonymous(Domain.AnyInteger) .Set<GreaterOrEqual>(solver.FromConstant(-3)).Set<LessOrEqual>(solver.FromConstant(4)) ).ToArray() ).ToArray(); // Enforce numbers in arrows for(int i=0;i<height;++i){ for(int j=0;j<width;++j){ if(board[i][j] != ' '){ fields[i][j].Set<GreaterOrEqual>(solver.FromConstant(0)); } } } // Make rows unique for(int i=0;i<height;++i){ solver.Set<AllDifferent>(fields[i][0], Enumerable.Range(1, width - 1).Select(j => fields[i][j]).ToArray()); } // Make columns unique for(int j=0;j<width;++j){ solver.Set<AllDifferent>(fields[0][j], Enumerable.Range(1, height - 1).Select(i => fields[i][j]).ToArray()); } // Make arrows match numbers in rest of the line for(int i=0;i<height;++i){ for(int j=0;j<width;++j){ if(board[i][j] == ' '){ continue; } IVariable[] rest = null; if(board[i][j] == 'R'){ rest = Enumerable.Range(j + 1, width - j - 1).Select(k => fields[i][k]).ToArray(); } else if(board[i][j] == 'D'){ rest = Enumerable.Range(i + 1, height - i - 1).Select(k => fields[k][j]).ToArray(); } else if(board[i][j] == 'L'){ rest = Enumerable.Range(0, j).Select(k => fields[i][k]).ToArray(); } else { rest = Enumerable.Range(0, i).Select(k => fields[k][j]).ToArray(); } solver.Operation<Addition>(rest.Select(v => v.Operation<IsGreaterOrEqual>(solver.FromConstant(0))).ToArray()) .Set<Equal>(fields[i][j]); } } var goal = solver.FromConstant(0); solver.Solve(); for(int i=0;i<height;++i){ for(int j=0;j<width;++j){ var value = Math.Round(solver.GetValue(fields[i][j])); if(value < 0){ Console.Write(" "); }else { Console.Write(value); } } Console.WriteLine(); } Console.WriteLine(); |
As usual, we start with the board (lines 1-13). Next, we represent the board as a series of integers. Each field will be filled, and we’ll represent the empty fields with negative numbers (lines 15-22).
Next, we make sure that fields with arrows are filled (lines 24-31).
Next, we enforce rows and columns (like in Sudoku) – lines 3-41.
Finally, we take all the fields indicated by arrows, and make sure that these fields are filled accordingly (lines 43-65).
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 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 |
Tried aggregator 2 times. MIP Presolve eliminated 1536 rows and 919 columns. MIP Presolve modified 4614 coefficients. Aggregator did 91 substitutions. Reduced MIP has 2337 rows, 999 columns, and 6490 nonzeros. Reduced MIP has 938 binaries, 61 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (6.74 ticks) Probing fixed 17 vars, tightened 7 bounds. Probing changed sense of 440 constraints. Probing time = 0.03 sec. (12.09 ticks) Cover probing fixed 0 vars, tightened 25 bounds. Tried aggregator 2 times. MIP Presolve eliminated 223 rows and 153 columns. MIP Presolve modified 283 coefficients. Aggregator did 336 substitutions. Reduced MIP has 1778 rows, 510 columns, and 5263 nonzeros. Reduced MIP has 450 binaries, 60 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (6.03 ticks) Probing fixed 2 vars, tightened 1 bounds. Probing time = 0.01 sec. (3.78 ticks) Cover probing fixed 0 vars, tightened 1 bounds. Tried aggregator 2 times. MIP Presolve eliminated 6 rows and 4 columns. MIP Presolve modified 65 coefficients. Aggregator did 1 substitutions. Reduced MIP has 1771 rows, 505 columns, and 5242 nonzeros. Reduced MIP has 445 binaries, 60 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (5.36 ticks) Probing time = 0.02 sec. (3.90 ticks) Clique table members: 1249. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 0.00 sec. (7.39 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 104 0.0000 309 0 0 0.0000 91 Cuts: 54 364 0 0 0.0000 157 Cuts: 116 500 0 0 0.0000 66 Cuts: 16 528 0 0 0.0000 100 Cuts: 60 613 0 2 0.0000 100 0.0000 613 Elapsed time = 0.63 sec. (214.60 ticks, tree = 0.01 MB, solutions = 0) 1217 145 0.0000 45 0.0000 24362 2807 188 0.0000 41 0.0000 51662 4355 203 0.0000 46 0.0000 80350 6220 308 0.0000 43 0.0000 103716 6597 339 0.0000 81 0.0000 108402 6672 222 0.0000 37 0.0000 111638 7113 79 0.0000 44 0.0000 126775 7742 94 0.0000 27 0.0000 146791 8246 95 0.0000 50 0.0000 169279 9777 84 0.0000 50 0.0000 230823 Elapsed time = 11.66 sec. (4402.69 ticks, tree = 0.17 MB, solutions = 0) 11346 168 0.0000 63 0.0000 287814 14198 251 0.0000 52 0.0000 386401 17188 477 infeasible 0.0000 502464 20156 771 0.0000 68 0.0000 618516 23390 750 0.0000 41 0.0000 743953 27088 764 0.0000 37 0.0000 870399 30492 1020 0.0000 49 0.0000 994022 34095 1084 0.0000 39 0.0000 1119451 37785 1178 0.0000 84 0.0000 1252184 41440 1266 0.0000 44 0.0000 1383705 Elapsed time = 44.86 sec. (13959.22 ticks, tree = 0.10 MB, solutions = 0) 45089 1401 0.0000 59 0.0000 1513966 48587 1462 0.0000 37 0.0000 1641233 52107 1442 infeasible 0.0000 1773688 55809 1700 0.0000 37 0.0000 1905442 59276 1830 0.0000 84 0.0000 2043446 62717 1679 0.0000 43 0.0000 2180412 66350 1448 0.0000 48 0.0000 2310054 70373 1480 infeasible 0.0000 2439498 74281 1234 0.0000 29 0.0000 2566073 78479 1110 0.0000 52 0.0000 2697817 Elapsed time = 74.02 sec. (23512.97 ticks, tree = 0.09 MB, solutions = 0) 82527 873 0.0000 36 0.0000 2818290 86790 490 infeasible 0.0000 2956576 * 87578 306 integral 0 0.0000 0.0000 2984334 0.00% Root node processing (before b&c): Real time = 0.61 sec. (213.77 ticks) Parallel b&c, 8 threads: Real time = 79.80 sec. (25497.28 ticks) Sync time (average) = 7.33 sec. Wait time (average) = 0.02 sec. ------------ Total (root+branch&cut) = 80.41 sec. (25711.05 ticks) 1 3204 3 4 210 0 3421 23140 40 132 41 2 30 2301 4 0 214 3 |