ILP Part 93 — Squared Poland – Random IT Utensils

This is the ninetieth third 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 Polska kwadratowa. We have a map of Poland divided into unit squares. We need to cover the map with as few bigger squares as possible. Squares cannot intersect and there are some cities which cannot belong to any bigger square (they form a unit square on their own).

Solution:

var board = new []{
	"       XXX             ",
	"      XXXX#  XX        ",
	"   XXXXXXXXXXXXXXXXXX  ",
	" XXXXXXXXXXXXXXXXXXXXX ",
	" XXXXXXXXXXXXXXXXXXXXX ",
	" #XXXXXXXXXXXXXXXXXXXXX",
	"XXXXXXXXXXXXXXXXXXXXXXX",
	" XXXXXXXXXXXXXXXXXXXXXX",
	" XXXXXXXXXXXXXXXXXXXXX ",
	" XXXXX#XXXXXXXXX#XXXX  ",
	" XXXXXXXXXXXXXXXXXXXXX ",
	" XXXXXXXXXXX#XXXXXXXXX ",
	"  XXXXXXXXXXXXXXXXXXXX ",
	"  XXXXX#XXXXXXXXXXXXXX ",
	"  XXXXXXXXXXXXXXXXXXXXX",
	"    XXXXXXXXXXXXXXXXXXX",
	"     XXXXXXXXXXXXXXXXXX",
	"     X  XXXXX#XXXXXXXX ",
	"          XXXXXXXXXXX  ",
	"           XXXXXXXXXX  ",
	"             X     XX  "
};

var isValid = board.Select(row => row.Select(column => column != ' ').ToArray()).ToArray();

var howFar = board.Select(row => row.Select(column => 1).ToArray()).ToArray();

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[0].Length;++column){
		if(board[row][column] != 'X'){
			howFar[row][column] = 1;
			continue;
		}
		
		bool valid = true;
		for(int size=1;valid;++size){
			for(int y=0;y<size;++y){
				for(int x=0;x<size;++x){
					if(row+y >= board.Length){
						valid = false;
					}
					if(column + x >= board[0].Length){
						valid = false;
					}
					if(valid && !isValid[row+y][column+x]){
						valid = false;
					}
					if(valid && board[row+y][column+x] == '#'){
						valid = false;
					}
				}
			}
			
			if(valid){
				howFar[row][column] = size;
			}
		}
	}
}

var isTopLeft = board.Select(row => row.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();
var isDependent = board.Select(row => row.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();
var dependentIds = board.Select(row => row.Select(column => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray()).ToArray();
var rectangleSize = howFar.Select(row => row.Select(column => 
	solver.CreateAnonymous(Domain.PositiveOrZeroInteger)
		.Set<GreaterOrEqual>(solver.FromConstant(0))
		.Set<LessOrEqual>(solver.FromConstant(column)))
		.ToArray())
	.ToArray();
	

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[0].Length;++column){
		solver.Operation<Addition>(isTopLeft[row][column], isDependent[row][column]).Set<Equal>(solver.FromConstant(1));
					
		solver.Set<Equal>(
			solver.FromConstant(1),
			solver.Operation<MaterialImplication>(
				isDependent[row][column],
				rectangleSize[row][column].Operation<IsEqual>(solver.FromConstant(0))
			)
		);
		
		for(int y=0;y<howFar[row][column];++y){
			for(int x=0;x<howFar[row][column];++x){
				if(x == 0 && y == 0) continue;
				
				var isInShape = solver.FromConstant((int)Math.Max(x, y) + 1).Operation<IsLessOrEqual>(rectangleSize[row][column]);
				
				solver.Set<Equal>(
					solver.FromConstant(1),
					solver.Operation<MaterialImplication>(
						isInShape,
						isDependent[row+y][column+x].Operation<IsEqual>(solver.FromConstant(1))
					)
				);
				
				solver.Set<Equal>(
					solver.FromConstant(1),
					solver.Operation<MaterialImplication>(
						isInShape,
						dependentIds[row+y][column+x].Operation<IsEqual>(solver.FromConstant(row * board.Length + column))
					)
				);
			}
		}
	}
}

var goal = solver.FromConstant(0);
var area = solver.FromConstant(0);
for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[0].Length;++column){
		goal = goal.Operation<Addition>(isTopLeft[row][column]);
		area = area.Operation<Addition>(isTopLeft[row][column]
			.Operation<Multiplication>(rectangleSize[row][column])
			.Operation<Multiplication>(rectangleSize[row][column])
		);
	}
}
area.Set<Equal>(solver.FromConstant(board.Length * board[0].Length));

