# 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. (Not relevant to this challenge) 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, using 0s and 1s)
1 1 0 0
0 1 1 0
1 0 0 1
0 0 1 1

(6x8, using Os and Xs)
O O X O X O X X
X X O X O X O O
X O X O X X O O
O O X X O O X X
X X O X O O X O
O X O O X X O X


## Challenge

Given a positive integer n, calculate the number of distinct valid Binary Sudoku rows of length 2n; that is, the number of permutations of n 0s and n 1s which do not have 000 and 111 as a substring.

The sequence is A177790, leading 1 removed and 1-based.

## Test cases

Here are the first 20 terms of this sequence (1-based):

2, 6, 14, 34, 84,
208, 518, 1296, 3254, 8196,
20700, 52404, 132942, 337878, 860142,
2192902, 5598144, 14308378, 36610970, 93770358


## Scoring and winning criterion

Standard rules apply. The shortest submission in bytes wins.

• Related (rule 2): oeis.org/A000984 -- number of numbers that follow the rule for any given N – S.S. Anne Mar 16 '20 at 22:59
• Related (rule 1): 4*n-4 or 4*(n-1). The number of numbers that don't follow the rule for any given N. Inverse is 2^(2*n)-(4*n-4). – S.S. Anne Mar 16 '20 at 22:59
• AFAIK it's not possible to reach a solution via. these two because some of the exclusions conflict. – S.S. Anne Mar 16 '20 at 23:05
• I think this can also be called "Unruly" or "Tohu wa Vohu" (see Simon Tatham's Portable Puzzle Collection) – Solomon Ucko Mar 17 '20 at 0:06

# Jelly,  13 12  9 bytes

ŻcṚ$+Ḋ$²S


Try it online! Or see the test-suite.

### How?

This code is calculating

$$\sum_{k=\lceil\frac{n}{2}\rceil}^{n}\big(\binom{k}{n-k}+\binom{k+1}{n-(k+1)}\big)^2$$

(where $$\k\$$ starts at $$\0\$$ rather than $$\\lceil\frac{n}{2}\rceil\$$ ...the additional terms are $$\0\$$ but allows a reversal trick)

ŻcṚ$+Ḋ$²S - Link: integer, n       e.g. 7
Ż         - zero range                  [0,  1,  2,  3,  4,  5,  6,  7]
$- last two links as a monad: Ṛ - reverse [7, 6, 5, 4, 3, 2, 1, 0] c - n-choose-k [0, 0, 0, 0, 4, 10, 6, 1]$   - last two links as a monad:
Ḋ    -   dequeue                   [0,  0,  0,  4, 10,  6,  1]
+     -   add                       [0,  0,  0,  4, 14, 16,  7,  1]
²  - square                      [0,  0,  0, 16,196,256, 49,  1]
S - sum                         518

• Where does this formula come from? – Jonah Mar 16 '20 at 2:49
• @Jonah oeis.org/A003440 – Jonathan Allan Mar 16 '20 at 3:34
• I think the correct formula is adding the 2 binomial – J42161217 Mar 16 '20 at 12:14
• @J42161217 ah yes missed the plus sign, thanks – Jonathan Allan Mar 16 '20 at 12:37

# Pari/GP, 77 bytes

n->polcoeff([x,0,1,0]*[0,x,1,0;0,0,1,0;x,0,0,1;x,0,0,0]^(2*n-1)*[1,1,1,1]~,n)


Try it online!

This uses a nice method involving automata and is quite efficient.

Consider the automaton that checks if a string satisfies condition one. Besides the initial state and a sink state, it has four interesting states. They signify that everything is still okay, what the last letter was and whether it was the same as the one before. When we replace the x with 1 in the matrix that occurs in the program, it describes the possibilities to get from one of these states to another.

Usually we should not ignore the initial state, but since it will not be entered again, we can handle it by starting with the vector [1,0,1,0] that describes all the states that can be reached after one step. Multiplying this vector with the matrix raised to the (m-1)th power gives a vector that tells us how many words of length m lead to each state. To get their sum, we multiply with the transpose of the all-one vector. There doesn't seem to be a shorter way to get the sum of the entries of a vector.

However, we still have condition two. It could be handled by the automaton, but that would need more states, depend on n and be complicated to create. Instead, we change the matrix (and starting vector) to have an x for each transition that corresponds to reading a 1. This way, the computation will not compuite a number, but a polynomial where each term a*x^k means that there are a words accepted by the automaton (i.e. satisfying condition one) that contain k 1s. For example, for n=3 (words of length 6) that polynomial is 6*x^4+14*x^3+6*x^2. So we just have to take the coefficient of x^n.

• Interesting. Can you explain what is going on here? – Bubbler Mar 16 '20 at 0:56
• @Bubbler Done, I hope it's understandable. – Christian Sievers Mar 18 '20 at 2:26

# Bash + GNU utilities, 123121 119 bytes

dc<<<[sD1q]so[sD0q]szzseq -f"%0.fdsK$1lK-[dsk0>zdsndlk>z[d2>od1-d2<F*]dsFxlklFxlnlk-lFx*/]dsCx1lK+d$1r-lCx+d*+" 0 $1p  Try the test suite online! I've added an explanation of this obscure-looking code at the end of the answer! Shaved off 2 bytes by moving the definitions of macros F and C to the first place they're used, and then another 2 bytes by eliminating two single-quotes that were no longer required after the macros were moved. This is another, completely different bash solution. Unlike my other (shorter) solution, this one is very fast -- TIO can compute the value for 1800 in just under its 60-second limit. Because it uses dc, it can handle arbitrarily large integers. The program is based on the binomial coefficient formula from OEIS, which is computed using dc. Since loops are such a pain to write in dc, I use seq instead to unroll the loop into a giant dc script to compute the specific number requested, and the dc script is then executed. If you're curious (and don't want to wait the 60 seconds at TIO), here's the 1800th term in the sequence: 105480721405474718567404887164925416724980133926539712143845881075284\ 901677297738964136155557073029386229070488343605298871231397783837622\ 530014641802254048917232853438125993571007137377212907244683700588015\ 444444467026455576839621404814982031106756318549435412359204504183866\ 493764320992226326910391777276272125030010740526937030702909019208912\ 640538519829602971756125307274565635138616156817423412863412177199151\ 055856207069714084657310495058759139542900519171388443547871558507573\ 948937524889911140590562675224573515451638678334944353358816689952838\ 021105461897807233248789972151274044554176393928054238190520484054350\ 689148029614875765339478833688339093323537661478061731620258929292671\ 03260220166411748225093782409130224917917686956257637269268564 How it works: Overall, the structure of the program is: dc<<<..., so bash calls dc with a script to run. But the dc script part isn't written out fully; it's actually generated itself by a program (the dc script is customized for the specific argument n that was passed in$1 to bash).

