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

51–60 of 78 posts

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

#51

Post by klipt »

RiderOfGiraffes wrote: post #18
brent wrote: post #14

Earlier quoted context omitted.

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

The problem with that is knowing that you have the minimum. The good thing about the question as asked is that it's asking for something specific and not a proof of impossibility. Your question is legitimate and interesting, but requires a proof of minimality. That's difficult.

A different question would be "who can come up with the smallest c in 6 months", which probably wouldn't yield the true answer, but for a $1M prize it might come quite close (and could lead to some interesting theoretical advancements).

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

#53

Post by drbaskin »

PieSquared wrote: post #49
nandemo wrote: post #29

Earlier quoted context omitted.

> 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, but... coloring grids of squares? Not that I really have anything against abstract mathematics. It's still very cool, but it's just not going to get me very excited - or at least this exact branch of it, I guess.

I'm not one to say that coloring grids of squares sounds fascinating to me, but nandemo's point still holds -- as far as mathematics goes, it's pretty concrete.

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

#54

Post by machrider »

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 )

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

#55

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?

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

#57

Post by mshafrir »

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…

magnet program?

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

#58

Post by jrp »

jules wrote: post #45
jrp wrote: post #44

Earlier quoted context omitted.

OBS4 is supposed to be a list of all configurations which deny 4-colorability for themselves, and any strictly larger (in both dimensions) configurations. Ie, if (19,17) is in OBS4 then (19+x,17+y) is not 4-colorable either. So given a shape (x,y) or even a more funky collection of grid points like a triangle, to know if it's 4-colorable just check for all X in OBS4, if you can fit X inside your shape.

Got it, although the more interesting property is that smaller shapes than those in OBS are 4-colorable? (because it is trivially true that if nxk cannot be colored then larger shapes can't either).

Right, he has apparently solved and proved a short list for OBS3 with the property that X is 3-colorable if and only if X doesn't contain anything from OBS3.

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

#59

Post by scythe »

DarkShikari wrote: post #55
machrider wrote: post #54

Earlier quoted context omitted.

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

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.
Post reply on HN