Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 17x17 challenge. "Worth $289.00. This is not a joke."

blog.computationalcomplexity.org

Post reply on HN
Print view View original

61–70 of 78 posts

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#61

Post by DarkShikari »

machrider wrote: post #54
DarkShikari wrote: post #48

Earlier quoted context omitted.

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 )

Out of curiosity, what's the lowest score you've seen on 17x17 so far?

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

#62

Post by RiderOfGiraffes »

Retric wrote: post #31
RiderOfGiraffes wrote: post #28

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…

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.

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

#63

Post by [deleted] »

DarkShikari wrote: post #48
scythe wrote: post #47

Earlier quoted context omitted.

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

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 )

[deleted]

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#64

Post by RiderOfGiraffes »

scythe wrote: post #59
DarkShikari wrote: post #55

Earlier quoted context omitted.

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

Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.

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

#65

Post by Retric »

JabavuAdams wrote: post #46
Retric wrote: post #34

Earlier quoted context omitted.

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,…

See, that's the thing about really big numbers. 10% of 10^174 is still 10^173.

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

#66

Post by Retric »

RiderOfGiraffes wrote: post #62
Retric wrote: post #31

Earlier quoted context omitted.

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.

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…

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

#67

Post by lkozma »

DarkShikari wrote: post #61
machrider wrote: post #54

Earlier quoted context omitted.

Out of curiosity, what's the lowest score you've seen on 17x17 so far?

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…

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

#68

Post by cjg »

brent wrote: post #14
RiderOfGiraffes wrote: post #6

Earlier quoted context omitted.

You're not being serious, I know, but I'll answer seriously anyway. 1000x1000 is not an edge case - it can't be done - so offering a reward for a solution is pretty pointless.

A related and unsolved question (and thus legitimate) could be: what is the smallest c such that 1000x1000 is c-colorable.

According to http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf c would be either 17 or 18.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#69

Post by abentspoon »

RiderOfGiraffes wrote: post #64
scythe wrote: post #59

Earlier quoted context omitted.

Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.

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.

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

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#70

Post by ahn »

nandemo wrote: post #29
PieSquared wrote: post #5

I know the professor who writes this blog, Bill Gasarch. I was thinking of interning with him (at our high school, we do an internship + report about it in our senior year), but then decided against it because the math is a bit too abstract and unapplicable to (as Gasarch would put it) make me "properly enthused". He seems like a great guy. Anyway, while I haven't read the entire thing, I would suggest reading the bo…

> but then decided against it because the math is a bit too abstract and unapplicable Combinatorics isn't really abstract as far as math goes. In fact some call it concrete mathematics .

>Combinatorics isn't really abstract as far as math goes.

Huh? Is it naturally abstract?

Post reply on HN