This is the eightieth fourth 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 are going to solve Na koń. 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 |
int size = 5; int neighbours = 2; var variables = Enumerable.Range(0, size).Select(x => Enumerable.Range(0, size).Select(y => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray(); var jumps = new List<Tuple<int, int>>(){ Tuple.Create(-2, -1), Tuple.Create(-2, 1), Tuple.Create(-1, -2), Tuple.Create(-1, 2), Tuple.Create(1, -2), Tuple.Create(1, 2), Tuple.Create(2, 1), Tuple.Create(2, -1) }; for(int x=0;x<size;++x){ for(int y=0;y<size;++y){ solver.Set<Equal>( solver.FromConstant(1), solver.Operation<MaterialImplication>( variables[x][y], solver.Operation<IsEqual>( solver.FromConstant(neighbours), solver.Operation<Addition>(jumps.Where(j => x + j.Item1 >= 0 && x + j.Item1 < size && y + j.Item2 >= 0 && y + j.Item2 < size) .Select(j => variables[x+j.Item1][y+j.Item2]).ToArray()) ) ) ); } } var goal = solver.Operation<Addition>(variables.SelectMany(x => x).ToArray()).Create(); solver.AddGoal("g", goal); solver.Solve(); Console.WriteLine(solver.GetValue(goal)); for(int x=0;x<size;++x){ for(int y=0;y<size;++y){ Console.Write(Math.Round(solver.GetValue(variables[x][y]))); } Console.WriteLine(); } |
First, we create variables in line 3. We define one binary digit for each field of the board indicating whether the night is there or not.
Next, we define all possible moves in lines 5-14.
Finally, we iterate over all fields and use if condition to enforce that there must be one neighbour if given field is selected. So we sum all neighbours (line 24), we use material implication to indicate that if the current field is selected (line 21) then the sum of neighbours must be equal to (22-25).
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 |
Tried aggregator 2 times. MIP Presolve eliminated 62 rows and 29 columns. MIP Presolve modified 292 coefficients. Aggregator did 105 substitutions. Reduced MIP has 159 rows, 92 columns, and 636 nonzeros. Reduced MIP has 92 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (0.78 ticks) Found incumbent of value 0.000000 after 0.00 sec. (1.40 ticks) Probing time = 0.00 sec. (0.20 ticks) Tried aggregator 1 time. Reduced MIP has 159 rows, 92 columns, and 636 nonzeros. Reduced MIP has 92 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (0.34 ticks) Probing time = 0.00 sec. (0.20 ticks) Clique table members: 309. 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. (0.85 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 0.0000 25.0000 64 --- * 0+ 0 8.0000 25.0000 64 212.50% 0 0 19.3169 71 8.0000 19.3169 64 141.46% * 0 0 integral 0 16.0000 Cuts: 80 86 0.00% 0 0 cutoff 16.0000 16.0000 86 0.00% Elapsed time = 0.03 sec. (7.65 ticks, tree = 0.00 MB, solutions = 3) Clique cuts applied: 29 Cover cuts applied: 13 Implied bound cuts applied: 12 Mixed integer rounding cuts applied: 8 Gomory fractional cuts applied: 1 Root node processing (before b&c): Real time = 0.03 sec. (7.67 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) = 0.03 sec. (7.67 ticks) 16 01110 11011 10001 11011 01110 |