News for hackers. Stuff that matters.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by RiderOfGiraffes on Monday November 30, 2009 @05:37PM (#968862)
To summarise the numbers given elsewhere ...

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by abentspoon on Monday November 30, 2009 @07:31PM (#969003)
You are also free to interchange rows and columns.

This should reduce the number of possible grids by a factor of (17!)^2, leaving 3.25e143 colorings.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Retric on Monday November 30, 2009 @06:14PM (#968905)
This is also more brute forcible than 4^289 might suggest. Consider a 2 x 2 grid. The first square does not count, there are 2 options for the second square, and 3 for the 3rd. But there is only 4 options for the fourth square if the first 3 squares where not the same color. Resulting in (2 * 3 -1) * 4 + 3 = 23 options not 4^ 4 = 256.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by RiderOfGiraffes on Tuesday December 01, 2009 @05:08AM (#969534)
Although this succeeds in eliminating 90% of the search space for a 2x2 grid (and even then I think your sums are slightly wrong) this doesn't even dent the 17x17 case. The 2x2 square in the top left of that only has 23 (or fewer) configurations, but now you can probably no longer permute the colors. The savings are irrelevant in the larger cases.

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Retric on Tuesday December 01, 2009 @09:04AM (#969718)
There is something like 12, valid 2x2 grids, and you can get rid of almost another (17!)^2 options because rows and columns are interchangeable. Actually thinking about it a little bit the only valid option for the top left square is:

  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.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by xenophanes on Monday November 30, 2009 @06:41PM (#968947)
counting there being less options b/c colors that aren't used yet are equivalent isn't going to get you very far. after all 4 colors are placed once it stops helping.

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Retric on Monday November 30, 2009 @06:53PM (#968962)
I was trying to point out that you can quickly eliminate 90% of the problem space so while I did forget about some summitry's my point still stands. Anyway looking at a 3x3 grid the box limitation is going to become increasingly important.

  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.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by JabavuAdams on Monday November 30, 2009 @09:04PM (#969098)
See, that's the thing about really big numbers. 10% of 10^174 is still 10^173.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Retric on Tuesday December 01, 2009 @08:36AM (#969679)
It's no where near 10^173 because of the box limitations. Adjusting for summitry's there are 12 (or less) 2x2 boxes. But then building a 3x3 box, the total is not 12 * 4^5 possible because at least 4 * 12 of them are eliminated by the boxing constraint. It's more than that but I am not doing this by hand.

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by xenophanes on Monday November 30, 2009 @07:03PM (#968973)
how does it stand? you have given no argument this will make a substantial reduction when the grid size is much larger than the number of colors
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Retric on Monday November 30, 2009 @07:32PM (#969007)
Ok, if you consider in on the logarithmic scale then it's almost meaningless, but the idea was:

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by xenophanes on Monday November 30, 2009 @07:35PM (#969012)
> you don't need to innumerate every complete grid before eliminating them.

Of course. For large grids, I wonder if you can eliminate everything that doesn't have nearly equal amounts of every color.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by Retric on Monday November 30, 2009 @07:57PM (#969032)
Yes, though I would try an construct a 9x9 grid, and then try tacking on 3 valid 8x8 grids, then add the filler. My guess is larger grids are more constrained than working with smaller independent grids. Also you could store the extra grids as part of a larger data structure and work your way up to them by testing valid 2x2 grids, which are subset's a valid 3x3 grid etc.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by scythe on Monday November 30, 2009 @09:12PM (#969105)
I've got a script running right now that should be able to color everything by a sort of random walk. It colors around 230 nodes quickly and then slows down, so I suppose I'll find out soon enough.

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

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Monday November 30, 2009 @10:09PM (#969156)
I wrote a simple genetic algorithm in C, took about 30 minutes, but I suspect a break-it-down approach starting at small blocks and working up might work better.

It did 13x13 really fast but I have a hunch it might not work very well for 17x17...

( Link: http://pastebin.com/m51149dd9 )

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by ganley on Tuesday December 01, 2009 @02:29PM (#970484)
This is a class of problems that Monte Carlo optimization (GA's, simulated annealing, etc.) typically can't solve, because almost-solutions are generally really deep local minima that the search machinery can't climb out of.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by machrider on Tuesday December 01, 2009 @12:36AM (#969301)
Out of curiosity, what's the lowest score you've seen on 17x17 so far?
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Tuesday December 01, 2009 @03:51AM (#969472)
Down to 39:

    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
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by machrider on Tuesday December 01, 2009 @02:23PM (#970473)
I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like they stop progressing. Haven't seen 11 yet.

    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...

http://pastebin.com/m33bccec1

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.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by ganley on Thursday December 03, 2009 @08:35AM (#974292)
I'm not sure minimizing the score (at least, until you get to 0) is interesting, but anyway, I wrote a simple hill-climbing-with-random-perturbation routine and let it run over and over for the last couple of days. So far my best has a score of 10:

12032213310013002 21301001102213023 30120303220111321 03330220131122010 22313133001012230 03123321011233102 20313010123321102 03022111302120233 31232100023232131 03201103213001212 11000232021331223 20221213031300031 13130132102302302 31103210230220313 12310021322030311 21012022213103330 12201332333120100

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by lkozma on Tuesday December 01, 2009 @06:42PM (#971097)
Something that might help would be to have the grids in some sort of canonical form: as swapping rows and columns doesn't change the score, for every configuration there is a reordering such that the whole grid value is minimal (i.e. if we read out as a 279 digit number). Intuition says that if grids were brought in such a canonical form, recombination might work better.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Tuesday December 01, 2009 @02:40PM (#970524)
Link to a diff of your fixes/tweaks?

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.)

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by lkozma on Tuesday December 01, 2009 @10:00AM (#969828)
34 here (after some tweaks):

  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 3
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by DarkShikari on Tuesday December 01, 2009 @01:35AM (#969353)
I think about 51, I haven't been saving the best so far. I'll tee it to a file from now on.

Edit: Oops, my random-restart code had an obvious bug. It's probably not very useful anyways, so I removed it.

http://pastebin.com/m63191b11

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by scythe on Tuesday December 01, 2009 @03:00AM (#969431)
Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by RiderOfGiraffes on Tuesday December 01, 2009 @07:52AM (#969626)
I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by abentspoon on Tuesday December 01, 2009 @11:46AM (#970056)
I've placed 74 using an IP solver

      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.

http://pastebin.com/m4c4696af

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