Binary Puzzle Solver

Question

Introduction

Rules of the puzzle:

The puzzle Binary (also known as Takuzu or Subiku) is very simple to understand, and has only a few rules:
Since the name of the game is binary it's pretty obvious, but you can only fill in zeros and ones.

1. No more than two of the same digit can be vertically or horizontally adjacent to each other
2. Each row and each column must contain an equal amount of zeros and ones (this implicitly means every binary game will always have even dimensions).
3. There may be no duplicated rows and no duplicated columns (with the exact same order of zeros and ones).

You can play the game at www.binarypuzzle.com if you want to.

Tactics:

Due to rule 1, we can always fill in a digit if:
- There are already two of the same digit vertically or horizontally adjacent to each other, in which case we can fill in the opposite digit at both sides. I.e. .11... → 0110...
- There are two of the same digit vertically or horizontally with only one gap in between them. I.e. .1.1.. → .101..

Due to rule 1, when three gaps are left and we cannot have three adjacent of the same digit, we can fill in one of the gaps. I.e. .0.1.0 → 10.1.0 (We still have to fill in two ones, and we cannot have three adjacent ones in the middle, so the first gap has to be a 1.)

Due to rule 2, we can always fill in the remaining gaps in a row or column if halve of them is already filled in with the opposite digit. I.e. .1.011 → 010011

Due to rule 3, we can always fill in the opposite digits if only two are left to solve on an equally ordered line. I.e. 101100 & 1..100 → 101100 & 110100

Due to rule 3, we can sometimes fill in a gap when three gaps are left on an equally ordered line. I.e. 010011 & .1.01. → 010011 & .1.010 (Here we cannot fill in a 1 at the end, because that would mean we have to fill in zeros at the other two gaps, making both lines equal in order.)

Example:

We start with the following 6x6 grid with some ones and zeros filled in (and the dots are gaps we have yet to fill in):

.1....
.10.0.
1.11..
.1....
...1.0
......

Due to rules 1 & 2 we can fill in these digits:

.1.01.
.1010.
101100
010011
.0.1.0
.010..

Due to rule 1 we can fill in a 1 at row 5, column 1:

.1.01.
.1010.
101100
010011
10.1.0
.010..

Due to rule 3 we can fill in a 0 at row 1, column 6 (when looking at row 4):

.1.010
.1010.
101100
010011
10.1.0
.010..

Now we can continue to fill gaps with digits due to rules 1 & 2:

.1.010
010101
101100
010011
10.1.0
.010.1

Now we can finish row 5 due to rule 3 (when looking at row 3):

.1.010
010101
101100
010011
100110
.010.1

And then we can finish the puzzle due to rules 1 & 2:

011010
010101
101100
010011
100110
101001

Challenge:

The challenge is simply: given the starting grid, output the solved puzzle.

NOTE: You don't have to implement the rules above. You of course can, and it should give you hints on how to implement this challenge, but bruteforcing the solution with the rules in mind is completely fine.
How you solve it is up to you, but the challenge is to output the solved puzzle.

Challenge rules:

• Input and output format for the grid is flexible, but please state what you use. (I.e. 2D byte-array; String with newlines; etc.)
• This above also applies to the characters used. In the example I've used 01., but if you want you can use ABx instead. Please state what input/output format and characters you've used.
• You can assume only the following grid sizes will be used: 6x6; 8x8; 10x10; 12x12; 14x14; 16x16.

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code.
• Also, please add an explanation if necessary.

Test cases:

The dots are only added for readability, feel free to use spaces or anything else you prefer for gaps instead. Both in and output format is flexible.

Input:
1..0..
..00.1
.00..1
......
00.1..
.1..00

Output:
101010
010011
100101
011010
001101
110100

Input:
.1....
.10.0.
1.11..
.1....
...1.0
......

Output:
011010
010101
101100
010011
100110
101001

Input:
.......1..
.00..0..1.
.0..1..0.0
..1...1...
1.1......1
.......1..
.0..1...0.
....11...0
.0.0..1..0
0...0...1.

Output:
0110010101
1001100110
1001101010
0110011001
1010100101
0101010110
1001101001
0110110100
1010011010
0101001011

Answer 1

Brachylog, 34 bytes

{ℕ<2}ᵐ²&≜{d?ọᵐctᵐ=&{ḅlᵐ⌉<3}ᵐ}&\↰₂&

Try it online!

This is pretty damn slow, so the test case on TIO is 4x4. I am currently running the 6x6 test case on my computer to see how much time it takes.

This takes a list of lists as input. The unknown values should be indicated with variables, that is with all-uppercase strings (and they should all be different, as otherwise you would be indicating that some cells must have the same value)

Explanation

We constrain the values to be in {0,1}, then we try instantiations of the variables until one respects all 3 rules. This is why this is so slow (because it will try all of them until finding one; and because in that case Brachylog is not implemented well enough so that constraints can be imposed before trying a possible matrix).

                                 &  Output = Input
{   }ᵐ²                             Map two levels on the Input (i.e. each cell):
 ℕ<2                                  The cell is either 0 or 1
       &≜                           Assign values to all cells
         {                  }       Define predicate 2:
          d?                          The Input with no duplicates is still the Input
                                        (i.e. all rows are different)
           ?ọᵐctᵐ=                    All occurences of 1s and 0s for each rows are equal
                  &{      }ᵐ          Map on rows:
                    ḅlᵐ                 Get the lengths of runs of equal values
                       ⌉<3              The largest one is strictly less than 3
                             &\↰₂   Apply predicate 2 on the transpose of the Input
                                      (i.e. do the same checks but on columns)