The dc script starts with a prologue string that's taken verbatim, then a call to seq to generate the bulk of the dc code, and then a final command to print the result.

PROLOGUE

The prologue is: [sD1q]so [sD0q]sz z (spaces added for clarity -- they don't affect the code).

1. [sD1q]so This defines a macro o which replaces the item at the top of the stack with 1. It's intended to be called from another macro.

In more detail:

[    Start a string (to be used as a macro definition).
sD   Pops an item from the stack and stores it in register D.
(I only do this because dc doesn't provide a way to just pop an item from the stack without doing something with it, and storing it an otherwise unused register is innocuous.)
1    Push 1 onto the stack.
q    Return from this macro and the macro which called it.
]    End the string.
so   Save the macro in register o.

1. [sD0q]sz This defines a macro z which replaces the top of the stack with 0. It works the same way as macro o above.

2. z

This pushes the current stack depth onto the stack. But the stack is currently empty, so it just pushes 0 onto the stack. This initializes the running total for the binomial coefficient sum that we're going to be computing. (The reason for using z instead of 0 for pushing a 0 is that a number is coming next; so if I used a 0 to push the 0 here, I'd need to put an extra space after it to separate it from the number coming up. So using z saves a byte.)

CALL TO seq

The seq command is of the form seq -f %0.f... 0 $1, where the ... is dc code. This takes each number k from 0 to n (the bash argument$1), replaces %0.f (in the first argument to seq) with k, and writes each of those strings on a line:

0...
1...
2...
.
.
.
n...


where the ... at the end of each line is the dc code in the argument to seq.

So the loop that one would imagine for computing $$\sum_{k=0}^n \big( \binom{k}{n-k}+\binom{k+1}{n-k-1}\big)^2$$ is actually unrolled into a simple but long computation for the specific $$\n\$$ that we have.

There are actually two macro definitions embedded in the dc code. (You can often a save a byte in dc by waiting to define a macro until the first time you use it.)

I'm going to describe those macros first, because I think it's clearer that way.

The first of the two embedded macros, [d2>od1-d2<F*] computes the factorial of the number at the top of the stack. The macro is saved in register F, so it calls itself recursively:

Assumption: The argument x is on the stack when the macro is called.

[    Start macro definition
d    Duplicate the item at the top of the stack, so x is there twice.
2>o  Pop that number. If it's < 2, call macro o to pop the extra copy of the argument, and return from F with 1 on the stack.  (This is the right answer for x! when x<2.)
If it's >= 2:
d    Pop the argument.
1-   Subtract 1.
d    Duplicate the top of the stack, so x-1 is there twice.
2<F  If it's > 2, call F recursively to compute (x-1)!.
*    Multiply the top of stack, which is (x-1)!, by the 2nd item on the stack, which is x, yielding x! as desired.
]    End macro definition


The above macro will be saved in register F.

The second of the two embedded macros computes the binomial coefficient $$\binom{n}{k} = \frac{n!}{k! (n-k)!},$$ where $$\k\$$ is the number on the top of the stack and $$\n\$$ is the second number on the stack.

The binomial coefficient macro is: [dsk0>zdsndlk>z[d2>od1-d2<F*]dsFxlklFxlnlk-lFx*/], which is saved in register C. (Note that the definition of macro F is actually embedded inside the definition of C.)

Here's how C works (when it's called, k is at the top of the stack, and n is second):

