# Binairo solutions

After seeing @stevon8ter post on Binairo, that got me thinking about the solutions for that type of puzzle. So here is a totally useless program that displays all of the solutions for a 6x6 puzzle. A 6x6 square can have 2^36 combinations of 0’s and 1’s. That was a little too many tries to go thru, so I just selected the valid combinations of 0’s and 1’s that worked for a single row. That turned out to be 14 combinations. So, using those 14 combinations on 6 rows amounts to 14^6 combinations or 7,529,536 tries, which was reasonable. So if you run this, it will go thru all 7,529,536 combinations and show 11,222 solutions. Of course there are less solutions or duplicates if you rotate a puzzle, but I’m not excluding those. The program is set up to stop after each solution, tap screen for next solution. Or you can slide “stop” to “off” and it will show each solution without stopping. All of the processing is done from draw(), so there will be times when the display doesn’t seem to be updating. That’s because it’s trying to find the next solution before exiting draw(), which will then update the display. After writing this, I tried an 8x8 puzzle. That has 2^64 combinations. I selected all of the combinations just for a single row, and that turned out to be 34. So 34^8 turned out to be 1,785,793,904,896 tries. That’s a little too many to do, so I gave up on that idea. If you turn “stop” to “off” and run this, it takes about 21 minutes to complete. I have a different way of doing this, so maybe the next time I have nothing better to do, I’ll try that and see if it’s faster.

EDIT: changed the code to eliminate duplicate rows or columns

``````
function setup()
parameter.boolean("stop",true)
print("Searching for a solution.")
print("\
When a solution is showing,")
print("tap the screen for the next")
print("solution. Some solutions may")
print("take several seconds before")
print("they show.")
print("\
\
Sliding the 'stop', parameter to")
print("'off' will show the solutions")
print("without stopping.")
done=false
solved=false
tries=0
solutions=0
colTab={}
tab={{0,0,1,0,1,1},{0,0,1,1,0,1},{0,1,0,0,1,1},{0,1,0,1,0,1},
{0,1,0,1,1,0},{0,1,1,0,0,1},{0,1,1,0,1,0},{1,0,0,1,0,1},
{1,0,0,1,1,0},{1,0,1,0,0,1},{1,0,1,0,1,0},{1,0,1,1,0,0},
{1,1,0,0,1,0},{1,1,0,1,0,0} }
tab1={1,1,1,1,1,1}
getBin()
end

function draw()
background(40,40,50)
fill(255)
if done then
text("Done",200,700)
else
while not solved do
tries=tries+1
if not done then
solve()
end
end
if not stop and solved then
solved=false
end
show()
end
text("Solution  "..solutions,200,650)
text("Tries  "..string.format("%d",tries),200,600)
end

function show()
c=0
for z=1,6 do
for y=1,6 do
c=c+1
text(tab2[c],100+y*40,500-40*z)
end
end
end

function solve()
if dupRows() then
return
end
if dupCol() then
return
end
for z=1,6 do
diff=0
zero=0
one=0
zeroes=0
ones=0
for y=1,6 do
if tab2[diff+z]==0 then
zero=zero+1
zeroes=zeroes+1
ones=0
if zeroes>2 or zero>3 then
return
end
else
one=one+1
ones=ones+1
zeroes=0
if ones>2 or one>3 then
return
end
end
diff=diff+6
end
if zero~=3 or one~=3 then
return
end
end
solved=true
solutions=solutions+1
end

function dupRows()
for x=1,6 do
for y=x,6 do
if x~=y then
if tab1[x]==tab1[y] then
return true
end
end
end
end
return false
end

function dupCol()
for z=1,6 do
dd=0
colTab[z]=0
for y=1,6 do
if tab2[dd+z]==1 then
colTab[z]=colTab[z]+2^(6-y)
end
dd=dd+6
end
end
for x=1,6 do
for y=x,6 do
if x~=y then
if colTab[x]==colTab[y] then
return true
end
end
end
end
return false
end

carry=0
for z=6,1,-1 do
tab1[z]=tab1[z]+1
if tab1[z]>#tab then
carry=1
tab1[z]=1
if z==1 then
done=true
solved=true
return
end
else
getBin()
return
end
end
end

function getBin()
tab2={}
for z=1,#tab1 do
for y=1,6 do
table.insert(tab2,tab[tab1[z]][y])
end
end
end

function touched(t)
if t.state==BEGAN then
solved=false
end
end

``````

@dave1707 nice to see there’s some interest in the binairo you dirty hacker xD

btw dave, this is a little algorithm to set all of the possible solutions of a single row

``````    solarr = {}

for c = 1, 3 do

table.insert(solarr, {})

d = (c + 2) * 2

for i = 0, 2^d do

if (op:bitcount(i) == d/2) then

if op:andd(op:orr(op:xor(i, 2*i, d), op:xor(i, math.floor(i/2), d), d), ((2^d)/2 - 2)) == ((2^d)/2 -2) then
table.insert(solarr[c], i)
end

end

end

end
``````

the for loop containing ‘c’ is only set to loop 3 times

if you take a closer look, you’ll see that it means it calculates rows (and columns, since columbs have same conditions as rows) for 6x6, 8x8 and 10x10

in my first versions, i set them to 7 since there were 18x18 tho that took a long time to start so i hardcoded them into my program

