ILP Part 89 — Poles – Random IT Utensils

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:

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));
}

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:

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

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