Counting valid Binary Sudoku boards

Question

Sequel of Counting valid Binary Sudoku rows.

Background

Binary Sudoku, also known as Takuzu, Binario, and Tic-Tac-Logic, is a puzzle where the objective is to fill a rectangular grid with two symbols (0s and 1s for this challenge) under the following constraints:

1. Each row/column cannot have a substring of 000 or 111, i.e. one symbol cannot appear three times in a row, horizontally or vertically.

   • A row/column of 1 0 0 0 1 1 violates this rule since it contains three copies of 0 in a row.

2. Each row/column should contain exactly as many 0s as 1s, i.e. the counts of two symbols must be the same.

   • A row/column of 1 0 1 1 0 1 violates this rule since it has four 1s but only two 0s.

   • Some examples of rows that meet the first two requirements include:

     [1 0 0 1]
     [1 1 0 0]
     [1 1 0 1 0 0]
     [1 1 0 0 1 0 0 1]
     

3. The entire grid cannot have two identical rows or columns.

Note that the constraint 2 enforces the grid size to be even in both dimensions.

Here are some examples of completed Binary Sudoku:

(4x4)
1 1 0 0
0 1 1 0
1 0 0 1
0 0 1 1

(6x8)
1 1 0 1 0 1 0 0
0 0 1 0 1 0 1 1
0 1 0 1 0 0 1 1
1 1 0 0 1 1 0 0
0 0 1 0 1 1 0 1
1 0 1 1 0 0 1 0

Challenge

Given two positive integer m and n, calculate the number of distinct valid Binary Sudoku boards of width 2m and height 2n. (You may take the values of 2m and 2n as input instead of m and n.)

A253316 is the sequence for square boards.

Test cases

m,n => answer
-------------
1,1 => 2
1,2 => 0
2,2 => 72
2,3 => 96
2,4 => 0
3,3 => 4140
3,4 => 51744
3,5 => 392208
4,4 => 4111116

For the input 1,2, it counts 2-by-4 boards, i.e. boards with four rows of length 2. But we can't have four distinct rows of length 2 to fill the grid (we have only 01 and 10). Therefore, by rule 3, the answer to the input 1,2 is zero. The same argument applies to the input 2,4 (4-by-8 boards).

Reference implementation in Python. This can handle up to 3,5 in a minute. Note that putting r > c takes much more time than the same pair swapped, though the results are the same.

Scoring and winning criterion

Standard code-golf rules apply. The shortest submission in bytes wins.

Answer 1

Python 3.8 (pre-release), 265 250 198 bytes

lambda n,m:sum(not(n>len({*s})or m>len(set(z:=[*zip(*s)]))or any(p*3in"".join(v)or v.count("1")*2-len(v)for p in'01'for v in[*s]+z))for s in P(*[[*P(*['01']*m)]]*n))
from itertools import*;P=product

Try it online! Takes as input 2n and 2m. Thanks to Bubbler for finding a bug in my original answer and for golfing a massive 52 bytes off.

How it works:

The anonymous function we define will be taking 2n and 2m as input, generate all binary boards with the specified dimensions and then count how many of those satisfy the restrictions.

Generating all boards

... for s in P(*[[*P(*['01']*m)]]*n))
from itertools import*;P=product

is generating all the boards. The product function from the library itertools can be used to generate the cartesian product of all the arguments it is given. Breaking the nested Ps down, P(*['01']*m) creates a list of length m with '01': ['01', '01', ..., '01'] and then the splat operator * is used to turn each element of the list into an argument to P, so P(*['01']*m) generates all valid rows of length m. Call it P1.

Then we have P(*[[*P1]]*n) which takes all valid rows and turns it into a list of all valid rows, with [*P1]. We then enclose such a list in another list and multiply by n, so that we get a list of length n where each value is a list of all valid rows. Then the splat operator * is used to provide such a list as a series of arguments to the itertools.product function, thus getting all the correct-sized binary sudoku boards. We iterate over those with s.

Checking restrictions on the board

Now we are left with checking the conditions imposed on the board s with

not(n>len({*s})or m>len(set(z:=[*zip(*s)]))or any(p*3in"".join(v)or v.count("1")*2-len(v)for p in'01'for v in[*s]+z))

Instead of verifying if the board satisfies everything, we check if the board doesn't violate any restriction:

• n>len({*s})or m>len(set(z:=[*zip(*s)])) checks if there are n unique rows, by converting the list of rows into a set; similarly we transpose s into z and check if there are m unique columns;

