William Gasarch is not the Clay Mathematics Institute. He isn’t paying a million bucks for proofs of famous conjectures. But Gasarch is putting up 172 of his own dollars for the solution to an intriguing little stumper. And the prize problem appears to be somewhat easier than the Riemann hypothesis or the P=NP question. (Unless it’s impossible!)
Gasarch sets forth his prize challenge in a blog post, with further background in a paper and in the slides from a talk. All of those works are well worth reading, but for those who don’t want to chase down the references, here’s the gist. Our mission, should we choose to accept it, is to color the nodes of an n-by-m grid, using only a specified number of colors, and observing a particular constraint: Nowhere in the grid may the four corners of a rectangle all have the same color. (Only rectangles with sides parallel to the x and y axes are considered.) For example, here is a four-colored 15-by-15 grid that satisfies the no-monochromatic-rectangles constraint:
In this array of dots there are \( {15 \choose 2}^2=11025\) distinct rectangles. If you care to check through all of them one by one, you’ll find that in no case do all four corners have the same color. In contrast, here is a 16-by-16 grid that is almost but not quite rectangle-free:
Gasarch offers his $289 bounty for any four-colored 17-by-17 grid with no monochromatic rectangles. Why is that grid of particular interest? It’s a border case. Among square grids, all those up through 16-by-16 have been shown to have rectangle-free four-colorings. For the 18-by-18 grid and all larger squares, rectangle-free four-coloring has been proved impossible. For squares larger than 18-by-18, four-coloring has been proved impossible. The status of the 17-by-17 and 18-by-18 grids remains unsettled, but Gasarch believes that both are four-colorable.
Gasarch has much more to say about the mathematics behind this problem. Here I would like to muse on some computational aspects of searching for a 17-by-17 four-coloring.
To state the obvious first, this is not a problem we can expect to solve by exhaustive enumeration. There are 4289 possible colorings of the grid. Casting out symmetries brings that down only to 2 × 4287. There’s not world enough or time for checking them all.
Testing grids at random is also hopeless in the 17-by-17 case. This nonstrategy actually works quite well for small grids. For example, you can readily find a four-coloring of an 8-by-8 grid just by generating a few hundred thousand random colorings. But the method fails for larger grids because the proportion of all colorings that are rectangle-free falls steeply with grid size. (Consider the 2-by-2 grid: There are 256 four-colorings, and all but four of them are rectangle-free.)
To make any progress toward the 17-by-17 case, we’ll have to do at least a little thinking, rather than expecting the computer to do all the work. Here’s one idea that’s very easy to implement: Find a monochrome rectangle somewhere within the grid, change the color of one of its corners, and repeat until you can’t find any more rectangles. This algorithm works reasonably well for grids up to about 12-by-12, but then it runs out of steam. On larger grids, changing the color of a node to eliminate one rectangle is likely to create another rectangle elsewhere (or several more of them). As a result, the system merely takes a random walk, with trendless fluctuations in the number of rectangles at any given moment. You discover a rectangle-free coloring only if the walk happens to stumble on the zero point.
I found the 15-by-15 four-coloring shown above with an algorithm that’s a little more effective even thought it’s no more sophisticated than the corner-twiddling method. The program repeatedly chooses a node at random and tries assigning it all four possible colors, tallying up the number of rectangles for each color choice. Some color or set of colors must minimize the rectangle count; from among these optimal colors the program chooses one at random and sets the node to that color before repeating the loop. This is a “greedy” method: At each step the number of rectangles can decrease or remain constant but can never increase. Greedy methods are notorious for getting stuck in local optima that are inferior to the global optimum. Maybe that’s what happens to my program when I try it on 16-by-16 and 17-by-17 grids. Or maybe the search space is just too large. In any case, when I woke up this morning and checked the results of an overnight run, I did not find a rectangle-free four-colored 17-by-17 grid awaiting me.
Of course I really didn’t have to do any algorithm analysis at all to know that I wasn’t going to win $289 and eternal fame with a day or two of idle hacking. If the problem were that easy, Gasarch and his students would have solved it for themselves long ago.
In spite of these various failures and frustrations, the grid-coloring problem still looks tantalizingly solvable. If a four-coloring of the Gasarch grid exists, it seems like we should be able to find it by some practical computation.
There are certainly lots of approaches more powerful than the blind dart game I’ve been playing. For example, if local optima are the major impediment, some variation on simulated annealing might help.
A more radical possibility is to try to construct an instance rather than merely search for it. If we assume that the four colors are represented as evenly as possible, then the 17-by-17 grid must have 72 nodes in each of three colors and 73 nodes in the fourth color. Starting from a blank grid, it’s easy to mark off 73 nodes in a single color without creating a forbidden rectangle. Adding 72 nodes of a second color is only a little harder. But then the job gets tricky. When you try to fill in a third color, you also by default choose nodes for the fourth color at the same time, and conflicts pile up in a hurry. Some kind of backtracking approach is probably needed here. Gasarch links to a paper by Elizabeth Kupin of Rutgers that explores these ideas in more detail. (If you want to prove the nonexistence of a four-coloring, this is presumably the way to go.)
Gasarch mentions two other promising avenues: integer programming (the discrete variant of linear programming) and SAT solvers–algorithms for the satisfiability problem. Having spent some time hanging out with a few master SAT solvers, I’m intrigued by the latter possibility. You can almost encode the grid-coloring problem as an instance of NAE-SAT, or not-all-equal SAT. Each node of the grid is represented by a variable that can take on any of four values. We group subsets of variables four at a time into clauses, where each clause includes the variables representing the four corners of a rectangle somewhere in the grid. For the 17-by-17 grid there are \({17 \choose 2}^2=18496\) clauses of this kind. The entire formula is satisfied if we can assign values to the 289 variables in such a way that none of the 18496 clauses has all four of its variables with the same value. After 40 years of work on SAT, there’s a highly developed technology for solving such problems. However, there’s a hitch. SAT problems are formulated in terms of boolean variables, with just two values each, but the grid-color variables have four values. Thus a further layer of encoding is likely to be needed, bringing a further explosion in the size of the problem instance.
One final hackerish note: What’s the best way to detect the presence of a monochromatic rectangle in a grid? My candidate goes like this. We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if the result of the AND is nonzero. at least two bits are set in the resulting vector.
[Thanks to all the commenters for corrections and elaborations.]
Update: If you are coming late to this topic, please note there are three later posts discussing it, the last of which gives a solution: 22 December 2009, 13 November 2010, and 8 February 2012.
I wonder if it would be worth while breaking the problem up. Find all the 9×9, 9×8, 8×9 and 8×8 solutions and then try all the combinations of them that build a 17×17 grid. Of course, this is a recursive strategy, you should find all the 4×4 solutions when trying to find the 8×8 solutions. There is some repeated work (9×8 and 8×8 will both require 4×4), so you can start by generating a list of 4×4, 4×5, 5×4 and 5×5 solutions and store them for later reference.
I’m not seeing how the condition at the end of the article follows. With the 4×4 rectangle 2-colored this way:
BGGB
GBGB
GGBB
BBGG
then our bit vectors for blue are:
1001
0101
0011
1100
the AND of the the first and last rows is
1000
which is nonzero but no rectangle exists, I think. The condition should be that the result of the AND has at least two bits set.
It’s pretty easy to formulate this as a SAT problem with binary variables:
Have four 17×17 grids, one grid for each color. We need 17×17 constraints to say at least one of the four binary variables for each site must be on (each grid must have one color, we can always remove extra colors at the end). For each rectangle in each grid we also have a constraint that ORs the negation of the four binary variables. This stops all four corners of a rectangle being one color.
I tried this and a small number of variants in minisat and got nowhere.
The test at the end is wrong, you need to check if there are two or more bits set in the and of any of the 4 bit vectors. Fortunately you can do this quickly by testing if a & (a - 1) is non-zero.
@Mark Gritter and cityhall: You’re exactly right, of course. Sorry for the careless error.
Pingback: uberVU - social comments
I’m trying a naive GA implementation using pyevolve; the best I’ve managed with this approach is 22 rectangles in a 17×17 grid.
I am very interested in finding out if anyone has found an efficient, quick way to test if a grid is a valid solution. As I work on this problem, this seems to be the slowest part of my implementation, by a large, large magnitude.
endeavormac: represent each row with 4 bitvectors for whether the cell is that color. Maintain a list of empty cells. Pick a cell and a color, set the appropriate bit, then for each other row, and the vector with the other row’s vector for that color. If more than one bit is set in the result then the color is invalid. Use the a & (a - 1) trick to test if more than one bit is set. If it’s bad, backtrack by clearing the bit and putting the cell back on the open list.
Isn’t it the case that you can swap any two rows or any two columns and preserve the rectangular-coloring property? If it is, then a more substantial symmetry reduction could be performed.
123,665,200,736,552,267,030,251,260,509,823,595,017,565,674,55
0,605,919,957,031,528,046,448,612,553,265,933,585,158,200,530,6
21,522,494,798,835,713,008,069,669,675,682,517,153,375,604,983,
773,077,550,946,583,958,303,386,074,349,568
different combinations should convince people not to just randomly put down colors
I don’t have time to try this myself, so I would like to offer the following suggestion.
We can pretty easily define a probability distribution over colorings that it is possible to sample from where any rectange-free colorings that might exist will have maximal probability. We can do this by creating an undirected graphical model on 17*17 4-valued discrete variables that represent colors. The factor graph for this markov random field will have one factor for each set of 4 vertices that correspond to the corners of a rectangle. The factor contributes a positive value to the energy function if and only if all of the four vertices have the same color.
Now that we have this distribution over colorings we can draw lots of samples and check each one. This isn’t immediately doomed (maybe it is still way too slow?) because colorings with very few rectangles will be much more probable than colorings with a lot of conflicts.
One would have to experiment with different sampling algorithms (presumably based on the obvious Gibbs sampling). What I like about the approach I am proposing is that it is a “soft” non-greedy (depending on the sampling temperature) variant of the algorithm described in this post that works for 15 by 15.
Please let me know if anyone tries something like this, if the problem is still open in a few weeks I might give it a shot myself.
I am running a minisat+ PB encoding of the problem now, though i doubt it will yield anything that hasn’t been explored thus far (here, or by gasarch and co.). It is pretty brain-dead — 4 vars for each location in the grid. 3 sets of constraints:
1)The sum of the 4 vars for a location is equal to 1 (locations can have only 1 color)
2)The sum of all the vars is 17^2 (all locations must have a color)
3)Somewhat complicated: Consider each row in turn. Consider each location in a row as a potential “upper-left corner”. Then, assuming that upper-left corner, iterate over all possible upper-right corners. Then consider the same locations in all other rows. The sum of these four locations’ variables, per-color, must be less than or equal to 3.
This encoding leverages the symmetry between rectangles in the grid, and so eliminates representing some of the possible rectangles from the clause set.
1) THANKS for the post! You’ve done a far better job explaining the problem than I seem to have judging from the comments on my blog and also the emails that I’ve gotten.
2) One correction: 18×18 is STILL open as to whether or not its
4-colorable. I think it is.
3) NICE spam screening device! Over at Complexity Blog we use one where you need to type in some nonsense word that is written in a strange font.
Here’s how I think this problem could be solved. Make all possible 2×2 squares and find the valid solutions (that will go quick). Using these solutions as templates create 3×3 squares and find all these valid solutions. Keep going until 17×17. The search space should be smaller than of the other methods I’ve seen.
The method mentioned at the end of the article doesn’t quite work, as a previous comment showed.
Instead of checking whether Row 1 & Row 2 == 0, check whether they are a power of two. If there is a single digit in the binary representation, the AND is nonzero but there is not a rectangle. However, if there are two or more binary digits then there must be at least one rectangle. Thus, if the AND is a power of two (or zero, of course) then there is no rectangle.
Reminder: A is a power of 2 iff A & (A - 1) == 0.
With enough people looking at it, you essentially are brute forcing it. Might want to consider a distributed computing solution.
What are the largest grid dimensions, including non square ones, where all possible solutions have been found? Since all grids must be made up of the members of all the smaller grids, that seems like it could be utilized. For example, the 17×17 grid will consist of 4 legal 16×16 grids put together. If all solutions are known for a fairly high grid size, it might be a better launching point to stop thinking about the 4 colors altogether and start thinking of overlapping versions of the solved grids.
I’m working on a Java implementation of the divide and conquer solution (i.e., use all possible solutions to 8 and 7 sized ones to do 17×17). May or may not be feasible depending on the number of solutions of size 7 and 8. If there aren’t that many this might work.
If 2 bits need to be set, just check if the result of the AND is larger than 2. 1 comparison only. Not 1 subtraction 1 AND and 1 comparison.
dharh and Paul:
I’m not sure that approach would work well. While it is true that any solution to 17×17 would contain several solutions to 16×16, it probably isn’t true that all, or even most, 16×16 solutions are useful bases for 17×17.
A similar idea could be useful for a genetic approach, though. For example, with an EA of some type that operates on this thing, you could generate solutions, even partial solutions, to small grids from a randomly initialized population; then use those to seed the initial population for a larger grid, and so on. You may be able to cut right to the chase and hold solutions of various sizes in the same population and apply some selection pressure to push for larger grids.
Trying some naiive approaches to this. I’m using Mathematica, and I’ve thus far implemented a general (nxn) random array generator, and an algorithm to test if the array meets the criterion. I used the row comparison method described here, and checked that it works with some small sized lattices. Looks good so far.
I did some timing tests, and it looks like it takes about .015 seconds to test one 17×17 array. This works out to 10^164 years to brute force the problem (check every possible arrangement.) Wondering how I might implement some symmetry arguments and simplify my testing method…. this has certainly captured my attention… two days before I’ve got a term paper due :)
Like a lot of other people, I wish I had the time to work on this, but I don’t so I will just offer ideas.
My initial thought was with dharh and paul.
A 17×17 will have to contain a 16×16…
However, as anescient said, we don’t know if a given 16×16 grid could make a 17×17. But, it is a sufficient condition, and a vastly smaller search space to begin with.
I think Spencer Tipping had a potentially very useful insight about row order, although he seemed somewhat uncertain.
On inspection, it is clear that row order does not matter. You can swap the first and last rows and it cannot make any rectangles. Any rectangles would already be present in the grid, you would just be changing the height.
From one 16×16 grid, it would be pretty easy to make 16!-1 new grids by reordering the rows.
Similarly, this applies to the columns. Reordering the columns would only change the width of any rectangles present. So from a single 16×16 grid we can make 16!-1 new ones by reordering the columns.
Sounds like a lot. Let’s say we have 4 columns:
a b c d
we can generate:
a b d c
a c b d
a c d b
a d b c
a d c b
b a c d
…
From reording columns alone, we can get 4!-1, or 23 other grids.
We can take it a step further. If we re-order the columns, we have a valid grid still, and we should be able to reorder the rows just as easily.
So for each of the 24 grids belonging to the column family of a single kernel, each of those belong to a row family of 24 grids.
From a single 4×4 kernel grid, we actually have a 24^2 family of grids, all with the same color validity.
That being said. If there exists a valid coloring of a 17×17 grid, there exists (17!)^2 grids, or 1.26513547 × 10^29.
That also means, for every grid that fails the test, there are 17!^2 grids of the family that you know will fail as well.
So it might be useful to try looking at families of grids instead of individual grids, and test
~126,513,547,000,000,000,000,000,000,000 grids at a time. It would be something of a performance boost.
And if you still think you’re going to solve this from random searching, you just don’t understand large numbers.
Also, a note to designers. Justify might nook neat and tidy to you, but it can make for some ugly text. Uneven spacing is 3^^^3 times more distracting than jagged right edges. There’s nothing wrong with left-align.
@anescient,
Yeah, having thought about it, while its true that any 17×17 must have a 16×16 inside it, the shear number of 16×16 solutions that leads to dead ends probably doesn’t lead to a small solution space. It still might be the best brute force method though. Random generation or full search starting from an empty grid is not gonna be productive.
@Spencer Tipping: Yes, you are correct: Rows can be permuted without altering the number of rectangles, and the same is true for columns. For the 17-by-17 case this reduces the number of distinct grids by a factor of (17!)2, or about 1029. That’s a big number and surely we can exploit it to advantage, although it’s still not enough to have much impact on 4289 cases.
I gave my idea a try. I gave up attempting to calculate all the 4×4 solutions after I found 8 million of them. There are about 60,000 2×4 solutions, so I would have to test over 300 million combinations. I could finish that step eventually. I’m guessing there are somewhere between 100 million and 300 million solutions to the 4×4 grid. So, combining all these to find all the 4×8 solutions would require something like 10^16 tests. Obviously this is a dead end.
I like Spencer Tipping’s observation that rows and columns can be swapped. I might use that to trim down the number of solutions I use from a previous step. The 60,000 2×4 solutions would become 2,500 unordered solutions. The 100 million 4×4 solutions would become about 200,000 unordered solutions.
I think I’m missing something because the solution seems very obvious. Consider the 2×17 challenge.
It is NOT doable because their are 17 vertical columns and only 16 ways to make different vertical columns.
Therefore, impossible.
Since 2×17 is a subset of 17×17, the 17×17 challenge is also impossible.
Where have I gone wrong? If I haven’t, can I get some money?
Never Mind, I’m an idiot
I have tried the simulated annealing approach running this on CUDA on 10 graphics cards (total 2400 processors) and various cooling schedules. So far the best result I have had (after a couple of hours running) has 8 rectangles in it, which I guess is reasonable but far off the prize!
Is there nothing to be derived from properly describing a functional grid? Given the fact that you can re-order columns and rows at will, that implies a mathematically describable, and therefor possibly reproducible, state to me.
I didn’t see any code here, so if someone wanna use mine as a framework, he it goes (I don’t guarantee there’s no bug :))
http://codepad.org/svtI3f5z
Rotating an inner complete grid, swapping rows/columns, don’t break the grid. All possible full complete grids must have inner complete grids and only inner complete grids. I think everyone already appreciates this.
Aside from people trying to create 2x17s and stacking them. What about shuffling 8x8s and 9x9s with the corner of 9x9s overlapping in the center. The search space then becomes all the solutions of those two grids.
Or heck just using 9x9s has anyone tried this with the center overlap?
It is impossible to solve that problem with 2 colors for a matrix bigger than 4×4, with 3 colors for a matrix bigger than 9×9, or in general, any number of colors C for a matrix bigger than C^2 x C^2. I have discovered a truly marvellous proof of this, which this comment box is too small to contain.
@lemonhead, so you are basically implying that because the grid size is 17 which is larger than 4(colours)^2=16, it is impossible to solve it?
however according to @gasarch, he says size 17 and 18 are still colourable. I’d be interested in seeing your proof.
I was hoping to code this up myself but lack the time. Is there any way to take advantage of the patterns that form in solutions from smaller dimensions of the problem? For example, I notice that the longest line that forms is four dots. Far more common is three dots. And there tends to be a lot of L shaped corners. Someone could do a statistical analysis of the distribution of these shapes in a large sample of answers to the 16 by 16 problem, and then concentrate on solutions that maintains a similar distribution for 17 by 17. If the distribution of the patterns change with size, they might change predictably which you could tell by comparing solutions to different sizes side by side.
@noj: I’m just kidding, but I’ve done some tests and only got to color 4×4 with 2 colors and 7×7 with 3 (but I suspect 8×8 is possible)
if the 3 color limit is really 9×9, we’d have a (weak) pattern
since we already know 15×15 is possible and 18×18 is impossible, this pattern would make more sense…
Actually, lem0nhead. I haven’t found any above 4×4 for 2 colors, or 9×9 for 3.
8×8 for 3:
00211201
02112010
21120100
11201002
12010022
20100221
01002211
10022112
9×9 for 3:
121002021
210020211
100202112
002021121
020211210
202112100
021121002
211210020
112100202
It takes less than a second for either. I actually managed to find 16×16 with 4 colors in a few seconds, but no luck on 17×17.
I think we can reduce the problem quite a bit…. although I’m just thinking out loud now, haven’t actually tried it yet…
Explaining this for an 8×8 is grid is somewhat easier though..
OK, so with an 8×8 grid we have 16 bits to fill per row/column, 2 bits per node. this thus means that there is only 65536 possible columns, and no possibility can appear twice, as that would immediately result in at least one rectangle. (only true for grids larger then 4×4)
From those 65536 possible columns we pick 1 randomly, and put it in the first column. Now we can filter out all remaining 65535 columns that will cause any rectangle formation with the first column. Then from whatever we have left, we pick the 2nd column, and filter the remaining columns with the 2nd column… then we pick the 3rd, and so on, and so on…
if no columns are left while we still have to fill in another, we either have to start over, or backtrack to a previous state and pick another random… although I guess that could still result in having to backtrack all the way to the 1st column, and thus still requires 2^32 iterations for a 8×8 grid, but I think there is a lot of early outs.
This should be a proper 16×16, four color grid:
0010113323220312
0101133232203120
1011332322031200
0113323220312001
1133232203120010
1332322031200101
3323220312001011
3232203120010113
2322031200101133
3220312001011332
2203120010113323
2031200101133232
0312001011332322
3120010113323220
1200101133232203
2001011332322031
I seem unable to find a 10×10 for 3 colors and a 5×5 for 2×2(Which is said in his paper that does not exist).
@lemonhead
Apparently nobody caught the joke there :)
@paddy,
I think that map is a dead end. Though I didn’t do an exhaustive search of all possible reformations of it, any attempts so far to turn that 16×16 into a 17×17 met with no results.
I’m going to say this is impossible.
Every row will have at least one color with 5 or more instances.
At least one color will have 5 rows where it is used at least 5 times.
For the first of those five rows, you have a max of 17 possible columns to put 5 colors.
For the second of those five rows, you have a max of 13 possible spots (you can overlap just one of the previous five columns… 5-1).
For the third, you have a max of 9
For the fourth, you have a max of 5
For the fifth, you have a max of 1 possible spot, which isn’t enough for five colors.
After thinking about it a bit more…
Nevermind…
For the first of those five rows, you have a max of 17 possible columns to put 5 colors.
For the second of those five rows, you have a max of 13 possible spots (you can overlap just one of the previous five columns… 17-5+1).
For the third, you have a max of 10
(you can overlap two of the previous row’s columns 13-5+2)
For the fourth, you have a max of 7
(you can overlap three previous row’s columns 10-5+3)
For the fifth, you have a maximum of 6 positions
7-5+4
hmmm… maybe it is possible?
Pingback: Math, anyone? - Page 7 - PersonalityCafe
I couldn’t find a 17×17 for 4 colors, but this is what I’ve found for 5 colors. So far I haven’t found a 21×21.
17×17, five colors:
01033143221100434
10331432211004344
03314322110043441
33143221100434410
31432211004344102
14322110043441020
43221100434410203
32211004344102034
22110043441020343
21100434410203433
11004344102034332
10043441020343322
00434410203433221
04344102034332211
43441020343322112
34410203433221120
44102034332211201
18×18, five colors:
043122334210234010
431223342102340100
312233421023401001
122334210234010011
223342102340100113
233421023401001132
334210234010011324
342102340100113244
421023401001132443
210234010011324434
102340100113244342
023401001132443422
234010011324434220
340100113244342203
401001132443422034
010011324434220343
100113244342203430
001132443422034301
19×19, five colors:
4303002340121224314
3030023401212243144
0300234012122431441
3002340121224314411
0023401212243144110
0234012122431441103
2340121224314411034
3401212243144110340
4012122431441103403
0121224314411034032
1212243144110340323
2122431441103403230
1224314411034032300
2243144110340323002
2431441103403230024
4314411034032300242
3144110340323002423
1441103403230024231
4411034032300242312
20×20, five colors:
02102234401133414324
21022344011334143242
10223440113341432420
02234401133414324201
22344011334143242010
23440113341432420100
34401133414324201002
44011334143242010022
40113341432420100223
01133414324201002230
11334143242010022304
13341432420100223043
33414324201002230431
34143242010022304311
41432420100223043114
14324201002230431140
43242010022304311401
32420100223043114013
24201002230431140131
42010022304311401313
There seems to be a correlation between what can be c-colored and what can be c-colored with a “periodic” pattern (like paddy’s). The non-existence of the latter can actually be proven easily.
Take the 17×17 grid for example. If we are to use 4 colors, there has to be at least 5 (>17/4) instances of the same color in the pattern. For the pattern to work, the (circular) distances between each pair of the instances of the same color should all be distinct (this is not obvious but can also be proven). There will at least be 10 such pairs (5 choose 2) but only 8 possible distances (0:15, 1:14, 2:13 etc.). Therefore a periodic solution is not possible.
Of course, this does not rule out a more general solution. At the same time, it seems to coincide with the known results. For instance, one can use the same arguement to prove that a 10×10 grid is not 3-colorable with a periodic solution and it is known that 10×10 is indeed not 3-colorable. Nevertheless, such correlation is sometimes misleading in maths. Still, I think it is an interesting direction.
@nil, I like your reasoning, but one advantage you gain by having non-periodic coloring is that the color with 5 in a row doesn’t have to be repeated on every line. For example, there could be 5 blue in row one (with 4 of the other 3 colors). Then in row two there could be 5 red. By alternating the pattern you may be able to find a solution.
Regarding non-periodic coloring. I’ve successfully generated 6×6 through 15×15 grids using a genetic algorithm.
6×6 took less than 1 second. 15×15 took 10 minutes. 16×16 so far unsolved, but the best run was down to 5 rectangles. 17×17 ran overnight, still unsolved, but the best run was down to 19 rectangles.
(15×15)
124433224331132
143412412124332
124123443213241
232421313312144
223213342444111
431212124234443
433234431112212
334223111421324
214114331234322
321142434143134
343341123132421
113424122343413
442131243221314
411343232411223
241334321423241
@nil, your observation on the limits to “periodic” colorings is spot on, so that no such 3-coloring can exist for the 10×10 grid. However, the 10×10 grid *is* nonetheless 3-colorable. Gasarch et al. give a 3-coloring on page 34 of the paper Brian linked to.
Pingback: 17 x 17 Challenge « Chris Taylor