6 ms·

The 17x17 problem solved

120 points by DanielRibeiro 15y ago

jameskilton 15y ago
For those of us who are confused what "monochromatic rectangles" actually means, this article shows it perfectly: http://mathlesstraveled.com/2012/02/09/17x17-4-coloring-with-no-monochromatic-rectangles/ http://mathlesstraveled.com/2012/02/09/17x17-4-coloring-with...
- Natsu 15y ago
  The example they give of randomly changing one coloring and getting a whole bunch of rectangles makes me wonder if there are any points in that coloring that you could change without destroying the solution. I doubt there are any, but it probably wouldn't take that long to write a program to check... EDIT: And after reading this, I'm starting to wonder about other ways to use this solution to search for others, such as swapping two colors: http://bit-player.org/2009/17-x-17-a-nonprogress-report http://bit-player.org/2009/17-x-17-a-nonprogress-report
  - Retric 15y ago
    That's interesting, last time this came around I started working though how to do it using a Sudoku style solver. Step 1: If a solution exists it's going to have 4!(17!)^2 'mirror' images of the same solution. To avoid this problem we give each color a number and a specific ordering of the solution. Thus eliminating 4!(17!)^2 - 1 options. Step 2: Based on the form that order takes we fill in the grid as much as possible. (Most of the top and side row). Step 3: Start plugging in missing squares until you find contradictions. EX: If swapping a column gives a lower ordering it's not a valid solution.
  - eichin 15y ago
    Took about 20 minutes to write some python code to search; takes about 1/3 of a second to try all 3x17x17 mutations and find at least one rectangle produced by each. So yeah, every single-point change "destroys" the solution.
- guard-of-terra 15y ago
  Do I understand correctly that you can shuffle the image's rows (or columns) without losing that effect? That would dramatically reduce the amount of computations we need to perform in order to find a match. Basically we are looking for a system of two sets of sets of 17-bit numbers. First set of sets is comprised of all sets of 17-bit numbers which when ANDed to each other yield a number with no more than one bit set. Second set of sets is comprised of all sets of 17-bit numbers which do not have any common bits set. Then from those sets we should draw a 17 4-tuples of 17-bit numbers where: every tuple is a subset of one of the sets in the second set every set of i-elements of tuples is a subset of one of the sets on the first set. Sounds trivially computable on modern hardware to me! I'm sure that I'm wrong, but where?
  - philh 15y ago
    > Do I understand correctly that you can shuffle the image's rows (or columns) without losing that effect? Yes, but a dramatic reduction in complexity still leaves a lot of complexity. Your conditions seem to be a lot simpler than they originally appear. If I interpret you correctly, we're drawing seventeen 4-tuples of seventeen-bit numbers such that > every tuple is a subset of one of the sets in the second set "the elements of each tuple have no bits in common", and > every drawn number is contained in one of sets in the first set "each number has at most one bit set". But there are only eighteen seventeen-bit numbers with at most one bit set, or seventeen if you exclude 0 (which seems reasonable). So isomorphically, we're trying to find seventeen 4-tuples of distinct numbers less than seventeen. This is indeed easy (there are (17 choose 4) = 2380 of them), but I don't understand what you hope to do with these. At any rate, I don't think they particularly help solve the problem at hand.
    - guard-of-terra 15y ago
      Nope, the second condition would be "each i-number is from a set where no two numbers share more than one common bit" You can pre-compute that set of sets (of course throwing away numbers with just 0, 1 or 2 bits set because we suspect they would slow us down without delivering) fit them in memory and then crunch the problem like a bug. I've thrown together two simple scripts (in perl) which show that the known solution fits both of my rules. Hopefully I can write a program that would find solutions for any given NxM (or tell that no solution exists) tomorrow or something like that. Still I suspect the solution would hit the wall because e.g. sets would be too big therefore the program would take actual ages to run, but one can surely hope?
ntkachov 15y ago
Aside from being just interesting, Does this have and applications? It seems like it might have some applications in data structuring but is this just a math problem or are there actually people who are waiting on the solution?
- kylemaxwell 15y ago
  I don't know if anyone has been waiting on this specific result for an application, but in general graph coloring has lots of applications[1]. Also, mathematical advances often predate their applications (sometimes by a very long time). Not to mention that we know something know we didn't know before, and that's always worthwhile. [1]: http://en.wikipedia.org/wiki/Graph_coloring#Applications http://en.wikipedia.org/wiki/Graph_coloring#Applications
