This is the ninetieth 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 this riddle. There is a board with yin and yang symbols on it. We need to cut the board in two pieces of the same shape in a way that each part contains exactly one yin and exactly one yang. In other way, we need to draw a continuous line on the board in a way that it splits the board into two parts of the same shape and the same number of yin and yang symbols.

Let’s see the 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 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 |
int width = 6; int height = 4; var board = new IVariable[width, height]; var ids = new IVariable[width, height]; for(int i=0;i<width;++i){ for(int j=0;j<height;++j){ board[i, j] = solver.CreateAnonymous(Domain.BinaryInteger); ids[i, j] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger); } } // Symmetry for(int i=0;i<width;++i){ for(int j=0;j<height;++j){ solver.Operation<Addition>(board[i, j], board[width-i-1, height-j-1]).Set<Equal>(solver.FromConstant(1)); } } // Exactly one yin, yang solver.Operation<Addition>(board[1, 0], board[2, 0]).Set<Equal>(solver.FromConstant(1)); solver.Operation<Addition>(board[1, 2], board[2, 2]).Set<Equal>(solver.FromConstant(1)); // Line for(int i=0;i<width;++i){ for(int j=0;j<height;++j){ if(i == 0 && j == 0) { board[i, j].Set<Equal>(solver.FromConstant(0)); ids[i, j] = solver.FromConstant(0); continue; } var isBlack = solver.Operation<IsEqual>(board[i, j], solver.FromConstant(0)); var isLowerCount = solver.FromConstant(0); if(i > 0) isLowerCount = isLowerCount.Operation<Addition>(solver.Operation<IsEqual>(board[i-1, j], solver.FromConstant(0)).Operation<Condition>(ids[i,j].Operation<IsGreaterThan>(ids[i-1,j]), solver.FromConstant(0))); if(i < width - 1) isLowerCount = isLowerCount.Operation<Addition>(solver.Operation<IsEqual>(board[i+1, j], solver.FromConstant(0)).Operation<Condition>(ids[i,j].Operation<IsGreaterThan>(ids[i+1,j]), solver.FromConstant(0))); if(j > 0) isLowerCount = isLowerCount.Operation<Addition>(solver.Operation<IsEqual>(board[i, j-1], solver.FromConstant(0)).Operation<Condition>(ids[i,j].Operation<IsGreaterThan>(ids[i,j-1]), solver.FromConstant(0))); if(j < height - 1) isLowerCount = isLowerCount.Operation<Addition>(solver.Operation<IsEqual>(board[i, j+1], solver.FromConstant(0)).Operation<Condition>(ids[i,j].Operation<IsGreaterThan>(ids[i,j+1]), solver.FromConstant(0))); solver.Set<Equal>( solver.FromConstant(1), solver.Operation<MaterialImplication>( isBlack, isLowerCount.Operation<IsEqual>(solver.FromConstant(1)) ) ); solver.Set<Equal>( solver.Operation<MaterialImplication>( isBlack.Operation<BinaryNegation>(), ids[i, j].Operation<IsEqual>(solver.FromConstant(0)) ), solver.FromConstant(1) ); } } var goal = solver.FromConstant(0); solver.Cplex.Populate(); Dictionary<string, int> solutions = new Dictionary<string, int>(); for(int x=0;x<solver.Cplex.GetSolnPoolNsolns();++x){ string result = ""; for(int j=0;j<height;++j){ for(int i=0;i<width;++i){ result += solver.Cplex.GetValue(((CplexVariable)board[i, j]).Var, x) > 0.5 ? 1 : 0; } result += "\n"; } if(solutions.ContainsKey(result)){ continue; } solutions[result] = 1; Console.WriteLine(result); } |

Let’s go line by line.

First, we start with definitions of variables. We define the board dimensions (lines 1-2), binaries representing the assignment of each field (line 4), and identifiers of the fields (line 5). Then, we initialize all the variables (lines 7-12).

First thing we need to tackle is how to cut the board in two pieces of the same shape. This is much easier than it seems. We can use the point reflection. Basically, we take a field of some coordinates, then find the matching field reflected by the middle of the board, and we make sure that these two fields belong to different pieces. So the sum of their values must be equal to one. This is in lines 14-19.

