I finally got some time to code up a messy script to test out a few
variations of an algorithm to generate rectangle-free single colorings of a
grid, as part of a lazy humble effort to solve the
17 x 17 challenge.
This post is going to be a bit of a code-dump. The algorithm is essentially:
color cell,
turn to the right,
stop on first non-rectangle forming cell,
if the cell is uncolored, color it and turn to the right, else if the cell was already colored and has been entered from this direction already, then skip it, else turn to the right
I’m not sure if an algorithm exists yet to find rectangle free colorings. The authors of the challenge seem to know of no optimal deterministic algorithm.
The code below produces a rectangle-free subset of 68 colored cells on a 17x17
grid. Apparently the largest known subset
is 73
74 (important because 4 subsets of length 73 or 72 one subset of
size 73 and three of size 72 would fill a 17x17 grid if they could be made to
fit together). So hopefully one of the variations of the algorithm above that
I have in mind will be able to match or beat that.
We don’t yet have logic for stopping once a row or column is exhausted, so it will just hang:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
|