Answer 2

JavaScript (ES6), 274 270 bytes

Takes input as a 2D array, where empty cells are marked with 2. Prints all possible solutions to the console.

f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

How it works

The first part of the code uses the M() function to check the validity of the current board, both horizontally and vertically.

M = z =>
  !a.some((r, y) =>
    /(0|1),\1,\1/.exec(
      s = r.map((v, x) =>
        (
          v = z ? v : a[x][y],
          b -= v & 1,
          c -= !v,
          m |= v & 2,
          v
        ),
        b = c = w / 2
      )
    ) ||
    b * c < 0 |
    o[b * c || s] &
    (o[s] = 1),
    o = {}
  )

It maps a full row or column to the string s. This is actually an array coerced to a string, so it looks like "1,2,2,0,2,2".

It uses:

• The regular expression /(0|1),\1,\1/ to detect 3 or more consecutive identical digits.
• The counters b and c to keep track of the number of ones and zeros. Both counters are initialized to w / 2 and decremented each time a one or a zero (respectively) is encountered. This leads to either:
  • b = c = 0 → b * c = 0 → the line is complete and correct (as many zeros as ones)
  • b > 0 AND c > 0 → b * c > 0 → the line is not complete but correct so far (we don't have more than w / 2 zeros or more than w / 2 ones)
  • b < 0 OR c < 0 → b * c < 0 → the line is invalid
• The flag m (for 'missing') which is non-zero if there's at least one remaining two on the board.
• The object o to keep track of all line patterns encountered so far.

If the board is invalid, we stop immediately. If the board is valid and complete, we print it to the console. Otherwise, the second part of the code attempts to replace each 2 with either a zero or a one with recursive calls:

[0, 1].map(n =>
  (p = a[y][x]) == n |
  p > 1 && (
    a[y][x] = n,
    f(a, z = (x + 1) % w, y + !z),
    a[y][x] = p
  )
)

Demo

f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

console.log('Example #1')
f([
  [1,2,2,0,2,2],
  [2,2,0,0,2,1],
  [2,0,0,2,2,1],
  [2,2,2,2,2,2],
  [0,0,2,1,2,2],
  [2,1,2,2,0,0]
])

console.log('Example #2')
f([
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,0,2,2,0,2,2,1,2],
  [2,0,2,2,1,2,2,0,2,0],
  [2,2,1,2,2,2,1,2,2,2],
  [1,2,1,2,2,2,2,2,2,1],
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,2,2,1,2,2,2,0,2],
  [2,2,2,2,1,1,2,2,2,0],
  [2,0,2,0,2,2,1,2,2,0],
  [0,2,2,2,0,2,2,2,1,2]
])

Answer 3

Jelly, 53 51 bytes

ṡ€3ḄFf0,7L
SḤnLṀȯÇ
⁻QȯÇ
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ

Takes a list of lists representing the grid, containing 0, 1, and 2 (the spaces). Returns a list of lists of lists, each list of lists is in the same format (although with no 2s) and represents a possible solution to the input.

Try it online! (this wont run any of the question's test cases due to memory limitations - all 2^nSpaces grids are created as a list of list of lists of integers - but I've put a relatively hefty case there with a single solution). The footer separates out and formats the grids.

Pure brute force method - implements the rules and checks them for each grid that could be formed by replacing any of the 2s with 1s or 0s.

ṡ€3ḄFf0,7L - Link 1, # of runs of 3 1s or 3 0s by row: list of lists
ṡ€3        - all contiguous slices of length 3 for €ach list
   Ḅ       - convert all results from binary
    F      - flatten into one list
     f     - filter keep values in:
      0,7  -   0 paired with 7: [0,7]
         L - length

SḤnLṀȯÇ - Link 2, unequal counts of 1s and 0s by column ...or link 1: list of lists
S       - sum (vectorises, hence "by column", counts 1s since only 1s or 0s appear)
 Ḥ      - double
   L    - length (number of rows - OK since square)
  n     - not equal? (vectorises)
    Ṁ   - maximum (1 if any not equal)
     ȯÇ - ... or last link (1) as a monad

⁻QȯÇ - Link 3, rows are unique ...or link 2: list of lists
 Q   - unique
⁻    - not equal?
  ȯÇ - ... or last link (2) as a monad

Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ - Main link: list of lists
F                           - flatten
 ṣ©2                        - split at 2s and copy the result to the register
    L                       - length (# of such slices)
     ’                      - decrement (# of 2s)
      0,1                   - 0 paired with 1
         ṗ                  - Cartesian power (all binary lists of length # of 2s)
             ®              - recall value from register (the flat version split at 2s)
          ż@€               - zip (reversed @rguments) for €ach (1s & 0s where 2s were)
              F€            - flatten €ach
                s€L         - split €ach into chunks of length length(input) (into rows)
                    Ðḟ      - filter discard if:
                   Ç        -   call last link(3) as a monad
                         Ðḟ - filter discard if:
                        $   -   last two links as a monad:
                      Z     -     transpose
                       Ç    -     call last link(3) as a monad