sp332 15y ago
Lots of discussion from when the challenge was issued a couple years back: https://news.ycombinator.com/item?id=968577 https://news.ycombinator.com/item?id=968577
pavel_lishin 15y ago
I'd really like to hear more about why this was not a trivial challenge.
- mvzink 15y ago
  This post explains the problem enough to give an intuitive understanding of why it's difficult: http://bit-player.org/2009/the-17x17-challenge http://bit-player.org/2009/the-17x17-challenge
- cheald 15y ago
  Short answer: 4^(17*17) combinations to try, and each combination requires an expensive test before you can pass/fail it. Plug that number into Wolfram Alpha alongside things like "age of the universe" for some perspective on just how massive the search space is.
  - rorrr 15y ago
    The search space a lot smaller, since you can cut many incorrect branches very early.
    - cheald 15y ago
      Yes, but as noted in the post mvzink linked, you can't cut it to the point that an exhaustive search is feasible.
ColinDabritz 15y ago
"I asked them if they did it for the money (which I doubted). No, but the money made them more aware of the problem." "The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!" This strikes me as an excellent opportunity to use KickStarter to amplify interest. If the people interested in 12x21 kicked in even $10 each, you could have a noticeable prize. Perhaps this would be a good way to focus attention on certain problems?
- cgag 15y ago
  I was thinking the same thing. I love the idea of using something like kick starter to publicly fund prizes for math / science, not necessarily related to 4-color rectangles.
  - ColinDabritz 15y ago
    You'd have to be careful about it, and have clear rules about who holds it and when the reward is given out. You could conceivably fund research that way as well, such as things that big business or the government shy away from, but has popular demand or value. It sounds approachable.
- eridius 15y ago
  If the problem is not solvable, then nobody can claim the prize. I'm not really familiar with Kickstarter's rules, but I'd imagine they might take issue with a Kickstarter project where it's possible that the money can't actually be used for anything.
  - ColinDabritz 15y ago
    An excellent point, along with 'who holds the money?' and 'is the money invested in the mean time?' I think it could be addressed with a reasonable fallback, such as a math related charity after 20 years or some such. Or if you could make it possible to start awarding 'best tempt' partial payouts. There are certainly some complications involved, but it still seems workable to me overall. Perhaps partner with a well-known prize-giving organization.
endtime 15y ago
>The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Is this a typo for 21x21? If not, then presumably 21x21 is known to be 4-colorable...and it seem to me that removing a column from the edge* of a 4-colored grid results in another 4-colored grid (since the resulting subgrid couldn't have contained any MRs if the original grid didn't)...so a 12x21 4-colored grid should result from removing nine columns from a 21x21 such grid. I don't actually think the above solves the problem - rather, I must be misunderstanding it. Can someone explain how? *The column doesn't have to be from the edge, but it's a sufficient claim, and is easier to see...I couldn't be bothered to write the small proof that removing a column from the middle works.
- jbri 15y ago
  It's also possible to mathematically prove that certain grids are not 4-colorable.
  - endtime 15y ago
    Ah, thank you. And also, duh.
- panic 15y ago
  Your argument only works if the 21x21 grid is known to be 4-colorable. But in fact, the 21x21 grid is known not to be 4-colorable.
  - deleted 15y ago
    [deleted]
experiment0 15y ago
Best way of finding if there are rectangles: > We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if at least two bits are set in the resulting vector. -- http://bit-player.org/2009/the-17x17-challenge http://bit-player.org/2009/the-17x17-challenge Thats some lovely hacking.
sebastianavina 15y ago
can someone explain me why this problem is important? or it just happens to be another problem to be solved?
kcl 15y ago
Wrote this up in response to the renewed attention to the problem: 17x17 is NP-Complete: http://hackerne.ws/item?id=3584732 http://hackerne.ws/item?id=3584732
akawry 15y ago
Tried to apply a genetic algorithm to arrive at a solution: https://gist.github.com/1820794 https://gist.github.com/1820794. Doesn't work too well just yet; maybe someone can take a look/play around with it/give me some pointers :)

