I’ve been making notes when I have time, on the “17 x 17 challenge” posted a couple months back by Bill Gasarch. I’ve been sketching out algorithms for the problem and wanted to quickly produce some optimal rectangle free subsets to check my work and look at. So the code below answers the following question:
Imagine an n x n grid. You can color cells of the grid such that no rectangle overlayed on the grid will have all four corners colored. Find a grid with the maximum possible colored cells.
So this is a quick and stupid brute force algorithm, but it let me see an optimal 6grid, which is what I needed. First out imports:
1 2 3 

We’ll call a colored cell True
, uncolored False
:
1 2 

Given the side length, we’ll spit out all the possible ways a row can be colored:
1 2 

A quick function to see if two rows form a rectangle:
1 2 

An ugly function to return all the nlength ordered subsets of the ordered set of rows. (Note: a grid can move about its columns and rows without changing itself fundamentally, which is why we do the extra effort to not return every nlength permutation of the rows):
1 2 3 4 5 6 7 8 

Validate a grid by making sure each pair is rectangle free with every other…
1 2 3 

…and tie it all together:
1 2 

So a best subset of size four looks like:
[[True,True,False,False],[True,False,True,False],[True,False,False,True],[False,True,True,True]]
And a pretty picture:
+++++
XXXX  
+++++
XX XX 
+++++
XX  XX
+++++
 XXXXXX
+++++
Does anyone have a more elegant way to represent the allGrids
function? In
the general sense it finds all nlength ordered subsets of an ordered set when
the length of the set is known.