Partitioning orthogonal polygons into squares
The Cimpress Tech Challenge 2015 asked:
Your challenge is to write a program that begins with an incomplete grid
and covers it exactly with squares of any sizes.
Cover it with as few squares as you can, and solve each puzzle as fast as
Your solution receives a higher score as your number of squares decreases.
This problem is known as
decomposition (with holes).
Solving it optimally is NP-complete, so what's sought here is a
for sizes up to N=100 which runs in less than ten seconds.
Submitted May 30th 2015, results will be announced around June 22nd 2015.
This program randomly tries to place squares as large as possible in
positions close to the corners of the grid.
The candidate() function searches the grid for the first uncovered cell
in one of eight lexicographical orders, starting from the respective
| 0 2 | case 0: left-right, top-down
|1 3| case 1: top-down, left-right
| | case 2: right-left, top-down
v v case 3: top-down, right-left
^ ^ case 4: right-left, bottom-up
| | case 5: bottom-up, right-left
|7 5| case 6: left-right, bottom-up
| 6 4 | case 7: bottom-up, left-right
The single cell forms a square of size one. The square size is then
enlarged, one by one, in the direction of the lexicographical order, as
long as no obstacle is encountered.
The function returns this maximal square, expressed as top-left corner
(independent of lexicographical order) and size.
The solve() function starts with the initial grid and repeatedly calls
candidate() with a random (!) lexicographical order and covers the
returned square until all cells are covered.
The entire process is repeated as long as the time limit is not reached,
and the best solution seen (minimum number of squares) is returned.
Grid::mark caches the last search position over multiple calls to
Implemented in 319 lines of C++ with no external dependencies.
g++ -O3 -o program program.cpp
Comparing the scores for 400 puzzles in contest mode for the starter
set (x) with this program (*)
N Min Max Median Avg Stddev
x 400 356 1484 805 839.5075 245.22293
+ 400 39 178 100 98.3525 29.069241
Difference at 95.0% confidence
-741.155 +/- 24.2001
-88.2845% +/- 2.88266%
(Student's t, pooled s = 174.613)
Things I tried which didn't work out so well:
- Simple quadtree
- Always pick the largest free square from the entire grid (strictly
- For the first three picks, try all combinations of the best ten
choices each step, then finish greedy. Except for small grids, this
will exceed the time limit, but doing it depth-first will produce
good results early.
- Pick first square in lexicographical order (left-right, top-down)
and maximize it. This produces surprisingly good results. Cheers to
- Try other lexicographical orders, return the best result.
May 30th 2015, Daniel Hartmeier <email@example.com>
This is an example result with score 573 for a randomly generated N=100 puzzle:
Here are the
I solved during the finals, and the