Partitioning orthogonal polygons into squares

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 NP-complete, 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: 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
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 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
    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

Here are the 400 puzzles I solved during the finals, and the resulting scores.

Source code

• cimpress2015.cpp source code as submitted in contest
  

Discussion

• $10k Tech Challenge by Cimpress discussion on reddit.com
  
• Algorithmic Challenge From Cimpress article by Lucy Black on i-programmer.info
  
• while (true) { discussion on arstechnica.com forum (scroll down and see subsequent pages)
  
• Least Squares problem on UVa Online Judge
  
• Tiling an orthogonal polygon with squares on stackexchange.com
  

Academic papers

• Covering orthogonal polygons with squares Larry J. Aupperle, Harold E. Conn, J. Mark Keil, Joseph O'Rourke, 1988
  
• Polygon Decomposition by J. Mark Keil, 1996
  
• Decomposing and packing polygons Dania El-Khechen, 2009
  
• Rectangular Decomposition of Binary Images Tomas Suk, Cyril Hoeschl, Jan Flusser, 2012