Binaris 1001

[henryzz]

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?

[science_man_88]

Originally Posted by henryzz

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?

in an n by n grid there's at most 2^n strings that can form the columns and rows:

4 by 4 has these 16 ( prior to the rules, red are eliminated by rule 1):

1. 0000
2. 0001
3. 0010
4. 0011
5. 0100
6. 0101
7. 0110
8. 0111
9. 1000
10. 1001
11. 1010
12. 1011
13. 1100
14. 1101
15. 1110
16. 1111

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.

[henryzz]

Originally Posted by science_man_88

in an n by n grid there's at most 2^n strings that can form the columns and rows:

4 by 4 has these 16 ( prior to the rules, red are eliminated by rule 1):

1. 0000
2. 0001
3. 0010
4. 0011
5. 0100
6. 0101
7. 0110
8. 0111
9. 1000
10. 1001
11. 1010
12. 1011
13. 1100
14. 1101
15. 1110
16. 1111

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.

You missed 0110 in your final list.
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.

[science_man_88]

Originally Posted by henryzz

You missed 0110 in your final list.
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.

Thanks for the missed one. What I'm saying is saying equal number of 0's or 1's doesn't cut it except now that I realize it's a singular row or column it's talking about it could be saying something like all rows have 3 ones and all columns have 3 ones. anyways I'm clearly misinterpreting things. for a 6 by 6 you have ( using your interpretation of rule 2):

1. 000000
2. 000001
3. 000010
4. 000011
5. 000100
6. 000101
7. 000110
8. 000111
9. 001000
10. 001001
11. 001010
12. 001011
13. 001100
14. 001101
15. 001110
16. 001111
17. 010000
18. 010001
19. 010010
20. 010011
21. 010100
22. 010101
23. 010110
24. 010111
25. 011000
26. 011001
27. 011010
28. 011011
29. 011100
30. 011101
31. 011110
32. 011111
33. 100000
34. 100001
35. 100010
36. 100011
37. 100100
38. 100101
39. 100110
40. 100111
41. 101000
42. 101001
43. 101010
44. 101011
45. 101100
46. 101101
47. 101110
48. 101111
49. 110000
50. 110001
51. 110010
52. 110011
53. 110100
54. 110101
55. 110110
56. 110111
57. 111000
58. 111001
59. 111010
60. 111011
61. 111100
62. 111101
63. 111110
64. 111111

14 remain to go through rule three.

[henryzz]

Ok so 6x6 is possible using that brute force method. What about 8x8, 10x10, 12x12, nxn?

[science_man_88]

Originally Posted by henryzz

Ok so 6x6 is possible using that brute force method. What about 8x8, 10x10, 12x12, nxn?

well in general there won't be at most 2 leading zero's until you hit 2^(n-3) ( 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.

[science_man_88]

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^24-1. edit2: 3418 and probably falling now.

[henryzz]

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.