goal = goal.Operation<Negation>();
solver.AddGoal("g", goal);
solver.Solve();

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[0].Length;++column){
		if(board[row][column] == '#'){
			Console.Write('#');
		} else if(board[row][column] == ' '){
			Console.Write(' ');
		} else if(solver.GetValue(isTopLeft[row][column]) > 0.5){
			Console.Write('T');
		} else if(solver.GetValue(isDependent[row][column]) > 0.5){
			Console.Write('d');
		} else {
			Console.Write('?');
		}
	}
	
	Console.WriteLine();
}
Console.WriteLine();

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

var board = new []{

" XXX ",

" XXXX# XX ",

" XXXXXXXXXXXXXXXXXX ",

" XXXXXXXXXXXXXXXXXXXXX ",

" #XXXXXXXXXXXXXXXXXXXXX",

"XXXXXXXXXXXXXXXXXXXXXXX",

" XXXXXXXXXXXXXXXXXXXXXX",

" XXXXXXXXXXXXXXXXXXXXX ",

" XXXXX#XXXXXXXXX#XXXX ",

" XXXXXXXXXXXXXXXXXXXXX ",

" XXXXXXXXXXX#XXXXXXXXX ",

" XXXXXXXXXXXXXXXXXXXX ",

" XXXXX#XXXXXXXXXXXXXX ",

" XXXXXXXXXXXXXXXXXXXXX",

" XXXXXXXXXXXXXXXXXXX",

" XXXXXXXXXXXXXXXXXX",

" X XXXXX#XXXXXXXX ",

" XXXXXXXXXXX ",

" XXXXXXXXXX ",

" X XX "

};

var isValid = board.Select(row => row.Select(column => column != ' ').ToArray()).ToArray();

var howFar = board.Select(row => row.Select(column => 1).ToArray()).ToArray();