120 points by DanielRibeiro 15y ago

For those of us who are confused what "monochromatic rectangles" actually means, this article shows it perfectly: http://mathlesstraveled.com/2012/02/09/17x17-4-coloring-with-no-monochromatic-rectangles/ http://mathlesstraveled.com/2012/02/09/17x17-4-coloring-with...

Natsu 15y ago
The example they give of randomly changing one coloring and getting a whole bunch of rectangles makes me wonder if there are any points in that coloring that you could change without destroying the solution. I doubt there are any, but it probably wouldn't take that long to write a program to check... EDIT: And after reading this, I'm starting to wonder about other ways to use this solution to search for others, such as swapping two colors: http://bit-player.org/2009/17-x-17-a-nonprogress-report http://bit-player.org/2009/17-x-17-a-nonprogress-report
- Retric 15y ago
  That's interesting, last time this came around I started working though how to do it using a Sudoku style solver. Step 1: If a solution exists it's going to have 4!(17!)^2 'mirror' images of the same solution. To avoid this problem we give each color a number and a specific ordering of the solution. Thus eliminating 4!(17!)^2 - 1 options. Step 2: Based on the form that order takes we fill in the grid as much as possible. (Most of the top and side row). Step 3: Start plugging in missing squares until you find contradictions. EX: If swapping a column gives a lower ordering it's not a valid solution.
- eichin 15y ago
  Took about 20 minutes to write some python code to search; takes about 1/3 of a second to try all 3x17x17 mutations and find at least one rectangle produced by each. So yeah, every single-point change "destroys" the solution.
guard-of-terra 15y ago
Do I understand correctly that you can shuffle the image's rows (or columns) without losing that effect? That would dramatically reduce the amount of computations we need to perform in order to find a match. Basically we are looking for a system of two sets of sets of 17-bit numbers. First set of sets is comprised of all sets of 17-bit numbers which when ANDed to each other yield a number with no more than one bit set. Second set of sets is comprised of all sets of 17-bit numbers which do not have any common bits set. Then from those sets we should draw a 17 4-tuples of 17-bit numbers where: every tuple is a subset of one of the sets in the second set every set of i-elements of tuples is a subset of one of the sets on the first set. Sounds trivially computable on modern hardware to me! I'm sure that I'm wrong, but where?
- philh 15y ago
  > Do I understand correctly that you can shuffle the image's rows (or columns) without losing that effect? Yes, but a dramatic reduction in complexity still leaves a lot of complexity. Your conditions seem to be a lot simpler than they originally appear. If I interpret you correctly, we're drawing seventeen 4-tuples of seventeen-bit numbers such that > every tuple is a subset of one of the sets in the second set "the elements of each tuple have no bits in common", and > every drawn number is contained in one of sets in the first set "each number has at most one bit set". But there are only eighteen seventeen-bit numbers with at most one bit set, or seventeen if you exclude 0 (which seems reasonable). So isomorphically, we're trying to find seventeen 4-tuples of distinct numbers less than seventeen. This is indeed easy (there are (17 choose 4) = 2380 of them), but I don't understand what you hope to do with these. At any rate, I don't think they particularly help solve the problem at hand.
  - guard-of-terra 15y ago
    Nope, the second condition would be "each i-number is from a set where no two numbers share more than one common bit" You can pre-compute that set of sets (of course throwing away numbers with just 0, 1 or 2 bits set because we suspect they would slow us down without delivering) fit them in memory and then crunch the problem like a bug. I've thrown together two simple scripts (in perl) which show that the known solution fits both of my rules. Hopefully I can write a program that would find solutions for any given NxM (or tell that no solution exists) tomorrow or something like that. Still I suspect the solution would hit the wall because e.g. sets would be too big therefore the program would take actual ages to run, but one can surely hope?

ntkachov 15y ago

Aside from being just interesting, Does this have and applications? It seems like it might have some applications in data structuring but is this just a math problem or are there actually people who are waiting on the solution?