[    start of macro
d    Duplicate k at the top of the stack.
sk   Pop one k and save it in register k.
0>z  Pop the other k, and if it's < 0, call macro z to return 0 from C (which is the right value for the binomial coefficient when k<0).
If k >= 0:
d    Duplicate n (so there are now two n's at the top of the stack).
sn   Pop one n and save it in register n.
d    Duplicate n (so there are now two n's again at the top of the stack).
lk>z If n<k, call macro z to return 0 from C (which is the right value for the binomial coefficient when k>n).
[d2>od1-d2<F*]  This is the definition of macro F, as described earlier, embedded in C.
d    Duplicate the F macro string on the stack.
sF   Pop one copy of the macro F string, and save it in register F.
x    Pop the stack to get a copy of the macro string F and call it.  So now the n at the top of the stack has been replaced by n!
lFx  Compute k!.
lnlk- Compute n-k.
lFx   Compute (n-k)!
*     Multiply k! (n-k)!.
/     Compute n!/(k! (n-k)!).
]     End of macro C.


So now let's go back to see what the dc code does with each value k from 0 to n. (Below I've written C(n,k) for $$\\binom{n}{k}\$$ since TeX doesn't seem to work inside code-sample formatting.)

%0.f seq replaces this with k, so k is pushed on the stack.
d    Duplicate the top of the stack, so k is now on the stack twice.
sK   Pop one of the k's off the stack and store it in register K.
$1 Push n on the stack. ($1 has already been replaced by n due to bash's parameter expansion.)
lK   Push k back on the stack (load it from register K).
-    Pop n and k, and push n-k onto the stack.
[dsk0>zdsndlk>z[d2>od1-d2<F*]dsFxlklFxlnlk-lFx*/]   This is the embedded defintion of C, with the definition of F embedded in it.
d     Duplicate the string defining C, so it's there twice.
sC    Save the macro for C in register C.
x     Call the macro C.  This pops k and n-k, and replaces them with C(k,n-k).
1     Push 1.
lK    Push k.
+     Compute k+1.
d     Duplicate k+1 on the stack.
$1 Push n. r Swap n and the k+1 that comes next. (So the stack now has k+1 at the top, then n, then k+1 again.) - Replace k+1 and n at the top of the stack with n-k-1. lCx Replace n-k-1 and k+1 with C(k+1,n-k-1). + Add the two binomial coefficients. d* Square the sum of the two binomial coefficients. + Add it onto the running total.  The above is done for each k, so after they're all done, the top of the stack contains the value we want. EPILOGUE The epilogue is fixed code that's hit last. It just consists of the single dc command p which prints the result, with a newline after it. It may be worth mentioning that the macro F is redefined every time C is called (because the definition of F is embedded in C), but that's OK -- it's defined the same way every time. • All I see is a whole bunch of random characters. Must've been hard to write. – S.S. Anne Mar 17 '20 at 13:10 • @S.S.Anne If I have time, I’ll add an explanation today. – Mitchell Spector Mar 17 '20 at 14:33 • @S.S.Anne I've added an explanation. It took me longer than I expected! – Mitchell Spector Mar 18 '20 at 1:42 # Wolfram Language (Mathematica), 46 bytes a(n) = Sum_{k=0..n} (C(k, n-k) + C(k+1, n-k-1))^2 Sum[Tr@Binomial[{k,k+1},{#,#-1}-k]^2,{k,0,#}]&  Try it online! # Perl 5-p, 50 48 bytes @Grimmy saved 2 bytes $_=grep!/000|111/&&y/1//==y/0//,glob"{0,1}"x2x$_  Try it online! # Python 3, 114 $$\\cdots\$$ 93 89 bytes Saved 15 bytes thanks to Bubbler!!! Saved 4 bytes thanks to Jitse!!! lambda n:sum([*map(bin(i).count,('000','111','1'))]==[0,0,n]for i in range(4**n//8,4**n))  Try it online! Brute force! • 93 bytes. – Bubbler Mar 16 '20 at 3:34 • @Bubbler Wow,! Very nice summing the test and streamlining the binary conversion - thanks! :-) – Noodle9 Mar 16 '20 at 11:25 • 89 bytes – Jitse Oct 22 '20 at 15:04 • @Jitse Nice one - thanks! :=) – Noodle9 Oct 22 '20 at 15:43 # Charcoal, 35 bytes ＮθＩＬΦＥＸ⁴θ⭆◧⍘ι²⊗θΣλ›⁼№ι0№ι1ΣＥ²№ι×³Ｉλ  Try it online! Link is to verbose version of code. Explanation: ＮθＩＬΦＥＸ⁴θ  Loop from 0 to 2²ⁿ. ⭆◧⍘ι²⊗θΣλ  Generate all binary strings of length 2n. ›⁼№ι0№ι1  Check that the number of 0s and 1s is the same. ΣＥ²№ι×³Ｉλ  Check that the string does not contain 3 repeated digits. # Bash + GNU utilities, 86 75 bytes n=$1;e()(egrep "(21*){$n}"|grep -v 111);seq$[10**(2*n)]|e|tr 12 21|e|wc -l


Try it online!

The input is passed as argument, and the output is written to stdout.

It's very slow -- TIO times out at $$\n=5\$$.

How it works:

The function e is a filter; it only allows a line through if:

(a) it doesn't have 3 1s in a row,

and (b) it has a substring consisting of just 1s and 2s, with exactly n 2s.

The seq command counts from $$\1\$$ to $$\10^{2n}\$$. These are all numbers of at most $$\2n\$$ digits (except for the $$\10^{2n}\$$ at the end).

We'll count numbers consisting of just 1s and 2s, not 1s and 0s, since otherwise we wouldn't get numbers starting with 0s.

The filter e is applied, and then it's applied to the same string with the 1s and 2s switched around. So a number is allowed through if:

(a) it doesn't have 3 1s in a row;

(b) it doesn't have 3 2s in a row;

(c) it has a substring consisting of just 1s and 2s, with exactly n 2s;

and (d) it has a substring consisting of just 1s and 2s, with exactly n 1s.

Since the numbers being produced are decimal numbers with at most $$\2n\$$ digits, it follows that we're only letting through numbers with exactly $$\n\$$ 1s and exactly $$\n\$$ 2s. (The $$\10^{2n}\$$ at the end is an exception with $$\2n+1\$$ digits, but it won't have passed through the filter anyway.)