Next, we want to make sure that there is exactly one yin and one yang in a piece. So we sum values for yins, and make the sum equal to one. Same for yangs. This is in lines 21-23.

From now on we assume that value 0 means black field, and value 1 means white field.

Now, we need to craft the line going through the board. We assume that the top-left field is black. This assumption changes nothing, we could assume it’s white, and everything would work the same way.

Our idea is to assign identifiers to all black fields. Identifiers must increase in a BFS-like fashion. This is the same trick we used in many previous tasks. First step is to assign identifier zero to the top-left field – this is in lines 29-31.

Next, we iterate over all fields. For each field we check if it’s black (line 34), and then calculate how many black fields with lower identifiers are next to the current field (lines 35-39). Next, we need to make sure that if the current field is black, then there must be exactly one black neighbour with a lower identifier. This is in lines 41-47.

Finally, we make sure that white fields have identifier of 0. It doesn’t matter actually, but it’s a good idea to have this kind of hygiene. This is in lines 49-55.

Lastly, we need to remove duplicates. As the solver will find multiple solutions differing in the value of identifiers, we need to exclude them. We could do that by making sure identifiers increase by one, but at the same time we can remove these duplicates in a post-processing step. So we have a dictionary (line 62), and we iterate over all solutions (lines 64-79). For each solution, we first create its text representation (lines 66-70), and then ignore it if it’s a duplicate (lines 72-74). Otherwise, we store it (line 76), and print it (line 78).

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 99 100 |
Populate: phase I Tried aggregator 2 times. MIP Presolve eliminated 704 rows and 305 columns. MIP Presolve modified 1340 coefficients. Aggregator did 743 substitutions. Reduced MIP has 518 rows, 269 columns, and 1544 nonzeros. Reduced MIP has 246 binaries, 23 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (3.64 ticks) Probing fixed 33 vars, tightened 0 bounds. Probing changed sense of 44 constraints. Probing time = 0.00 sec. (2.28 ticks) Tried aggregator 1 time. MIP Presolve eliminated 197 rows and 115 columns. MIP Presolve modified 84 coefficients. Reduced MIP has 321 rows, 154 columns, and 924 nonzeros. Reduced MIP has 131 binaries, 23 generals, 0 SOSs, and 0 indicators. Presolve time = 0.00 sec. (0.91 ticks) Probing changed sense of 8 constraints. Probing time = 0.00 sec. (0.69 ticks) Tried aggregator 2 times. MIP Presolve eliminated 8 rows and 0 columns. MIP Presolve modified 8 coefficients. Aggregator did 8 substitutions. Reduced MIP has 305 rows, 146 columns, and 884 nonzeros. Reduced MIP has 123 binaries, 23 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (0.69 ticks) Probing time = 0.00 sec. (0.64 ticks) Clique table members: 621. 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.48 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 0 0 0.0000 20 0.0000 43 0 0 0.0000 37 Cuts: 58 77 0 0 0.0000 45 Cuts: 46 118 0 2 0.0000 45 0.0000 118 Elapsed time = 0.11 sec. (40.66 ticks, tree = 0.01 MB, solutions = 0) * 65+ 32 0.0000 0.0000 861 0.00% Clique cuts applied: 18 Cover cuts applied: 30 Implied bound cuts applied: 77 Zero-half cuts applied: 11 Root node processing (before b&c): Real time = 0.13 sec. (40.48 ticks) Parallel b&c, 8 threads: Real time = 0.06 sec. (11.05 ticks) Sync time (average) = 0.04 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 0.19 sec. (51.52 ticks) Populate: phase II MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 8 threads. Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap 112 37 infeasible 0.0000 0.0000 1148 0.00% Elapsed time = 0.20 sec. (51.87 ticks, tree = 0.02 MB, solutions = 1) Clique cuts applied: 18 Cover cuts applied: 30 Implied bound cuts applied: 77 Zero-half cuts applied: 11 Root node processing (before b&c): Real time = 0.05 sec. (9.66 ticks) Parallel b&c, 8 threads: Real time = 0.31 sec. (90.74 ticks) Sync time (average) = 0.05 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 0.36 sec. (100.40 ticks) 001111 011011 001001 000011 001111 000011 001111 000011 001111 001011 001011 000011 001111 011101 010001 000011 |