This should reduce the number of possible grids by a factor of (17!)^2, leaving 3.25e143 colorings.
Besides, to some extent you are preempting the problem. You've counted the number of colorings of the 2x2 grid and found there to be only a small number. The evidence suggests that the number of colorings of the 17x17 grid is either 1 or 0 (up to permutation of colors), but that doesn't mean the search is trivial.
I may not have expressed that clearly, but I hope I've conveyed the point.
0,0
0,1
However, the vast majority of the grids are eliminated by the boxing constriant before the grid get's all that large.also you're counting wrong. there are 2 or 3 options for the third square. 2 if the first 2 squares got the same color.
Step 1: (1,x,x,x)
Step 2:
There are 2 meaningful options (1,1,x,x) and (1,2,x,x) because (1,3,x,x) is the same as (1,2,x,x). Granted only apply to the first 2x2 grid.
Step 3: (1,1,1,x), (1,1,2,x), (1,2,1,x), (1,2,2,x), (1,2,3,x)
Step 4: (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,1,2,3), (1,2,1,1), (1,2,1,2), (1,2,1,3), (1,2,2,1),(1,2,2,2),(1,2,2,3), (1,2,3,1),(1,2,3,2),(1,2,3,3),(1,2,3,4)
So 14 options.The reason you can't crack RSA is because after skipping composite numbers and small primes you cant further reduce the search space. Don't forget 20x20 box is known to not be solvable and the 16x16 box has at least one known solution.
A) you don't need to innumerate every complete grid before eliminating them.
B) How you count is important, if you just looked at the top row the boxing effect does not help and you have almost 2 * 3 * 4^14 options.
PS: You can also cull some rotational summitry's from those 14 options before you start, but again that's only important if you are trying to actually calculate it.
Of course. For large grids, I wonder if you can eliminate everything that doesn't have nearly equal amounts of every color.
edit: nah, at this rate it won't finish. source here for those interested; you probably just need to iterate over the remaining empty values in a more effective way than I am: http://ctrl-v.org/3708
It did 13x13 really fast but I have a hunch it might not work very well for 17x17...
( Link: http://pastebin.com/m51149dd9 )
1 0 1 0 2 0 2 1 0 2 1 3 3 2 3 3 1
3 3 0 3 1 2 3 0 0 1 1 1 2 2 2 0 1
3 2 3 2 2 0 1 0 3 0 3 3 1 1 0 2 1
0 3 1 2 1 1 2 3 1 0 3 0 0 3 2 0 2
0 1 1 3 3 3 1 0 1 1 2 2 3 2 0 2 0
3 1 2 2 3 1 0 1 0 3 0 2 0 3 0 1 2
1 1 1 2 0 2 3 2 3 3 0 0 1 2 0 0 3
2 2 0 0 3 1 0 1 3 1 3 0 1 2 1 3 2
0 0 2 0 0 2 0 3 1 2 1 2 1 3 3 1 3
3 2 2 1 0 3 0 1 1 0 3 1 2 0 3 2 3
1 3 3 0 1 3 2 2 1 3 0 2 2 0 1 3 0
2 3 2 1 2 1 1 2 0 0 1 0 3 0 2 3 3
1 0 3 3 2 2 1 0 2 3 2 1 0 0 3 1 2
0 2 1 1 0 3 3 2 0 2 2 3 0 3 1 1 0
2 1 3 2 3 0 0 3 2 2 1 3 2 1 1 0 0
0 2 0 1 1 0 3 3 2 3 3 2 3 0 2 1 1
2 0 0 3 1 2 2 3 3 0 0 1 1 1 3 2 0 Score: 12
2 3 0 1 3 2 1 2 2 3 1 2 0 3 1 3 0
2 1 1 2 2 1 1 0 3 3 3 3 3 2 0 0 0
2 2 1 1 0 3 3 3 1 0 2 0 1 3 3 0 2
3 2 0 1 1 1 0 3 2 1 3 0 2 2 0 3 1
1 2 1 3 1 0 2 2 0 2 0 0 3 3 1 1 0
1 1 3 3 0 2 2 0 0 1 3 1 0 2 3 1 2
3 2 3 0 2 1 0 0 0 0 1 2 1 3 2 1 3
1 3 3 2 3 1 0 1 2 2 0 3 0 1 2 0 2
2 0 2 1 3 0 3 1 0 2 3 1 2 0 0 1 3
3 0 2 0 1 3 1 2 3 3 2 1 1 2 2 0 0
0 0 2 3 2 3 2 0 2 1 0 3 1 1 1 3 3
2 0 1 3 3 0 2 3 3 0 1 1 0 1 2 2 1
0 1 0 2 1 0 2 3 1 3 2 2 2 1 3 0 3
3 2 2 2 0 2 0 1 1 1 1 3 3 0 3 2 0
3 3 0 3 2 1 3 2 1 0 0 1 2 0 1 2 2
1 3 3 0 0 3 1 3 1 2 0 2 3 2 0 2 1
0 1 3 0 2 2 3 1 3 2 2 0 0 0 1 3 1
Edit: I can't reply to you, so...It's not pretty, but I did a few things. Instead of taking the top n candidates and breeding them randomly, I kept all of them (NUM_STATES 200 and KEPT_STATES 200), but weight them according to score. So the best scores have the highest chance of passing their DNA down to the next generation, but the occasional loser gets lucky too.
Mutation is also weighted, so the most likely number of mutations is zero, but it's possible to have up to 4. Increasing this value made the performance go down, but it's also possible that there is no way to get to a solution by incrementally tweaking a decent attempt. Which could explain why I'm stuck at 12.
There are a few optimizations that may or may not make a difference, for instance in the scoring function. I think the pick_best_states function was not actually picking the best states. If you had two states with the same score, the first one is kept, but the next one is not. I fixed this. The stupid thing is, with NUM_STATES and KEPT_STATES at 200, it's basically an n^2 sort now. I never bothered to improve that.
Finally, compiled with -O3 and let 'er rip.
12032213310013002 21301001102213023 30120303220111321 03330220131122010 22313133001012230 03123321011233102 20313010123321102 03022111302120233 31232100023232131 03201103213001212 11000232021331223 20221213031300031 13130132102302302 31103210230220313 12310021322030311 21012022213103330 12201332333120100
I've only got to 30 here running 8 instances of mine.
(Also, I imagine this could probably benefit from a really fast PRNG, like an LCG.)
0 0 0 0 0 1 1 1 2 2 2 2 2 3 3 3 3
0 1 1 3 3 0 1 2 0 1 2 3 3 0 2 2 3
0 1 2 2 3 0 0 0 3 3 3 1 2 1 1 2 1
0 2 3 3 2 1 3 3 1 1 0 0 0 2 3 2 1
0 3 0 1 1 3 2 3 1 2 1 1 3 3 0 0 2
1 1 3 2 0 3 0 1 3 0 1 2 3 2 2 0 2
1 2 0 2 1 0 2 3 3 0 2 3 0 1 3 1 0
1 3 0 2 2 2 3 0 2 1 0 1 1 0 1 3 3
2 0 1 2 1 0 3 1 3 2 3 0 1 3 2 0 1
2 0 3 1 0 2 2 1 0 1 3 2 0 1 0 2 3
2 1 3 1 0 3 2 0 2 3 2 3 1 2 0 3 0
2 3 1 3 2 1 0 2 3 3 0 1 2 0 0 1 2
3 0 2 3 2 3 0 1 1 2 3 0 1 0 2 1 0
3 1 2 0 1 1 3 2 0 3 0 2 3 2 3 0 0
3 2 2 0 3 1 1 3 2 0 1 0 1 1 0 3 2
3 2 3 1 3 2 1 0 0 0 1 0 2 3 2 1 1
3 3 2 0 1 2 1 0 1 2 2 3 0 0 1 0 3Edit: Oops, my random-restart code had an obvious bug. It's probably not very useful anyways, so I removed it.
1 1 . . . . . 1 1 . . . . . 1 . .
. 1 1 1 1 . . . . . . . . . . . .
1 . 1 . . 1 . . . . . 1 . . . . 1
1 . . 1 . . 1 . . . 1 . . . . 1 .
1 . . . 1 . . . . 1 . . . 1 . . .
. . . 1 . 1 . 1 . . . . . 1 . . .
. 1 . . . 1 1 . . 1 . . . . . . .
. . 1 . . . 1 1 . . . . 1 . . . .
. . . . 1 1 . . 1 . . . 1 . . 1 .
. . 1 . . . . . 1 1 1 . . . . . .
. . . . 1 . . 1 . . 1 1 . . . . .
. . . . . . 1 . 1 . . 1 . 1 . . .
. . . 1 . . . . . 1 . 1 1 . 1 . .
. 1 . . . . . . . . 1 . 1 1 . . 1
. . 1 . . . . . . . . . . 1 1 1 .
. . . . 1 . 1 . . . . . . . 1 . 1
. . . . . . . 1 . 1 . . . . . 1 1
The solver chokes on anything larger than a 6x6 grid, but I've had good luck adding one row at a time to a smaller solution.edit: He mentions that he already found a size 74 set in one of the linked pdfs. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf
The number of possible 4-colorings of a 17x17 grid is 4^289 which is about 10^174, but that doesn't take into account the permutations of colors (4!) and possible symmetries.
However, since almost all colorings have no symmetry that's largely irrelevant, so the number of colorings of the grid (up to permutations of colors) is about 4^289/24 which is about 4.122e172.
Within the 17x17 grid we must avoid X-Y-aligned rectangles with corners all the same color. The number of such rectangles is obtained by choosing two rows and two columns, and so is (17choose2)x(17choose2) = 23409.