I've made no secret of my obsession with the 17x17 challenge. I started working on it in November 2009 and went straight at it for six months. At that point I had to stop to code/write up my PhD but started working on it again as soon as I was done. This problem has given me a reason to learn so many amazing things in both math and programming, that I would be happy to have worked on it even if I never produced anything worthwhile. It's now a weekend project given that I run a startup, but, after almost 2 years, I have something to show the world: A grid with 3 rectangles.
To be clear, this is not a solution. It would need to have 0 rectangles to be a solution. But it is the least broken solution I know of. Bill Gasarch posted with the problem a 4-rectangle grid by Rohan Puttagunta, but this has not been improved on since. Here is a leader board of the best grids known so far.
This solution is less impressive than that one in that it's missing two cells rather than one, but it does have fewer rectangles when extended to a full colouring, which is what makes it interesting. Without further ado, the solution, with the rectangles marked out:
If anyone has code they want to use to analyse this, here it is again in a machine-friendlier format:
To be clear, this is not a solution. It would need to have 0 rectangles to be a solution. But it is the least broken solution I know of. Bill Gasarch posted with the problem a 4-rectangle grid by Rohan Puttagunta, but this has not been improved on since. Here is a leader board of the best grids known so far.
This solution is less impressive than that one in that it's missing two cells rather than one, but it does have fewer rectangles when extended to a full colouring, which is what makes it interesting. Without further ado, the solution, with the rectangles marked out:
If anyone has code they want to use to analyse this, here it is again in a machine-friendlier format:
4,2,1,3,1,2,3,4,4,1,2,4,2,1,4,3,3
2,4,2,1,3,2,1,4,1,4,1,2,4,3,3,4,3
1,2,4,1,3,1,3,4,3,1,4,2,3,4,2,2,4
3,1,1,4,3,1,4,3,4,2,3,2,2,4,1,4,2
1,3,3,3,3,3,4,2,2,4,1,4,2,1,1,2,4
2,2,1,1,3,4,4,1,2,3,4,3,4,2,4,3,1
3,1,3,4,4,4,3,4,1,1,2,3,1,2,3,2,2
4,4,4,3,2,1,4,3,3,3,1,2,1,2,3,1,1
4,1,3,4,2,2,1,3,2,4,4,1,3,1,2,3,1
1,4,1,2,4,3,1,3,4,1,4,3,2,2,2,1,3
2,1,4,3,1,4,2,1,4,4,3,3,3,3,2,1,2
4,2,2,2,4,3,3,2,1,3,3,1,4,4,1,1,2
2,4,3,2,2,4,1,1,3,2,3,4,1,4,1,2,3
1,3,4,4,1,2,2,2,1,2,3,4,4,2,3,3,1
4,3,2,1,1,4,3,3,2,2,2,1,1,3,2,4,4
3,4,2,4,2,3,2,1,3,1,1,1,2,3,4,3,4
3,3,4,2,4,1,2,1,1,3,2,2,3,1,4,4,3
In case anyone hasn't noticed, this solution is symmetric, i.e. colour(x,y) = colour(y,x) if you start numbering from the top left.
I have a lot more to write about the solution and method, and I'm not yet done with this approach, but if I start writing up I may never publish this, so I'll just stop here for the moment.