However, this algorithm only show the solutions in decimals…
in a 6x6 this would mean:

``````0 = 000000
1 = 000001
2 = 000010
10 = 001010
etc etc
``````

I’m sure you could work with these as well, and maybe filter some more solutions out (there may not be 2 rows that are the same… ) (same for columns)

Maybe even a performance upgrade… but i doubt that

In general, nice to see such a thing, well done, some wonderful programming from your side… again… as usual xD

@stevon8ter I’m not sure what your routine does. Too many and’s, xor’s, or’s, in the one if statement to work it out. I tried to run it, but I don’t have the op: routines. In my program, in the tab table, are the 14 combinations that are valid for a row of a 6x6 puzzle. I just take every combination of those 14 and put them in all 6 rows and then check each column for a valid result.

@dave1707 i forgot i used my bitmath operations xD

And with valid result… you also mean you check for duplicates? I mean duplicates withing the rows, and duplicates within the columns…?

@stevon8ter No, I don’t check for duplicates. The only thing I check for in the 6x6 puzzle is that there are three 0’s and three 1’s, and there are no more than two 0’s or two 1’s together in each row and each column. I’ll have to find or write some bit operaters so I can run your code.

@dave1707 i’ll post mine in a minute

but you should check for more than just the two 0’s and two 1’s

in a binairo, no 2 rows or columns can be the same

no 2 rows could be for exalple 010011 (same for columns)
however… 1 row and 1 column may be the same (and this multiple times, as long as no rows are the same, and as long as no columns are the same)

edit:

``````op = class()

function op:init()

end

function op:andd(a, b)
c = 0
for i = 0, 50 do
c = c + (a%2) * (b%2) * (2^i)

a = math.floor(a/2)
b = math.floor(b/2)
end

return c

end

function op:nott(a, b)
return 2^b - 1 - a
end

function op:orr(a, b, c)
return op:nott(op:andd(op:nott(a, c), op:nott(b,c)), c)
end

function op:xor(a,b , c)
return op:andd(op:orr(a,b,c), op:nott(op:andd(a,b), c))
end

function op:bitcount(x)
bitcoun = 0

while x ~= 0 do
bitcoun = bitcoun + (x % 2)
x = math.floor(x/2)
end

return bitcoun

end
``````

@stevon8ter I didn’t realize that 2 rows or 2 columns can’t be the same. I was just going by what I saw in puzzles and that was the 1 and 0 had to be the same count and there couldn’t be more than 2 together. I should have looked up the rules. I guess I’ll have to rewrite my code above. I’ll run your code and see what I get.

@dave1707 don’t worry, you still had a nice program, showing alot of solutions already

As for the code above, you only need to set the first for loop to 1, since you only need 6x6 puzzles, and it would just store your 14 solutions… but in decimals…

@Stevon8ter I wrote something that gave me what I have in the table tab. It’s basically the same 14 values you got in your 1st table, but I printed mine in 0’s and 1’s. I was using the decimal values in my first try, but the program ran faster when I changed it to use 0’s and 1’s. As for my program above, it still displays all of the solutions, but also some that I shouldn’t. I guess it will be interesting to see how many solutions shouldn’t be displayed.

@stevon8ter Forgot to mention, thanks for the bit functions.

@dave1707 no problem, and ok, didn’t know the performance wa faster with the 0’s and 1’s , but as always, you got the better coding skills

@stevon8ter I added code to eliminate duplicate rows and columns. The number of solutions went from 11,222 down to 4,140. Once I check the code to make sure it’s now correct, I’ll replace the above code.

Wow that reduced the possible solutions by alot

i’m curious how you generate the starting configuration of the puzzle, given that it should be solvable at each step based on logic and not guessing?

Well how i make the puzzles: I program them in manually, but later on I’m going to create a random generator… Tho I will get help from someone else, who did this on his calculator… So he’s going to explain it to me, and I’m going to try understand it and recreate it in lua

@piinthesky I’m not guessing when I look for a solution. The way the code is set up, I check all combination for a valid solution. That’s similar to finding all the 2 digit numbers that have both digits the same (11,22,33,etc). You would start at 10 and see if both digits are the same. If they are you have a solution. If not then you add 1 and check again. You keep doing that until you reach 99. In the table tab in the code above, I have 14 combinations of 0’s and 1’s that are valid solutions for a row. Then in table tab1, I have the starting table offsets that I use for table tab. Table tab1 start out as 1,1,1,1,1,1… So my first check is the 1st offset for all six rows. I check for the correct combinations of 0’s and 1’s in the 6 columns. If there isn’t a valid solution, I add 1 to a position in tab1. I continue to do that. When a position is greater than 14, I set it back to 1, and add 1 to the next position, and so on. It similar to the odometer in a car, but instead of each position going to 9, this goes to 14. So I start out at 1,1,1,1,1,1 then 1,1,1,1,1,2 then 1,1,1,1,1,3 and I check each combination until I reach 14,14,14,14,14,14.

i notice the binary sudoku app on the appstore, introduces a time penalty if you enter the wrong number in the box.

A version on the web, lets one toggle between 1 or 0 as you tap on the box- saves having to select the 1 or o explictly.

Yeah I also saw a version that toggles the numbers, I think I’ll implement that method once I get some spare time, but i still have alot of stuff to do when I get some time, so idk if i’ll work on it in the near future, it could take another month or two