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:
Each row/column cannot have a substring of
000
or111
, 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 of0
in a row.
- A row/column of
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]
- A row/column of
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.
2n
and2m
as input instead ofn
andm
? \$\endgroup\$4,5 => 201005480
\$\endgroup\$