Finally, wc -l counts the lines remaining.

The earlier 86-byte version used dc instead of seq, so it can handle arbitrarily large numbers, not limited by bash's maximum integer size. But that's more or less moot because it's too slow anyway.

Here's the old version:

n=$1;e()(egrep "(21*){$n}"|grep -v 111);dc<<<"O\$1d+^[d1-pd0<f]dsfx"|e|tr 12 21|e|wc -l

You can see more about that one (including a faster version that's 2 bytes longer, counting in base 3 instead of base 10) in the edit history.

# 05AB1E, 13 8 bytes

Port of Jonathan Allan's Jelly answer

ÝÂcDÀ+nO


Try it online!

Old 13-byter:

xLÉœêʒü3€ËË}g


Try it online!

# APL (Dyalog Unicode), 18 bytes

+.×⍨1,2+/⊢(-!⊢)⍳,⊢


Try it online!

Bubbler's port of the Jelly solution(-14 bytes!).

# APL (Dyalog Unicode), 35 32 bytes

{+/(×⍨((⍵-1+⊢)!1+⊢)+⊢!⍨⍵-⊢)⍳1+⍵}


Uses the formula from the Bash answer(which is very, very cool, go upvote it!).

Requires ⎕IO←0 for 0-indexing.

-3 bytes from ovs (Converted inner dfn to train, removing assignment to n).

