17x17: Some Attempts at Doubly-Symmetrical Rotations

Note: 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 a previous post I presented rotations of some single-color rectangle-free grids which were symmetrical along a diagonal axis. I also noticed that, of the single-colorings of optimal size which I could generate, all with an odd number side-length could be made symmetrical along both diagonals (the evens could not):

TODO: insert google doc iframe

Perhaps all odd-sided optimal single-colorings are doubly-symmetrical in one of their rotations! That would be a cool thing to learn, and it would also mean that if we wanted to generate an optimal coloring, then our search space would be roughly 1/4 of the grid.

So I thought I would see if I could rotate the known 74-color grid into a doubly-symmetrical arrangement… and I have to admit defeat.:

TODO: insert google doc iframe

The orange squares mark discrepancies I couldn’t resolve. It could be that it is true that all optimal (having the greatest number of colored cells possible for the grid size) single colorings can be made doubly symmetrical and that the 74 colors in 17x17 grid is less than optimal. It could also mean I suck at moving rows and columns around in google spreadsheet. Either way, I’m done with this line of investigation for now.

Next I would like to jump into actually trying to generate 4-colorings of 17x17, using some informed search algorithms and ladder climbing techniques.