

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
you can!
Your solution receives a higher score as your number of squares decreases.
(archived
details,
developer pack,
README.txt,
zip,
legal)
This problem is known as
rectilinear polygon
decomposition (with holes).
Solving it optimally is NPcomplete, so what's sought here is a
heuristic
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.
Description
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
origin corner:
+> <+
 0 2  case 0: leftright, topdown
1 3 case 1: topdown, leftright
  case 2: rightleft, topdown
v v case 3: topdown, rightleft
^ ^ case 4: rightleft, bottomup
  case 5: bottomup, rightleft
7 5 case 6: leftright, bottomup
 6 4  case 7: bottomup, leftright
+> <+
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 topleft 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
candidate().
Implemented in 319 lines of C++ with no external dependencies.
Build with
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
greedy)
 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 depthfirst will produce
good results early.
 Pick first square in lexicographical order (leftright, topdown)
and maximize it. This produces surprisingly good results. Cheers to
Solomonoff's Secret
http://arstechnica.com/civis/viewtopic.php?p=28989393#p28989393
 Try other lexicographical orders, return the best result.
May 30th 2015, Daniel Hartmeier <daniel@benzedrine.ch>
Results
This is an example result with score 573 for a randomly generated N=100 puzzle:
Here are the
400 puzzles
I solved during the finals, and the
resulting scores.
Source code
Discussion
Academic papers
