![[benzedrine.ch logo]](/logo.jpg){kind=logo} |
|
|
|
Partitioning orthogonal polygons into squaresThe 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.
This problem is known as
rectilinear polygon
decomposition (with holes). 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 <[email protected]>
ResultsThis 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
|
![[How efficiently can you cover a grid like this with squares?]](cimpress-ask.png)
![[Cimpress Tech Challenge random N=100 puzzle solution]](cimpress-573.png)