6 ms·
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 acco
by RiderOfGiraffes 17y ago
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.
- Retric 17y agoThis 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.
- xenophanes 17y agocounting 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.
- Retric 17y agoI 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.
- xenophanes 17y agohow 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
- Retric 17y agoOk, 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.
- xenophanes 17y ago> 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.
- Retric 17y agoYes, 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.
- JabavuAdams 17y agoSee, that's the thing about really big numbers. 10% of 10^174 is still 10^173.
- Retric 17y agoIt'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.
- RiderOfGiraffes 17y agoAlthough 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.
- Retric 17y agoThere 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.
- abentspoon 17y agoYou 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.
- scythe 17y agoI'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 http://ctrl-v.org/3708
- DarkShikari 17y agoI 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 http://pastebin.com/m51149dd9 )
- machrider 17y agoOut of curiosity, what's the lowest score you've seen on 17x17 so far?
- DarkShikari 17y agoI 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 http://pastebin.com/m63191b11
- scythe 17y agoTry just placing 73 1's. You need to be able to place that many, but I can't get more than 65.
- RiderOfGiraffes 17y agoI'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.