• then any(B1 or B2 for v in[*s]+z) goes over all rows and all columns:

  • B2 = v.count("1")*2-len(v) gives 0 when the amount of 1s is exactly half of the size of the row/column and other non-zero integers when it is not. Regardless of giving a positive or negative result, Python will treat it as a Truthy value.

  • B1 = p*3in"".join(v) for p in'01' builds the substrings "000" and "111" and checks if those are in the row/column

Wrapping it up

In the end, we just sum all the Truthy values that correspond to all the boards that did not violate any restrictions.

Answer 2

Wolfram Language (Mathematica), 144 bytes

Input (2n,2m)

(l=Length)@Select[Tuples[{0,1},g=#],And@@Flatten[{#~Count~1==#~Count~0,Max[l/@Split@#]<3}&/@Flatten[c={#,Transpose@#},1],1]&&l/@(Union/@c)==g&]&

Try it online!

Answer 3

Jelly, 26 bytes

IIP;S¬$PȧQƑ
×Ø-ṗ$s€ÇƇZ€$⁺L

A dyadic Link accepting 2n on the left and 2m on the right (or vice-versa as it's symmetric) which yields the count.

Try it online! This will time out even for (6,4) (i.e. m=2 and n=3)*

How?

I imagine that if one worked out a combinatorial formula it would be much shorter (and quicker and more memory efficient!), but this entry is pure brute-force...

IIP;S¬$PȧQƑ - Link 1, (    no row has a run of 3 or more
                       AND no column contains differing type counts
                       AND all the rows are different
                      ): a single board, B
I           - incremental differences (vectorises) - e.g. [-1,1,1,1] -> [2,0,0]
 I          - incremental differences (vectorises)
  P         - product - this will give a list which will contain a zero for any row
                        containing a run of at least three equal items
     $      - last two links as a monad:
    S       -   sum (vectorises) - since we use -1 and 1: zero if the counts are equal
     ¬      -   logical NOT
   ;        - concatenate
       P    - product - this will be non-zero if (no row has a run of 3 or more
                                  AND no column contains differing type counts)
          Ƒ - is (B) invariant under:
         Q  -   de-duplication - i.e are all the rows different?
        ȧ   - logical AND

×Ø-ṗ$s€ÇƇZ€$⁺L - Link: 2n, 2m
×              - multiply -> 2n×2m (size of board)
    $          - last two links as a monad:
 Ø-            -   signs = [-1,1]
   ṗ           - Cartesian power (all lists of length 2n×2m of items -1 and 1)
      €        - for each:
     s         -   split into slices of length 2m (i.e. into rows)
           $   - last two links as a monad:
        Ƈ      -   filter keep those for which:
       Ç       -     call last Link (1) as a monad
          €    -   for each:
         Z     -     transpose
            ⁺  - repeat the last link - i.e. check the results with rows<->columns
             L - length

---

* I ran m=2, n=3 locally and it yielded 96 as expected (after over an hour in which it hit 100% memory (16GB Ram) and slowed to a snail's pace while using disk).

Answer 4

Charcoal, 102 81 64 bytes

Ｎθ≔×θＮη≔ＥＸ²η⪪⭆◧⍘ι²ηΣλθζＦ²≔ＥΦζ⬤κ›⁼№μ0№μ1⁺⊖№κμΣＥ²№μ׳ＩξＥθ⭆κ§ξμζＩＬζ

Try it online! Link is to verbose version of code. Takes the actual size as input. Explanation:

Ｎθ≔×θＮη

Input the width and area.

≔ＥＸ²η⪪⭆◧⍘ι²ηΣλθζ

Generate all possible grids of 0s and 1s of the given width and area.

Ｆ²

Loop over rows and columns.

Φζ⬤κ›⁼№μ0№μ1⁺⊖№κμΣＥ²№μ׳Ｉξ

Keep only those grids where each row has an equal number of 0s and 1s, is unique, and contains neither 000 nor 111.

≔Ｅ...Ｅθ⭆κ§ξμζ

Transpose the rows and columns so that the columns can be checked on the next pass.

ＩＬζ

Output the number of remaining grids.

Previous much faster 102-byte version:

ＮθＮη≔ΦＥＸ²θ⭆◧⍘ι²θΣλ›⁼№ι0№ι1ΣＥ²№ι׳Ｉλζ⊞υ⟦⟧ＦυＦ‹ＬιηＦζＦ¬№ιλ⊞υ⁺ι⟦λ⟧ＩＬΦＥΦυ⁼ＬιηＥθ⭆ι§νλ⬤ι›⁼№λ0№λ1⁺⊖№ιλΣＥ²№λ׳Ｉν

Try it online! Link is to verbose version of code. Takes the actual size as input.