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.
4 comments:
What do you mean by missing 2 cells?
You can turn it into a 0-rectangle grid by removing 2 cells. Rohan's can be made into a 0-rectangle by removing only a single cell. The goal of course is to make a 0-rectangle grid that doesn't need any cells to be removed..
I'm using a relatively dodgy method here (Excel with VBA code to check for rectangles) because I wanted to tackle this visually instead of programatically... and I've ended up with the result below. You only need to remove one cell (the top left corner) but filling it in with any value will give you 4 rectangles. Like yours, this is symmetric. If this helps you in any way then great :)
1,4,4,4,4,3,3,3,3,2,2,2,2,1,1,1,1
4,1,2,3,4,2,3,4,1,3,4,1,2,4,1,2,3
4,2,1,4,3,1,4,3,2,4,3,2,1,3,2,1,4
4,3,4,1,2,4,1,2,3,1,2,3,4,2,3,4,1
4,4,3,2,1,3,2,1,4,2,1,4,3,1,4,3,2
3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,4,3
3,3,4,1,2,1,2,3,4,3,4,1,2,1,2,3,4
3,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1
3,1,2,3,4,3,4,1,2,1,2,3,4,3,4,1,2
2,3,4,1,2,2,3,4,1,4,1,2,3,3,4,1,2
2,4,3,2,1,1,4,3,2,1,4,3,2,2,1,4,3
2,1,2,3,4,4,1,2,3,2,3,4,1,1,2,3,4
2,2,1,4,3,3,2,1,4,3,2,1,4,4,3,2,1
1,4,3,2,1,2,1,4,3,3,2,1,4,3,2,1,4
1,1,2,3,4,1,2,3,4,4,1,2,3,2,3,4,1
1,2,1,4,3,4,3,2,1,1,4,3,2,1,4,3,2
1,3,4,1,2,3,4,1,2,2,3,4,1,4,1,2,3
Yeap, I just verified Constantinos' incredible grid. Symmetric with only 4 rectangles, and only 1 cell needing removal to go to 0-rectangles (the top left cell). The colour populations are 73-72-72-72, with the 73 being the one used for the top left cell. In other words, identical characteristics with Rohan's grid. The question now is whether they are permutations of each other. Hmm...
Post a Comment