This is the seventieth fifth 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 100 and 13. We have a board with numbers and we need to find a path with given amount of numbers, with some specific sum, and where all numbers are different. First, data model:

1 2 3 4 5 6 7 8 9 10 11 |
public class Field{ public int Value {get;set;} public IVariable Selected {get;set;} public IVariable Up {get;set;} public IVariable Down {get;set;} public IVariable Left {get;set;} public IVariable Right {get;set;} public IVariable[] AllDirections { get { return new IVariable[]{Up, Down, Left, Right}; } } public IVariable DirectionsCount {get;set;} public IVariable Identifier {get;set;} } |

And now the 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 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 |
var board = new int[][]{ new int[]{2, 5, 11, 4, 6}, new int[]{10, 14, 9, 15, 6}, new int[]{7, 15, 9, 8, 1}, new int[]{8, 11, 1, 3, 10}, new int[]{3, 14, 13, 5, 2} }; var sum = 100; var length = 13; var height = board.Length; var width = board[0].Length; // Create fields var fields = board.Select(r => r.Select(c => new Field{ Value = c, Selected = solver.CreateAnonymous(Domain.BinaryInteger), Up = solver.CreateAnonymous(Domain.BinaryInteger), Down = solver.CreateAnonymous(Domain.BinaryInteger), Left = solver.CreateAnonymous(Domain.BinaryInteger), Right = solver.CreateAnonymous(Domain.BinaryInteger), Identifier = solver.CreateAnonymous(Domain.PositiveOrZeroInteger) }).ToArray()).ToArray(); // Block invalid directions for(int row=0;row<height;++row){ for(int column=0;column<width;++column){ if(row == 0)fields[row][column].Up.Set<Equal>(solver.FromConstant(0)); if(row == height - 1)fields[row][column].Down.Set<Equal>(solver.FromConstant(0)); if(column == 0)fields[row][column].Left.Set<Equal>(solver.FromConstant(0)); if(column == width - 1)fields[row][column].Right.Set<Equal>(solver.FromConstant(0)); } } // Match direction neighbours for(int row=0;row<height;++row){ for(int column=0;column<width;++column){ if(row > 0)fields[row][column].Up.Set<Equal>(fields[row-1][column].Down); if(row < height - 1)fields[row][column].Down.Set<Equal>(fields[row+1][column].Up); if(column > 0)fields[row][column].Left.Set<Equal>(fields[row][column-1].Right); if(column < height - 1)fields[row][column].Right.Set<Equal>(fields[row][column+1].Left); } } // Set Selected properly for(int row=0;row<height;++row){ for(int column=0;column<width;++column){ fields[row][column].Selected.Set<Equal>(solver.Operation<Disjunction>(fields[row][column].AllDirections)); } } // Set path continuous for(int row=0;row<height;++row){ for(int column=0;column<width;++column){ fields[row][column].DirectionsCount = solver.Operation<Addition>(fields[row][column].AllDirections); fields[row][column].DirectionsCount.Set<LessOrEqual>(solver.FromConstant(2)); } } // Set path with start an end solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => f.DirectionsCount).ToArray()).Set<Equal>(solver.FromConstant((length - 2)*2 + 2)); // Set path length solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => f.Selected).ToArray()).Set<Equal>(solver.FromConstant(length)); // Set path sum solver.Operation<Addition>(fields.SelectMany(r => r).Select(f => solver.Operation<Condition>(f.Selected, solver.FromConstant(f.Value), solver.FromConstant(0))).ToArray()).Set<Equal>(solver.FromConstant(sum)); // Set different values on the path { IVariable[] parts = fields.SelectMany(r => r).Select(f => solver.Operation<Condition>(f.Selected, solver.FromConstant(f.Value), solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<GreaterOrEqual>(solver.FromConstant(100)).Set<LessOrEqual>(solver.FromConstant(width*height - length + 100)))).ToArray(); solver.Set<AllDifferent>(parts[0], parts.Skip(1).ToArray()); } // Propagate identifiers for(int row=0;row<height;++row){ for(int column=0;column<width;++column){ List<Tuple<IVariable, IVariable>> neighbours = new List<Tuple<IVariable, IVariable>>(); Field self = fields[row][column]; if(row > 0)neighbours.Add(Tuple.Create(fields[row-1][column].Identifier, self.Up)); if(row < height - 1)neighbours.Add(Tuple.Create(fields[row+1][column].Identifier, self.Down)); if(column > 0)neighbours.Add(Tuple.Create(fields[row][column-1].Identifier, self.Left)); if(column < width - 1)neighbours.Add(Tuple.Create(fields[row][column+1].Identifier, self.Right)); foreach(var n in neighbours){ var difference = self.Identifier.Operation<Subtraction>(n.Item1).Operation<AbsoluteValue>(); n.Item2.Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(1))).Set<Equal>(solver.FromConstant(1)); } foreach(var n1 in neighbours){ foreach(var n2 in neighbours){ if(n1.Item1 == n2.Item1)continue; var difference = n1.Item1.Operation<Subtraction>(n2.Item1).Operation<AbsoluteValue>(); n1.Item2.Operation<Conjunction>(n2.Item2).Operation<MaterialImplication>(difference.Operation<IsEqual>(solver.FromConstant(2))).Set<Equal>(solver.FromConstant(1)); } } } } solver.Solve(); for(int row=0;row<height;++row){ for(int column=0;column<width;++column){ Console.Write(solver.GetValue(fields[row][column].Selected) + ","); } Console.WriteLine(); } Console.WriteLine(); |

