ILP Part 86 — Skyscrapers – Random IT Utensils

This is the eightieth sixth 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 a modification of Skyscrapers riddle.

In regular Skyscrapers we have a square board with some skyscrapers on it where all skyscrapers in a given line have different heights. We do have numbers along the board which indicate how many buildings are visible from a given side. In modified version numbers indicate how many blocks are visible.

Also, one number in the initial input is not needed to find the solution as there is only one. Our goal is to find which number it is.

Code:

int size = 4;
var board = Enumerable.Range(0, size).Select(w => Enumerable.Range(0, size).Select(h => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<GreaterOrEqual>(solver.FromConstant(1)).Set<LessOrEqual>(solver.FromConstant(size))).ToArray()).ToArray();

// Make them different heights
for(int i=0;i<size;++i){
	solver.Set<AllDifferent>(board[i][0], new []{board[i][1], board[i][2], board[i][3]});
	solver.Set<AllDifferent>(board[0][i], new []{board[1][i], board[2][i], board[3][i]});
}

// Helper function for calculating sums
Func<IVariable[], IVariable> makeGreater = line => {
	IVariable sum = solver.FromConstant(0);
	for(int i=0;i<line.Length;++i){
		IVariable heights = solver.FromConstant(1);
		
		for(int j=0;j<i;++j){
			heights = heights.Operation<Conjunction>(line[i].Operation<IsGreaterThan>(line[j]));
		}
		
		sum = sum.Operation<Addition>(heights.Operation<Condition>(line[i], solver.FromConstant(0)));
	}
	
	return sum;
};

makeGreater(new []{board[3][0], board[3][1], board[3][2], board[3][3]}).Set<Equal>(solver.FromConstant(7));
makeGreater(new []{board[3][3], board[2][3], board[1][3], board[0][3]}).Set<Equal>(solver.FromConstant(4));
makeGreater(new []{board[1][3], board[1][2], board[1][1], board[1][0]}).Set<Equal>(solver.FromConstant(9));
makeGreater(new []{board[0][2], board[1][2], board[2][2], board[3][2]}).Set<Equal>(solver.FromConstant(7));

solver.AddGoal("g", solver.FromConstant(0));
solver.Solve();

for(int i=0;i<size;++i){
	for(int j=0;j<size;++j){
		Console.Write((int)solver.GetValue(board[j][i]));
	}
	Console.WriteLine();
}
Console.WriteLine();

int size = 4;

var board = Enumerable.Range(0, size).Select(w => Enumerable.Range(0, size).Select(h => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<GreaterOrEqual>(solver.FromConstant(1)).Set<LessOrEqual>(solver.FromConstant(size))).ToArray()).ToArray();

// Make them different heights

for(int i=0;i<size;++i){

solver.Set<AllDifferent>(board[i][0], new []{board[i][1], board[i][2], board[i][3]});

solver.Set<AllDifferent>(board[0][i], new []{board[1][i], board[2][i], board[3][i]});

}

// Helper function for calculating sums

Func<IVariable[], IVariable> makeGreater = line => {

IVariable sum = solver.FromConstant(0);

for(int i=0;i<line.Length;++i){

IVariable heights = solver.FromConstant(1);

for(int j=0;j<i;++j){

heights = heights.Operation<Conjunction>(line[i].Operation<IsGreaterThan>(line[j]));

}

sum = sum.Operation<Addition>(heights.Operation<Condition>(line[i], solver.FromConstant(0)));

}

return sum;

};

makeGreater(new []{board[3][0], board[3][1], board[3][2], board[3][3]}).Set<Equal>(solver.FromConstant(7));

makeGreater(new []{board[3][3], board[2][3], board[1][3], board[0][3]}).Set<Equal>(solver.FromConstant(4));

makeGreater(new []{board[1][3], board[1][2], board[1][1], board[1][0]}).Set<Equal>(solver.FromConstant(9));

makeGreater(new []{board[0][2], board[1][2], board[2][2], board[3][2]}).Set<Equal>(solver.FromConstant(7));

solver.AddGoal("g", solver.FromConstant(0));

solver.Solve();

for(int i=0;i<size;++i){

for(int j=0;j<size;++j){

Console.Write((int)solver.GetValue(board[j][i]));

}

Console.WriteLine();

}

Console.WriteLine();

This should be pretty straightforward. First, we make sure that skyscrapers have different heights. Next, we create a helper function to sum visible blocks. We compare given skyscraper with all before it in the line, check if it’s higher and then include its height or not.

Now, the output:

Tried aggregator 2 times.
MIP Presolve eliminated 211 rows and 96 columns.
MIP Presolve modified 816 coefficients.
Aggregator did 93 substitutions.
Reduced MIP has 450 rows, 211 columns, and 1332 nonzeros.
Reduced MIP has 177 binaries, 34 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.26 sec. (2.18 ticks)
Found incumbent of value 0.000000 after 0.36 sec. (4.11 ticks)

Root node processing (before b&c):
  Real time             =    0.41 sec. (4.13 ticks)
Sequential b&c:
  Real time             =    0.00 sec. (0.00 ticks)
                          ------------
Total (root+branch&cut) =    0.41 sec. (4.13 ticks)
2413
4321
3142
1234

Tried aggregator 2 times.

MIP Presolve eliminated 211 rows and 96 columns.

MIP Presolve modified 816 coefficients.

Aggregator did 93 substitutions.

Reduced MIP has 450 rows, 211 columns, and 1332 nonzeros.

Reduced MIP has 177 binaries, 34 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.26 sec. (2.18 ticks)

Found incumbent of value 0.000000 after 0.36 sec. (4.11 ticks)

Root node processing (before b&c):

Real time = 0.41 sec. (4.13 ticks)

Sequential b&c:

Real time = 0.00 sec. (0.00 ticks)

------------

Total (root+branch&cut) = 0.41 sec. (4.13 ticks)

2413

4321

3142

1234

We can now comment out numbers one by one and find that top 7 is redundant.