3 ms·
The example they give of randomly changing one coloring and getting a whole bunch of rectangles makes me wonder if there are any points in that coloring that yo
by Natsu 15y ago
The example they give of randomly changing one coloring and getting a whole bunch of rectangles makes me wonder if there are any points in that coloring that you could change without destroying the solution.
I doubt there are any, but it probably wouldn't take that long to write a program to check...
EDIT: And after reading this, I'm starting to wonder about other ways to use this solution to search for others, such as swapping two colors:
http://bit-player.org/2009/17-x-17-a-nonprogress-report http://bit-player.org/2009/17-x-17-a-nonprogress-report
- Retric 15y agoThat's interesting, last time this came around I started working though how to do it using a Sudoku style solver. Step 1: If a solution exists it's going to have 4!(17!)^2 'mirror' images of the same solution. To avoid this problem we give each color a number and a specific ordering of the solution. Thus eliminating 4!(17!)^2 - 1 options. Step 2: Based on the form that order takes we fill in the grid as much as possible. (Most of the top and side row). Step 3: Start plugging in missing squares until you find contradictions. EX: If swapping a column gives a lower ordering it's not a valid solution.
- eichin 15y agoTook about 20 minutes to write some python code to search; takes about 1/3 of a second to try all 3x17x17 mutations and find at least one rectangle produced by each. So yeah, every single-point change "destroys" the solution.