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:

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 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 ", " #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(); |

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.