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?
"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
4^(17*17) = 9.9 * 10^173
4^(17*17) / (4!17!17!) = 3.3 * 10^143
4^(17*17) / 17! = 2.8 * 10^159
any idea why not?
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.
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?
> 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.
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.
in short: you made me stop and think. thanks.
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:
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.
"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?
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.
Obviously the non-existence of a solution might itself be unprovable, so you'd still have to set some time limit. Oh Gödel, always there to ruin our plans.
> 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.
Thats some lovely hacking.
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.
Doesn't work too well just yet; maybe someone can take a look/play around with it/give me some pointers :)
17x17 is NP-Complete: http://hackerne.ws/item?id=3584732
or it just happens to be another problem to be solved?