mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2017-02-24, 19:32   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

32·631 Posts
Default 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 2017-02-24 at 19:33
henryzz is online now   Reply With Quote
Old 2017-02-24, 20:12   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-02-24, 20:55   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

10110001011112 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
henryzz is online now   Reply With Quote
Old 2017-02-24, 21:39   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-02-25, 00:07   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

130578 Posts
Default

Ok so 6x6 is possible using that brute force method. What about 8x8, 10x10, 12x12, nxn?
henryzz is online now   Reply With Quote
Old 2017-02-25, 00:29   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.

Last fiddled with by science_man_88 on 2017-02-25 at 00:55
science_man_88 is offline   Reply With Quote
Old 2017-02-25, 02:43   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

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.

Last fiddled with by science_man_88 on 2017-02-25 at 02:46
science_man_88 is offline   Reply With Quote
Old 2017-03-15, 17:03   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

32×631 Posts
Default

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.
henryzz is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
k=1001-1399 pb386 Riesel Prime Search 26 2016-05-30 12:10
Team drive #14: k=600-1001 n=1M-2M mdettweiler No Prime Left Behind 9 2014-09-02 01:21
Team drive #7 k=800-1001 n=600K-1M gd_barnes No Prime Left Behind 127 2011-07-15 14:25
GPU sieving drive for k<=1001 n=1M-2M mdettweiler No Prime Left Behind 11 2010-10-04 22:45
Sieving. 300<k<=1001, n=600K-1M. Lennart No Prime Left Behind 30 2008-09-01 08:51

All times are UTC. The time now is 18:35.

Thu Jul 9 18:35:40 UTC 2020 up 106 days, 16:08, 1 user, load averages: 4.72, 2.46, 1.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.