17x17: Some Thoughts on the Problem

I’ve been puzzling over some of the problems presented by the 17 x 17 Challenge, and wanted to share some of what I’ve learned and have been wondering about. The problem and ultimate goal is to color a 17 x 17 grid with four colors such that every cell is colored and no rectangle is formed by any four cells of the same color.

Single-Color Subsets

I’ve started by trying to find an algorithm to find optimal single-color subsets, i.e. a way of coloring a grid with one color such that no rectangle is formed by the colored cells, and we have the greatest number of cells colored as possible. I started thinking of coloring cells one at a time, following a path based on the notion of an “extended rectangle” where the fourth side was longer or shorter than the first, to avoid forming rectangles.

I also noticed that we could traverse all the cells in the largest known 17x17 subset by following a simple spiraling algorithm. It didn’t seem to matter which cell or direction we started in either:

This led to a simple algorithm that does well in finding pretty good subsets, but doesn’t find optimal subsets for the larger grids (at least it couldn’t find a grid of size 74, linked above). The algorithm is something like “wagging the dog”, and it’s surprising that it works as well as it does. I wonder whether the sub-problem of optimal single-colorings has applications to knot theory.

Optimal Grids

I generated some optimally-colored grids to see if they all followed this property of being traversable via this “rotation” algorithm above. It turns out that some directions and starting points loop before they touch every colored cell. I suspect that will also be the case for the 74-color grid above.

Here are the grids I was able to generate via brute force:

Notice that, as you might guess, colored cells are spread out as evenly as possible among rows and columns (i.e. no two rows differ by more than one in their number of colored cells).

…and Symmetry and Rotations

Also notice the diagonal symmetry that all of the grids exhibit. The 5x5 grid was not symmetrical when it came out of my brute force algorithm, but I was happy to see that I could turn it into the above symmetrical version with a few rotations (a fun puzzle by the way). The symmetry reminds me of creating/solving sudoku and I wonder if this is a similar constraint-solving problem.

It would be interesting to see if the 17x17 grid was symmetrical in one of its possible rotations. I would like to look into that as well as code up a symmetrical variation of the algorithm I described in my last post. If all optimal subsets were symmetrical, that could make the search-space considerably smaller.

I also wonder whether all subsets of the same size are not simply rotations of the others. This seems to be the case for the smaller optimal subsets in the image above.

Four-Coloring the 17x17 Grid

The author suggests that a 17x17 grid is an edge case, meaning that it may or may not be possible to four-color. A single-coloring of at least 73 must be possible in order for a four-coloring to be possible: 73 + 72 + 72 + 72 = 289 = 17 x 17. The author of the challenge has found one of size 74.

Given the difficulty of finding a single-coloring (74 colors seems to be the largest known), we can perhaps assume that each of the four single-color subsets will be evenly distributed with 4 or 5 cells per row/column.

Thus every row of a successful four coloring will have 4 + 4 + 4 + 5 = 17 in each of the four colors respectively.

There are 2380 possible unique 17-length rows with four colored cells in the row. There are 6188 with 5 colored. Here’s the code I used for that fun fact:

-- finding promising rows:  
allRowsSize sz n
    | sz == n = [ replicate n True ]
    | n == 0 = [ replicate sz False ]
    | otherwise =
        [ True:as | as <- allRowsSize (sz-1) (n-1) ] ++ 
        [ False:as | as <- allRowsSize (sz-1) n ]

Going Forward

If the couple ideas I still have for an optimal single-coloring don’t work out, it may be interesting to try to “deconstruct” the known 74-coloring, treating it like the algorithm I developed in my last post, but in reverse, noticing the “choices” made.

After giving up on a deterministic single-coloring algorithm it might be interesting to investigate some kind of ladder climbing algorithm that looks at trying to consolidate rectangle-forming squares.

Finally, an approach that might have been the easiest all along, would be to take the author’s 74-coloring above and try to generate 4 different permutations of sizes 73 and 72 that could fit together. We don’t learn too much from that though.

I’m really interested to know your thoughts on the problem as well. So leave a comment if you like!