## Explanation

{+/{×⍨((n-⍵+1)!⍵+1)+(n-⍵)!⍵}⍳1+n←⍵}
n←⍵  store input in n
⍳1+     range 0..n
{                       }        apply the following to it's elements k:
(n-⍵)!⍵         k C (n-k)
+                plus
((n-⍵+1)!⍵+1)                 (k+1) C (n-(k+1))
×⍨                              squared
+/                                 sum the resulting array


# APL (Dyalog Extended), 42 bytes

{+/(≢=2×+/)¨{⍵/⍨{⍱/0 3∊⍵}¨3+/¨⍵}↓⍉⊤⍳2*2×⍵}


Try it online!

Brute force method, which is much slower and longer.

• From what I could tell, the combinatorial formula is actually from Jonathan Allan's Jelly answer, no? – RGS Oct 19 '20 at 15:16
• @RGS The bash formula is closer to what I've implemented. – Razetime Oct 19 '20 at 15:20
• The inner dfn can be written as a train like (×⍨((n-1+⊢)!1+⊢)+⊢!⍨n-⊢). This removes the need for the assignment: tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/6u19TUOT3/… – ovs Oct 19 '20 at 16:02
• More directly porting the Jelly solution can lead to much fewer bytes (I got 18). Can you find it? Hint: 2+/ – Bubbler Oct 21 '20 at 4:31
• @Bubbler I got {+/1,×⍨2+/(⊢!⍨⍵-⊢)⍳1+⍵} which is 23. Nice hint. – Razetime Oct 21 '20 at 5:44

# JavaScript (ES6),  80 76  70 bytes

A port of the Maple solution presented on OEIS.

f=(i,j=i,k=2)=>i*j<0?0:i|j?(k<4&&f(i-1,j,k<3?3:4))+(k&&f(i,j-1,k>1)):1


Try it online!

# Japt-x, 15 bytes

Far too long and extremely inefficient! :\

çA á â Ë«ø56¤ò3


Try it

# Ruby, 75 bytes

->n{([0,1]*n).permutation.uniq.count{|r|r.chunk{|n|n}.all?{|k,v|v.size<3}}}


Try it online!

## Explanation

This is a naive solution that generates the permutations and counts the valid ones.

->n{([0,1]*n).permutation.uniq.count{|r|r.chunk{|n|n}.all?{|k,v|v.size<3}}}

# This gets all the unique permutations of 0s and 1s of size 2n.
([0,1]*n).permutation.uniq

# This counts all instances where the inner block evaluates to true
count{                                     }

# This chunks together consecutive 0s and 1s.
|r|r.chunk{|n|n}

# This checks that all consecutive 0s and 1s are shorter than 3
all?{|k,v|v.size<3}


# C (gcc), 79 bytes

f(i,j,k){i=i*j<0?0:i|j?(k<4)*f(i-1,j,3+k/3)+!!k*f(i,j-1,k>1):1;}a(x){f(x,x,2);}


A port of Arnauld's solution, and, by extension, the Maple solution on the OEIS page.

I spent way too much time working on an alternate solution. Here's what I came up with that didn't work:

• The number of numbers that don't meet the requirements of rule 1 is 2(x-1), or 4(x-1) in this challenge's input scheme.

• The number of numbers that do meet the requirements of rule 2 is (n)!/(floor(n/2)!)^2, or (2n)!/(n!)^2.

• These cannot be combined because some numbers meet both the requirements, some meet neither, and the rest meet only one.

-6 bytes thanks to ceilingcat!

Try it online!