17x17: More about symmetry and a new rotation

This is part of a series of posts is related to the " 17x17 Challenge" posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.

In my last post, I gave a symmetrical rotation of the known 74-cell single-coloring. I want to use a slight variation of that grid to show why I think treating the grids as symmetrical will help us in solving this problem.

Here is a new spreadsheet, with several panes you can click through on the bottom. Panes ONE through FIVE represent the first few rows of a single- coloring in which we avoid making any real choices, thanks to a few assumptions we make (I’ll come back to that).

Orange represents the row we’re coloring, gray cells are rectangle forming cells (in which marks are not allowed), and blue cells represent what I consider to be the real search-space:

TODO: insert google doc iframe

NOTE: We’re simply using another automorphism of the original 74-coloring, i.e. a series of rotations that preserve all the significant attributes of the graph.

Making Coloring Decisions

We can choose, arbitrarily, to start with a 5-cell row starting on the cell in the upper left. This is our first decision: if it were that in an optimal single-coloring of 17x17 no row with five colored cells shared a cell with any column with five colored cells, then we would have made a poor decision.

But given that in the 74-coloring that we have, all 5-colored-cell rows share a cell with a 5-colored column, we can probably assume that at least one will in our optimal single-coloring. So our first row (in pane 1) is a non- decision.

We continue with the second row by dumping 3 cells as soon as we can (i.e. as far to the left as possible. The only decision made here is in whether to make row two a row of four or five. But as we can see very quickly (and as a shallow search algorithm would see very quickly), making row 2 a five-colored- cell row would force us into forming a 3-cell row out of row five.

So in row 2 we have an easy decision (seeing that we would soon regret creating a 5-cell row) based on our assumption that a good singly-colored grid will have its cells spread evenly over rows & columns.

And we have the non-decision of the column placement of those three cells: because identical columns (in this case empty columns) can be freely swapped without changing anything, there is no need to try every combination of column placement for the row. We put off our decision making for later.

We continue on in the same way.

Search Ideas

I’m coding up a program to try to generate good grids based on some heuristics. I think that a minimax type solution might be good: in which the coloring of a cell is assigned a point-value based on how many future cells it makes unusable. I could then keep track of which previous cells were complicit in forming potential rectangles and back-track at apparently-bad decisions: i.e. hilll climbing.

I may try to formulate the algorithm like a game and see if I can use the game-tree module by Colin Adams.

Conclusion

It seems to me that the key to the problem of a single-coloring is shrinking the search-space by eliminating false-choices. Treating the graph as it’s symmetrical (by our definition of symmetrical) automorphism is one way: suddenly the search space becomes the shaded area in the graph above.

Thankfully, my next post will be haskell-related and have nothing to do with Grids.