kylemaxwell 15y ago
I don't know if anyone has been waiting on this specific result for an application, but in general graph coloring has lots of applications[1]. Also, mathematical advances often predate their applications (sometimes by a very long time). Not to mention that we know something know we didn't know before, and that's always worthwhile. [1]: http://en.wikipedia.org/wiki/Graph_coloring#Applications http://en.wikipedia.org/wiki/Graph_coloring#Applications

sp332 15y ago

Lots of discussion from when the challenge was issued a couple years back: https://news.ycombinator.com/item?id=968577 https://news.ycombinator.com/item?id=968577

pavel_lishin 15y ago

I'd really like to hear more about why this was not a trivial challenge.

mvzink 15y ago
This post explains the problem enough to give an intuitive understanding of why it's difficult: http://bit-player.org/2009/the-17x17-challenge http://bit-player.org/2009/the-17x17-challenge
cheald 15y ago
Short answer: 4^(17*17) combinations to try, and each combination requires an expensive test before you can pass/fail it. Plug that number into Wolfram Alpha alongside things like "age of the universe" for some perspective on just how massive the search space is.
- rorrr 15y ago
  The search space a lot smaller, since you can cut many incorrect branches very early.
  - cheald 15y ago
    Yes, but as noted in the post mvzink linked, you can't cut it to the point that an exhaustive search is feasible.

ColinDabritz 15y ago

"I asked them if they did it for the money (which I doubted). No, but the money made them more aware of the problem." "The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!" This strikes me as an excellent opportunity to use KickStarter to amplify interest. If the people interested in 12x21 kicked in even $10 each, you could have a noticeable prize. Perhaps this would be a good way to focus attention on certain problems?

cgag 15y ago
I was thinking the same thing. I love the idea of using something like kick starter to publicly fund prizes for math / science, not necessarily related to 4-color rectangles.
- ColinDabritz 15y ago
  You'd have to be careful about it, and have clear rules about who holds it and when the reward is given out. You could conceivably fund research that way as well, such as things that big business or the government shy away from, but has popular demand or value. It sounds approachable.
eridius 15y ago
If the problem is not solvable, then nobody can claim the prize. I'm not really familiar with Kickstarter's rules, but I'd imagine they might take issue with a Kickstarter project where it's possible that the money can't actually be used for anything.
- ColinDabritz 15y ago
  An excellent point, along with 'who holds the money?' and 'is the money invested in the mean time?' I think it could be addressed with a reasonable fallback, such as a math related charity after 20 years or some such. Or if you could make it possible to start awarding 'best tempt' partial payouts. There are certainly some complications involved, but it still seems workable to me overall. Perhaps partner with a well-known prize-giving organization.

endtime 15y ago

>The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Is this a typo for 21x21? If not, then presumably 21x21 is known to be 4-colorable...and it seem to me that removing a column from the edge* of a 4-colored grid results in another 4-colored grid (since the resulting subgrid couldn't have contained any MRs if the original grid didn't)...so a 12x21 4-colored grid should result from removing nine columns from a 21x21 such grid. I don't actually think the above solves the problem - rather, I must be misunderstanding it. Can someone explain how? *The column doesn't have to be from the edge, but it's a sufficient claim, and is easier to see...I couldn't be bothered to write the small proof that removing a column from the middle works.

jbri 15y ago
It's also possible to mathematically prove that certain grids are not 4-colorable.
- endtime 15y ago
  Ah, thank you. And also, duh.
panic 15y ago
Your argument only works if the 21x21 grid is known to be 4-colorable. But in fact, the 21x21 grid is known not to be 4-colorable.
- deleted 15y ago
  [deleted]

experiment0 15y ago

Best way of finding if there are rectangles: > We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if at least two bits are set in the resulting vector. -- http://bit-player.org/2009/the-17x17-challenge http://bit-player.org/2009/the-17x17-challenge Thats some lovely hacking.

sebastianavina 15y ago

can someone explain me why this problem is important? or it just happens to be another problem to be solved?

kcl 15y ago

Wrote this up in response to the renewed attention to the problem: 17x17 is NP-Complete: http://hackerne.ws/item?id=3584732 http://hackerne.ws/item?id=3584732

akawry 15y ago

Tried to apply a genetic algorithm to arrive at a solution: https://gist.github.com/1820794 https://gist.github.com/1820794. Doesn't work too well just yet; maybe someone can take a look/play around with it/give me some pointers :)