First, we define the riddle in lines 1-9, and couple helper variables in 12-13.

Next, we create fields in lines 16-24. `Value`

is just the number in the field. `Selected`

indicates whether the field is chosen to the final result. `Up`

and other directions are for indicting whether path continues in some specific direction from this field. `Identifier`

is to propagate numbers throughout the path to make sure we have only one path on the board.

First, we block invalid directions in lines 26-34. We want to make sure that we don’t step out of the board.

Next, in lines 36-44 we make sure that if some field thinks that path is going in some direction then the neighbour thinks the same.

Next, we make sure that if there is a path in the field then it must be selected (lines 46-51).

Next, we make sure the path is continuous (lines 53-59). This means that it cannot fork so it can go in at most two directions in given field.

Next, we indicate the path has a start and an end (line 62). This is actually not needed as we block forks but better safe than sorry.

We set path length (line 65) and sum of the numbers (line 68).

Next, we make sure that all numbers on the path are different. In lines 71-74 we take all variables and check their `SelectedIdentifier`

to set this constraint, given field must differ from its neighbours by one, and its neighbours must differ by two. This effectively makes creating loops impossible.

Finally, 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 82 83 84 85 86 87 88 89 |
Tried aggregator 2 times. MIP Presolve eliminated 2694 rows and 888 columns. MIP Presolve modified 8814 coefficients. Aggregator did 2484 substitutions. Reduced MIP has 7203 rows, 3808 columns, and 21521 nonzeros. Reduced MIP has 3415 binaries, 393 generals, 0 SOSs, and 0 indicators. Presolve time = 0.09 sec. (48.76 ticks) Probing fixed 70 vars, tightened 50 bounds. Probing changed sense of 325 constraints. Probing time = 0.05 sec. (9.71 ticks) Cover probing fixed 0 vars, tightened 50 bounds. Tried aggregator 2 times. MIP Presolve eliminated 304 rows and 193 columns. MIP Presolve modified 1900 coefficients. Aggregator did 300 substitutions. Reduced MIP has 6599 rows, 3315 columns, and 19898 nonzeros. Reduced MIP has 2922 binaries, 393 generals, 0 SOSs, and 0 indicators. Presolve time = 0.05 sec. (20.59 ticks) Probing time = 0.05 sec. (4.77 ticks) Tried aggregator 1 time. MIP Presolve eliminated 100 rows and 50 columns. Reduced MIP has 6499 rows, 3265 columns, and 19598 nonzeros. Reduced MIP has 2872 binaries, 393 generals, 0 SOSs, and 0 indicators. Presolve time = 0.05 sec. (13.46 ticks) Probing time = 0.03 sec. (3.85 ticks) Clique table members: 13256. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 0.06 sec. (54.46 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 61 0.0000 913 0 0 0.0000 212 Cuts: 509 1471 0 0 0.0000 265 Cuts: 554 1990 Repeating presolve. Tried aggregator 1 time. MIP Presolve eliminated 2554 rows and 1527 columns. Reduced MIP has 3945 rows, 1738 columns, and 11809 nonzeros. Reduced MIP has 1473 binaries, 265 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (10.44 ticks) Probing time = 0.02 sec. (2.67 ticks) Tried aggregator 1 time. Reduced MIP has 3945 rows, 1738 columns, and 11809 nonzeros. Reduced MIP has 1473 binaries, 265 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (4.85 ticks) Represolve time = 0.06 sec. (23.96 ticks) Probing time = 0.01 sec. (2.67 ticks) Clique table members: 7703. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Root relaxation solution time = 0.08 sec. (47.44 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 76 0.0000 2868 0 0 0.0000 142 Cuts: 459 3911 0 0 0.0000 141 Cuts: 84 4355 0 2 0.0000 22 0.0000 4355 Elapsed time = 4.05 sec. (1387.34 ticks, tree = 0.01 MB, solutions = 0) 15 17 0.0000 194 0.0000 9806 * 32+ 15 0.0000 0.0000 18968 0.00% GUB cover cuts applied: 33 Clique cuts applied: 144 Cover cuts applied: 20 Implied bound cuts applied: 287 Mixed integer rounding cuts applied: 8 Zero-half cuts applied: 41 Gomory fractional cuts applied: 8 Root node processing (before b&c): Real time = 4.05 sec. (1385.51 ticks) Parallel b&c, 8 threads: Real time = 0.89 sec. (441.92 ticks) Sync time (average) = 0.56 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 4.94 sec. (1827.43 ticks) 1,1,1,1,1, 1,0,0,0,0, 1,1,1,0,0, 0,0,1,0,0, 1,1,1,0,0, |