This is the eightieth 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 are going to solve Słupki rosną riddle. We have a board chipped into multiple parts. We need to build poles of different heights so that each chipped part has at most four fields selected.

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 |
var board = new[]{ new[]{1,1,1,1,1,2,2,2,2}, new[]{1,3,1,4,1,2,5,2,2}, new[]{1,3,1,4,1,1,5,5,2}, new[]{3,3,3,4,4,4,5,5,2}, new[]{6,3,4,4,4,4,5,2,2}, new[]{6,6,6,4,7,5,5,2,2}, new[]{8,6,6,7,7,7,9,9,2}, new[]{8,8,8,8,7,9,9,9,9} }; int width = board[0].Length; int height = board.Length; var variables = board.Select(r => r.Select(c => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray(); for(int p=1;p<=9;++p){ var matching = new List<IVariable>(); for(int r = 0; r< height;++r){ for(int c=0;c<width;++c){ if(board[r][c] == p){ matching.Add(variables[r][c]); } } } solver.Set<Equal>(solver.FromConstant(4), solver.Operation<Addition>(matching.ToArray())); } for(int c=0;c<width;++c){ for(int r=1;r<height;++r){ solver.Set<LessOrEqual>(variables[r-1][c], variables[r][c]); } } var heights = Enumerable.Range(0, width) .Select(c => solver.Operation<Addition>(Enumerable.Range(0, height).Select(r => variables[r][c]).ToArray())).ToArray(); solver.Set<AllDifferent>(heights[0], heights.Skip(1).ToArray()); solver.AddGoal("g", solver.FromConstant(0)); solver.Solve(); for(int r=0;r<height;++r){ for(int c=0;c<width;++c){ Console.Write(solver.GetValue(variables[r][c])); } Console.WriteLine(); } foreach(var h in heights){ Console.Write(solver.GetValue(h)); } |

First, we define a board. Next, we make sure that each part has exactly four fields selected (line 27).

Next, we make sure that poles are continuous and going up (lin 32). If the field below wasn’t selected then field above cannot be selected either which we represent with less or equal constraint.

Finally, we make sure that all poles are of a different height (lines 36-38).

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 |
Tried aggregator 1 time. MIP Presolve eliminated 112 rows and 75 columns. MIP Presolve modified 376 coefficients. Reduced MIP has 249 rows, 141 columns, and 2613 nonzeros. Reduced MIP has 141 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (2.19 ticks) Found incumbent of value 0.000000 after 0.02 sec. (4.28 ticks) Root node processing (before b&c): Real time = 0.02 sec. (4.29 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.02 sec. (4.29 ticks) 001000000 001001000 011001000 011001100 011001101 011101101 011111101 111111101 168327504 |