for(int row=0;row<board.Length;++row){

for(int column=0;column<board[0].Length;++column){

if(board[row][column] != 'X'){

howFar[row][column] = 1;

continue;

}

bool valid = true;

for(int size=1;valid;++size){

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

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

if(row+y >= board.Length){

valid = false;

}

if(column + x >= board[0].Length){

valid = false;

}

if(valid && !isValid[row+y][column+x]){

valid = false;

}

if(valid && board[row+y][column+x] == '#'){

valid = false;

}

if(valid){

howFar[row][column] = size;

}

var isTopLeft = board.Select(row => row.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();

var isDependent = board.Select(row => row.Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()).ToArray();

var dependentIds = board.Select(row => row.Select(column => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray()).ToArray();

var rectangleSize = howFar.Select(row => row.Select(column =>

solver.CreateAnonymous(Domain.PositiveOrZeroInteger)

.Set<GreaterOrEqual>(solver.FromConstant(0))

.Set<LessOrEqual>(solver.FromConstant(column)))

.ToArray())

.ToArray();

for(int row=0;row<board.Length;++row){

for(int column=0;column<board[0].Length;++column){

solver.Operation<Addition>(isTopLeft[row][column], isDependent[row][column]).Set<Equal>(solver.FromConstant(1));

solver.Set<Equal>(

solver.FromConstant(1),

solver.Operation<MaterialImplication>(

isDependent[row][column],

rectangleSize[row][column].Operation<IsEqual>(solver.FromConstant(0))

)

);

for(int y=0;y<howFar[row][column];++y){

for(int x=0;x<howFar[row][column];++x){

if(x == 0 && y == 0) continue;

var isInShape = solver.FromConstant((int)Math.Max(x, y) + 1).Operation<IsLessOrEqual>(rectangleSize[row][column]);

solver.Set<Equal>(

solver.FromConstant(1),

solver.Operation<MaterialImplication>(

isInShape,

isDependent[row+y][column+x].Operation<IsEqual>(solver.FromConstant(1))

)

);

solver.Set<Equal>(

solver.FromConstant(1),

solver.Operation<MaterialImplication>(

isInShape,

dependentIds[row+y][column+x].Operation<IsEqual>(solver.FromConstant(row * board.Length + column))

)

);

}

var goal = solver.FromConstant(0);

var area = solver.FromConstant(0);

for(int row=0;row<board.Length;++row){

for(int column=0;column<board[0].Length;++column){

goal = goal.Operation<Addition>(isTopLeft[row][column]);

area = area.Operation<Addition>(isTopLeft[row][column]

.Operation<Multiplication>(rectangleSize[row][column])

);

}

area.Set<Equal>(solver.FromConstant(board.Length * board[0].Length));

goal = goal.Operation<Negation>();

solver.AddGoal("g", goal);

solver.Solve();

for(int row=0;row<board.Length;++row){

for(int column=0;column<board[0].Length;++column){

if(board[row][column] == '#'){

Console.Write('#');

} else if(board[row][column] == ' '){

Console.Write(' ');

} else if(solver.GetValue(isTopLeft[row][column]) > 0.5){

Console.Write('T');

} else if(solver.GetValue(isDependent[row][column]) > 0.5){

Console.Write('d');

} else {

Console.Write('?');

}

Console.WriteLine();

}

Console.WriteLine();

First, we define a board in lines 1-23. Space indicates an empty cell, capital X indicates a free unit square. Hash # indicates a city which can’t belong to any other big square.

We first calculate which fields are valid, e.g., they belong to the country and are free to be covered with a bigger square. That’s in line 25.

Now, the general idea is that for each cell we define whether it’s a top-left corner of some square and how big the square is. To calculate that we need to first precalculate the size of a biggest square we can start in a given cell. We do that in lines 27-60. What we do is we start from some cell and then try to extend it to the right and to the bottom as far as possible.

Now, we start defining variables. First, indicators whether a given cell is a top-left corner of a square (line 62) or if it’s a part of some other square (so it’s dependent) in line 63. Next, we define the id of the square the cell belongs to (line 64) and the square size (lines 65-70).

And now comes the heart of the algorithm. We iterate over all cells and make sure that a cell is either a top-left corner or is dependent (line 75). Notice that cells outside of the country will be considered a top-left ones (this makes the algorithm a little easier).

Next, if a cell is dependent then the size of the square starting in this cell must be zero (as there is no square) – lines 77-83.

And now we iterate over a square starting in this cell (from line 85). We try to move right and down (hence x and y in lines 85 and 86). We check if given cell can be a part of the square — that’s the case if it’s not further away then the maximum possible square size starting in the top left cell (line 89) and if its less or equal to the actual size of the square we want to build start from the given cell. If that’s the case then we mark the other cell as dependent (lines 91-97).

It seems like that should be enough. However, with such an approach the solver would make all cells dependent and call it a day. So we need to actually make sure that the map is covered. In lines 111-122 we take all top-left corners and calculate the area they cover (based on the square size started from such a cell). Next, we minimize the number of top-left corners as we want to have as few squares as possible (line 124-125).

However, that’s not enough as we don’t disallow for intersecting squares. That’s why we need to keep a track of ownership of each dependent cell. We basically add an id of a top-left corner owning the cell to the cell (lines 99-105).

That’s it.