4 ms·

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

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?

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?