[benzedrine.ch logo]
Contents
Home
Daniel Hartmeier
Packet Filter
pfstat
Mailing list
Annoying spammers
Prioritizing ACKs
Transparent squid
Proxy ICB/IRC
milter-regex
milter-spamd
milter-checkrcpt
login_yubikey
Dorabella
Tron
Planet Wars
Hexiom solver
3D-ODRPP
Polygon partition
Mikero's grid puzzle
Dark Star
Misc
Statistics


Partitioning orthogonal polygons into squares

The Cimpress Tech Challenge 2015 asked:

[How efficiently can you cover a grid like this with 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

This is an example result with score 573 for a randomly generated N=100 puzzle:

[Cimpress Tech Challenge random N=100 puzzle solution]

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

Source code

Discussion

Academic papers

Last updated on Sat Jun 13 09:13:46 2015 by daniel@benzedrine.ch.