This is the eightieth 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 Lying riddle (Kłamigłówka).

We have a board split into parts. Each part has some numbers in it. A number indicates how many neighbouring fields (up, down, left, or right) are selected. One number in each part lies.

We need to select fields according to numbers. However, two selected fields cannot be neighbours and if they touch corners then they can’t split the board into multiple parts.

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 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 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 |
using System; using System.Collections.Generic; using System.Linq; using MilpManager.Abstraction; using MilpManager.Utilities; using CplexMilpManager.Implementation; namespace LyingRiddle { public class Program { public static void Start(IMilpSolver solver) { var parts = new int[,]{ {1, 1, 2, 2, 2, 2, 2, 3, 3, 3}, {1, 1, 4, 5, 5, 5, 5, 3, 3, 3}, {1, 1, 4, 5, 5, 5, 5, 3, 3, 3}, {1, 1, 4, 6, 6, 6, 7, 7, 7, 7}, {8, 8, 8, 6, 6, 6, 7, 7, 7, 7}, {8, 8, 8, 6, 6, 6, 7, 7, 7, 7}, {8, 8, 8, 6, 6, 6, 9, 9, 10, 10}, {11, 11, 11, 11, 12, 12, 9, 9, 10, 10}, {13, 13, 13, 13, 12, 12, 9, 9, 10, 10}, {13, 13, 13, 13, 12, 12, 9, 9, 10, 10} }; var numbers = new int[,] { {-1, 1, -1, 2, -1, 2, -1, 2, -1, 2}, {2, -1, 1, -1, -1, -1, 2, -1, 2, -1}, {-1, 3, -1, 3, -1, 3, -1, 3, -1, -1}, {2, -1, 1, -1, -1, -1, -1, 1, 2, -1}, {-1, 3, -1, 3, 2, -1, -1, -1, 3, -1}, {-1, -1, 3, -1, 3, -1, 2, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, 1}, {2, -1, -1, 1, -1, 2, 3, -1, 2, -1}, {-1, 3, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, 2, -1, -1, 2, -1, 2, -1, 2} }; int height = 10; int width = 10; var board = Enumerable.Range(0, height).Select(h => Enumerable.Range(0, width).Select(w => new Field { Part = parts[h, w], Number = numbers[h, w], Selected = solver.CreateAnonymous(Domain.BinaryInteger), IsLying = solver.CreateAnonymous(Domain.BinaryInteger), Id = solver.CreateAnonymous(Domain.PositiveOrZeroInteger), LowerCount = solver.FromConstant(-1), Neighbours = new List<Field>() }).ToArray()).ToArray(); // Calculate neighbours for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { if (h > 0) board[h][w].Neighbours.Add(board[h - 1][w]); if (h < height - 1) board[h][w].Neighbours.Add(board[h + 1][w]); if (w > 0) board[h][w].Neighbours.Add(board[h][w - 1]); if (w < width - 1) board[h][w].Neighbours.Add(board[h][w + 1]); } } // Exactly one lier in each part foreach (var part in Enumerable.Range(0, board.SelectMany(f => f).Max(f => f.Part))) { var partFields = board .SelectMany(f => f) .Where(f => f.Number != -1) .Where(f => f.Part == part + 1) .Select(f => f.IsLying).ToArray(); solver.Set<Equal>( solver.FromConstant(1), solver.Operation<Addition>(partFields) ); } // Field with number cannot be selected foreach (var field in board.SelectMany(f => f).Where(f => f.Number != -1)) { field.Selected.Set<Equal>(solver.FromConstant(0)); } // Selected fields cannot touch edges for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { foreach (var neighbour in board[h][w].Neighbours) { neighbour.Selected.Operation<Conjunction>(board[h][w].Selected).Set<Equal>(solver.FromConstant(0)); } } } // Fields with number must have correct neighbours count for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { if (board[h][w].Number != -1) { solver.Set<Equal>( solver.Operation<Addition>(board[h][w].Neighbours.Select(x => x.Selected).ToArray()) .Operation<IsEqual>(solver.FromConstant(board[h][w].Number)), solver.Operation<BinaryNegation>(board[h][w].IsLying) ); } } } // Make sure field is not isolated for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { solver.Set<LessOrEqual>( solver.Operation<Addition>(board[h][w].Neighbours.Select(n => n.Selected).ToArray()), solver.FromConstant(board[h][w].Neighbours.Count - 1) ); } } // Make sure that we do not split the board board[height - 1][0].Id.Set<Equal>(solver.FromConstant(1)); board[height - 1][0].Selected.Set<Equal>(solver.FromConstant(0)); for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { // Calculate lower count board[h][w].LowerCount = solver.Operation<Addition>( board[h][w].Neighbours .Select(n => n.Id.Operation<IsLessThan>(board[h][w].Id)) .ToArray() ); // Id is limited var highestId = 30; board[h][w].Id.Set<LessOrEqual>(solver.FromConstant(highestId)); // Selected fields have super big id solver.Set<Equal>( solver.FromConstant(1), board[h][w].Selected.Operation<MaterialImplication>(solver.Operation<IsEqual>(board[h][w].Id, solver.FromConstant(highestId))) ); // Fields next to each other should differ by one unless any of them is selected foreach (var neighbour in board[h][w].Neighbours) { solver.Operation<Disjunction>(board[h][w].Selected, neighbour.Selected).Operation<BinaryNegation>().Operation<MaterialImplication>( solver.Operation<AbsoluteValue>(solver.Operation<Subtraction>(board[h][w].Id, neighbour.Id)).Operation<IsEqual>(solver.FromConstant(1)) ).Set<Equal>(solver.FromConstant(1)); } // Only one field can have no lower neighbours, all others must have a path if (h == height - 1 && w == 0) { board[h][w].LowerCount.Set<Equal>(solver.FromConstant(0)); } else { board[h][w].LowerCount.Set<GreaterOrEqual>(solver.FromConstant(1)); } } } solver.AddGoal("g", solver.FromConstant(0)); solver.Solve(); for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { if (numbers[h, w] != -1) { Console.Write(numbers[h, w]); } else { Console.Write((int)solver.GetValue(board[h][w].Selected) == 1 ? "X" : " "); } } Console.WriteLine(); } Console.WriteLine(); } static void Main() { var solver = new CplexMilpSolver(new CplexMilpSolverSettings { IntegerWidth = 5, Epsilon = 0.00001, StoreDebugExpressions = false, CacheConstants = false, StoreDebugConstraints = false }); Start(solver); } } public class Field { public int Part { get; set; } public int Number { get; set; } public IVariable Selected { get; set; } public IVariable IsLying { get; set; } public IVariable Id { get; set; } public IVariable LowerCount { get; set; } public List<Field> Neighbours { get; set; } } } |

First, in lines 14-38 we define the input. For numbers we use -1 to indicate there is no number in given field.

Next, we calculate neighbours in lines 55-64, just to know which fields are next to each other.

We start with straightforward constraints: one lier in each part (71-82), fields with number can’t be selected (85-88), selected fields can’t be next to each other (91-100), fields with numbers must have correct selected neighbours unless they lie (103-116).

Now, we take care of the requirement that we can’t split the board. First, we make sure a particular field is not isolated (123-132).

Next, we need to build a road from the starting position (bottom left corner) to each field. So we make sure that field is not selected and that we start counting from one (135-136).

Next, we calculate lower neighbours (142-147), we make sure that selected fields have very high id (150-157). Next, fields next to each other must differ by one unless any of them is selected (160-165). Finally, only one field (bottom left corner) can have no lower neighbours (168-174). That’s all.

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 |
Parallel mode: none, using 1 thread. Root relaxation solution time = 0.01 sec. (9.18 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 363 0.0000 356 0 0 0.0000 69 Cuts: 10 571 0 0 0.0000 132 Cuts: 67 653 * 0+ 0 0.0000 0.0000 653 0.00% 0 0 cutoff 0.0000 0.0000 653 0.00% Elapsed time = 0.86 sec. (436.87 ticks, tree = 0.00 MB, solutions = 1) Clique cuts applied: 2 Cover cuts applied: 23 Implied bound cuts applied: 6 Flow cuts applied: 1 Mixed integer rounding cuts applied: 3 Zero-half cuts applied: 3 Gomory fractional cuts applied: 16 Root node processing (before b&c): Real time = 0.86 sec. (437.18 ticks) Sequential b&c: Real time = 0.00 sec. (0.00 ticks) ------------ Total (root+branch&cut) = 0.86 sec. (437.18 ticks) X1 2X2X2 2 2 1 2X2 X3X3X3X3X 2 1X X 12 X3X32 X3X 3X3X2 X X X X X 1 2 1 23X2X X3X X 2X 2X2X2 |