You also need the condition that every point in the grid actually has a color. In your language that means that you have to replace your second set with:

"Second set of sets is comprised of all 4-tuples of 17-bit numbers which when ANDed together have no bits set and when ORed together have all bits set."

I don't see how this reformulation would help you solve the problem since these sets of sets are huge. You're also only exploiting the symmetries in one space direction, and you're not exploiting the symmetries in the colors. A better (and standard) way to go at it is to impose additional lexicographic ordering constraints. In addition to the constraints given by the problem you choose an ordering on the colors and add the constraint that row1 <= row 2 <= ... <= row17 where `<=` is the lexicographic ordering on 17-tuples. You do the same for columns and a similar thing for colors. That would (roughly) eliminate the following factor of grids:

      4! for the colors
    * 17! for the columns
    * 17! for the rows
    = 3.0 * 10^30

The total number of grids is:

    4^(17*17) = 9.9 * 10^173

So eliminating all those symmetries leaves us with:

    4^(17*17) / (4!17!17!) = 3.3 * 10^143

Your method only eliminates one of the 17! symmetries, so with your method you'd have to iterate over this many grids:

    4^(17*17) / 17! = 2.8 * 10^159

This is hardly trivially computable, but I'd still encourage you to try.

interestingly, the solution given is not ordered along rows or columns. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt

any idea why not?

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

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?

Oh, I read AND but was doing OR. My mistake.

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

I suspect something will go wrong, and this seems to me the obvious place for it to fail. But I expect it to fail mostly based on "if it was that easy, someone would probably have noticed", not because I have any particular insight into the problem.

I have a same gut feeling, but one of my professors told us how the discoveries are being made:

Everybody know that some thing is impossible to do. But one person who didn't know that accidentally does it.

Right now I have one type-1 set having 36 numbers in it. The first numbers are 7, 25 and 42. I like it.

And the first rule would be "the elements have no bits in common, but together (ORed) they have all 17 bits" That's almost XOR(i in S) = -1 but not really

i'm sorry people vote down interesting comments like yours. please don't be discouraged by the increasing stupidity around here - i, for one, welcome an interesting viewpoint, particularly if it acknowledges that it is wrong and wants to know why...

in short: you made me stop and think. thanks.