This article is for the method I, Mladen Dobrichev, used in Hexagonal Neighbors contest. See the references at the end of this page for the methods of other contestants.
The method I used in one sentence:
Improve valid boards by reducing to "1" all cells that directly or not depend on particular cell "1", then improve by repeatedly dragging smaller values "forward" to periphery, CCW, then "backward" to center, CW.
For each board size I started from infinite ideal pattern.
Then applied patches for the borders. Due to the symmetry of the ideal pattern, patches are value substitutions for the border 2 rows at each of the 6 sides.
Initially I started from random infinite pattern, then switched to one with 567 loops in triangle which gave better initial results.
The corner 3x3 cells were patched finally by brute force resulting in several non-isomorphic initial valid boards for each board size.
Then I repeatedly applied batches of reduction -> improvement cycles in a manner close to breadth-first search.
For cells I used clockwise inward spiral coordinate system, starting from a corner and ending to the central cell.
From various reduction methods, I found that those that clear particular patterns (by setting cell values to 0 = unknown) almost don't work.
The working reduction methods are few modifications of "take a cell with value 1, trace all cells that directly or indirectly depend on it, and set them all to 1".
After such reduction the board remains valid.
The best working board improvement method does possible exchanges of a cell with one of its 18 neighbors at distance 1 or 2 and immediately improves the changed cells if possible.
The tricky part is that at one "forward" pass the smaller values selectively are dragged to the cells with smaller coordinate (to periphery and counter clockwise).
On the next "backward" pass smaller values are dragged in opposite direction (to center and clockwise). Imagine cyclone and anticyclone.
At some point board is compared to its rotated and mirrored 11 other representations and the lexicographically minimal is chosen.
Process repeats until the last pass resulted in a board from previous passes (yes, sometimes non-trivial loops occur). The so collected boards originating from a single source board I consider "morphs" and only lexicographically smallest from them is stored for further processing.
I assumed that several passes in dragging the cells, each pass in opposite direction, will cause sufficient slip, allowing single-cell upgrades and respectively reducing the penalties.
Finally I replaced all 567 chains/loops with their predefined canonical values sequence, and try to join 'lone 5' cells to the neighbor 567 chains/loops by applying a bit more complicated logic.
The result of the improvement is considered canonical form of the board and is stored in a dictionary.
Processed boards are tagged. Reasonable amount of boards per score is between 200 and 2000, rarely up to 100 000 for smaller boards.
Note that the improvement method doesn't guarantee that even the original board is reproduced. Each pass only guarantees that on exit score is same or improved, but the entry score is the highly reduced compared to the original.
The improvement process strongly depends on the firstly executed pass, so that the work is duplicated, once starting by "forward" pass, once by "backward".
It is vital not to mishandle the process being tempted doing deep-first search, especially on the early stages.
My rule was to continue improving boards scored N until sufficient boards scored N + 1 are collected.
The batch collects all untagged (not already processed by particular improvement technique) boards of the given score, randomly shuffles them, and starts processing.
The improvements are logged and can be monitored, and it is safe to stop the batch at any time (Ctrl-C handler).
My unproven explanation why this method works is
- the reduced area in general is orthogonal to the 567 chains, and enforced slipping gives sufficient chance for chains to recombine.
- the improvement isn't limited to particular board area. The whole board can recrystallize.
Variations of reduction methods include limitation of how deep from periphery to get "root" cells for reduction, different assumptions what exactly root cell and dependent cells are, whether to shuffle the board performing random validity preserving cell exchanges before the reduction, etc.
As expected, the larger the cleared area is, the lesser are chances for improvement or even reproduction of the original board, but the larger are chances for escaping local maximum.
I worked with tuples, a central cell with its direct neighbors, and used large lookups like
- 173506 valid 7-cells "interior" tuples, including penalty (measured in half-penalties to prevent duplicate counting by adjacent tuple), strong link directions to center, etc.
- 1950 valid 5-cells "border" tuples (x6 if rotated),
- 265 valid 4-cells "corner" tuples (x6 if rotated),
- 36715 valid 7-cells tuples that are valid to be placed on a corner,
- 74382 valid 7-cells tuples that are valid to be placed on a border,
- 1 gigabyte 7-dimensional array where the array indexes are tuple cell values (0 = unknown, 1 to 7) for all 7 cells of the board. Each value is a list of all valid tuples, ordered by penalty and with precalculated count of tuples with 0 penalty. Most lists are empty of course, and those for all non-zero indexes are of size 1.
- similar smaller arrays for 5-cells borders and 4-cells corners.
I wrote 2 brute force solvers.
The first is entirely based on tuples and allows solving subgrids (doesn't care what happens with unpopulated cells outside the area of interest).
The second uses tuples and pencilmarks (per cell bitmaps of allowed values). It also allows pencilmarks as input (some fixed cells/layers + fixed 567 chain cell positions but not their values + unknown values).
I am not satisfied by any of the solvers.
I found the penalties concept early, but the fact that rules enforce all 567 cells to degrade to chains/loops was hidden for me until 2-3 weeks before the end.
My final score is 24.96.
References
Al Zimmermann's Programming Contests - Hexagonal Neighbors - the contest page.
Al Zimmermann's Programming Contests - Discussion Group - the official discussion group on Yahoo.
Tomas Sirgedas, 25.0000 pts, 1st place.
Tomas Rokicki, 25.0000 pts, 2nd place - an excellent writeup of the methods used. Defines terms "Penalty", "Layer", etc.
Walter Trump, 24.9679 pts - a manual approach with pictures.
Herbert Kociemba, 24.9194 pts - alternative definition for penalties.
Mikhail Markeyev, 24.7637 pts - regular tiling patterns.
Visualizations of the solutions - a zip file by Johan Claes, 24.8967 pts.
Dominating set - Wikipedia - pointed by Gil Dogon, 24.9163 pts.