The 17x17 challenge. "Worth $289.00. This is not a joke." | Hacker News Reader

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

blog.computationalcomplexity.org

87 pointssp33272 comments

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.

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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?

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.

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

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

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

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.

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

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.

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

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.

Is the problem basically this game? http://www.kongregate.com/games/Mygame/blocky

i.e. find a grid where you can not make any moves in the game?

Yes

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 book he has online - it's quite interesting, and it goes into more detail about colorings and such, so anyone who likes this post will find the book interesting as well.

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

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

Huh? Is it naturally abstract?

The opportunity to work directly with a university professor while still in high school is fantastic. Wish I'd had it. I hope you ended up taking advantage of it with someone else. Even if you're not totally absorbed in the research, this will give you a huge leg up when you reach college.

Living near the University of Maryland and NIST and etc, there really are a bunch of opportunities to work with professors and researchers in high school - it's really quite great. I hope (slash think, but knock on wood) that I'm going to be able to work with either another math professor or a theoretical physicist over the summer. :)

magnet program?

Yup, it's the Montgomery Blair High School Magnet Program - it's in Silver Spring, Maryland. The funding cuts are kind of hurting it, but it's a very good education, especially if you put your own effort into it too.

(Are you, perhaps, somehow associated with this or another magnet program in the MD area?)

I graduated from the Magnet program in 2000.

I'm not the most mathy person in the world; can someone explain to me the following statement:

"Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17."

If I've understood it correctly, OBS4 is the set of grid-sizes which are impossible. But if 17x17 were impossible, surely the bigger ones would be too?

[Edit to answer my own question: the OBS4 set seems to be made up solely of the smallest such grid-sizes that can be given without being redundant.]

So if they say "Exactly one of a,b,c is in OBS4" then one of a,b,c is not 4-colorable?

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.

Took me a second to realize why 289. 17 * 17. One dollar per square. If you could get him to offer a prize for a 1000 * 1000 grid, you have quite a nice reward.

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.

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.

> That's difficult

Agreed, but that is why it would be worth $1M :-).

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

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

Sorry, misread the parent post.

Darn it. I thought this was a huge In & Out burger or something. I guess a math game is more logical and fitting for this forum.

Given the difficulty, should he not be offering more?

I think the cash is more symbolic than anything.

See: http://en.wikipedia.org/wiki/Knuth_reward_check

This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem

Did you read the article? These are actually quite different.

I'm pretty sure you haven't understood the problem. It's really nothing to do with the 4CT.

The 4 colour theorem is about colouring an arbitrary planar graph such that adjacent vertices have different colours.

The problem posed here is about colouring a 17x17 grid such that there is no monochromatic rectangle.

These problems have nothing in common aside from the word "colouring" and the number "4".

The problem isn't what you think it is, otherwise the solution would be trivial: alternate one pair of colors on even rows, and then alternate another pair on odd rows. That satisfies the four color theorem.

This problem differs in two ways.

First, we're not looking for all of the vertices to be different colors. We're looking for them to not all be the same color. This is easier to do.

Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do.

(To be fair, I made the same mistake on a first reading of the problem.)

I see now! I completely missed this part: "Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do."

Otherwise the problem seemed trivial.

On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

4^(17x17).

I think that's quite a few. Your mileage may vary based on the force available to you for bruting.

What a neat problem. I hadn't seen this before.

You don't need quite that many -- you could test 2^289 (and you can probably skip many of them) and look for the "rectangle free subsets" that he mentions in the slides, and then just look for four of them that don't overlap. Still gonna take eons.

how many possible 17x17 4-colored grids are there?

There's 289 points on the grid, and 4 options for each. So... 2^578 options.

Can this be brute forced?

That depends. Do you have a kilobit quantum computer available?

Hold on, let me check my other universe.

Um, no. The rectangles are aligned with the X and Y axes, so you choose two rows and two columns, giving 17C2x17C2 rectangles in total: 23409 possible rectangles.

He asked how many grids there were, not how many rectangles there were. :-)

Ah - sorry, my turn to do a misreading. As you point out, I computed the number of rectangles that aren't permitted to have all its vertices the same color.

My bad - sorry.

> On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

4^(17*17) ~= 10^173.. a bit too many to brute force, but I'm sure you could narrow the number down a lot with simple heuristics (though it would still be too large to brute force).

That's not the same problem. This refers to a grid (not a map) of colored points (not regions), colored with 4 colors (at least in this case) in which a rectangle with four same-colored points cannot be found.

Note that the second distinction you made is actually trivial. Coloring the vertices of a planar graph is the same problem as coloring the regions of a different planar graph. The graphs are duals:

http://en.wikipedia.org/wiki/Dual_graph

In this case, the dual of a grid is a grid. So at least that part of it would be the same problem. The other distinctions are true, though.

Of course you are right. I guess I pictured the 17x17=289 points forming 16x16=256 squares, which is why I felt it necessary to make the distinction.

Reply on news.ycombinator.com