20170224, 19:32  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,951 Posts 
Binaris 1001
I have been playing a puzzle game on my tablet lately. The aim is to fill in the grid with 0s and 1s such that 3 conditions are met:
1. There can be at most two 0s or 1s next to one another. 2. Each row and column should contain an equal number of zeros and ones. 3. Any two rows or any two columns can't be completely the same. Rule two indicates that the boards have an even size. I have been thinking about how many possible grids there are. Rule two isn't that hard to implement and I got some way to thinking about one. Can anyone work out have many valid 4x4 or 6x6 grids there are as solutions to this puzzle? Last fiddled with by henryzz on 20170224 at 19:33 
20170224, 20:12  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
4 by 4 has these 16 ( prior to the rules, red are eliminated by rule 1):
and a 6 by 6 has 64 possible combinations before rules. depending on the interpretation of rule 2 ( if all rows and columns need say 2 ones and 2 zeroes for example, versus say half are ones and half are 0's in each) even more could be eliminated. and the third rule is more about the order of rows I think because a different ordering of the rows could change what numbers the columns represent. so you might get to use 1100,1010,1001,0101,0011 and try to combine then if the equal number of ones and zeroes are in each row separately or not. 

20170224, 20:55  #3  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3×1,951 Posts 
Quote:
Not sure what you are saying about rule 2. If a row has 4 numbers then it needs 2 0s and 2 1s. This sort of logic will only get you so far. You wouldn't be able to do much beyond a 6x6. 

20170224, 21:39  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
14 remain to go through rule three. 

20170225, 00:07  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,951 Posts 
Ok so 6x6 is possible using that brute force method. What about 8x8, 10x10, 12x12, nxn?

20170225, 00:29  #6 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
well in general there won't be at most 2 leading zero's until you hit 2^(n3) ( first time the 3rd place from the left gets filled) I think you'll find so a great deal of possible binary strings of length n can already be deleted. so already you can toss out 1/16 of all binary strings already. PS ( changed the exponent later) but then you can figure out when a third of the places have 1's by repeating the pattern.
Last fiddled with by science_man_88 on 20170225 at 00:55 
20170225, 02:43  #7 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
oh and because you can switch all 0s to 1s and all 1s to 0s we know there will be an even number of solutions at least to each row. and we know a structure they may have using this plus hamming weight you can already cut the n=24 case down to 1800 or so without testing any more properties. edit: sorry 3600 when you flip the 1s and 0s but that's a lot less than 2^241. edit2: 3418 and probably falling now.
Last fiddled with by science_man_88 on 20170225 at 02:46 
20170315, 17:03  #8 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011011101_{2} Posts 
I have just coded a solution generator in c#.
This told me that there are 72, solutions for 4x4, 4140 solutions for 6x6 and 4111116 solutions for 8x8. Putting 4111116 in the oeis turned up https://oeis.org/A253316 which gives me another name for the puzzle. I think that the general consensus online seems to be that an exact formula isn't even known with just the first rule ignoring the others. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Team drive #14: k=6001001 n=1M2M  mdettweiler  No Prime Left Behind  10  20210313 22:32 
k=10011399  pb386  Riesel Prime Search  26  20160530 12:10 
Team drive #7 k=8001001 n=600K1M  gd_barnes  No Prime Left Behind  127  20110715 14:25 
GPU sieving drive for k<=1001 n=1M2M  mdettweiler  No Prime Left Behind  11  20101004 22:45 
Sieving. 300<k<=1001, n=600K1M.  Lennart  No Prime Left Behind  30  20080901 08:51 