# Is this a valid Takuzu board?

Takuzu is a logic game in which you have to complete a grid with cells containing 0s and 1s. The grid must follow 3 rules:

1. No three horizontal or vertical consecutive cells can be the same.
2. There must be an equal number of 0s and 1s in each row and column.
3. No two rows can be the same, and no two columns can be the same.

Let's look at a finished grid:

0011
1100
0101
1010


As you can see, this board follows rule 1, 2 and 3. There are no three horizontal or vertical cells that are the same, all the rows and columns contain an equal number of 0s and 1s, and no two rows and no two columns are the same.

Let's look at a grid that isn't valid:

110100
010011
011010
101100
100011
001101


There's a bunch of problems with this grid. For example, row 5 has three 0s in a row, and column 2 has three 1s in a row, followed by three 0s. Therefore, this is not a valid grid.

Your task is to make a program which, given a 2D array of n * n 0s and 1s, verifies the board to see if it's a valid, finished Takuzu board.

## Examples:

0011
1100
0101
1010


This board follows all the rules, and is therefore a valid Takuzu board. You must return a truthy value for this.

11
00


This is not a valid board - row 1 doesn't follow rule 2. You must return a falsey value for this.

100110
101001
010101
100110
011010
011001


This is not a valid board, it fails (only) due to rule 3 - the first and fourth rows are the same.

110100
001011
010011
101100
100110
011001


This is not a valid board, it fails (only) due to rule 3 - the first and fourth columns are the same.

011010
010101
101100
010011
100110
101001


This is a valid board.

## Rules and Specs:

• You can assume that all boards are square of dimensions n * n, where n is a positive even integer.
• You can assume that all boards are finished.
• You may take input as a 2D array containing values signifying 0 and 1, or as a string.
• You must output consistent truthy and falsey values for truthy and falsey boards, and the values representing "truthy" and "falsey" cannot be the same.

This is , so shortest code in bytes wins!

• Related – Kevin Cruijssen Sep 1 '17 at 10:46
• I know this as 0h h1... – Erik the Outgolfer Sep 1 '17 at 11:12
• @EriktheOutgolfer Yeah, I started off only knowing this as 0h h1 as well, but Takuzu is the original name of the puzzle. – clismique Sep 1 '17 at 11:42
• @EriktheOutgolfer I always knew it as "Binary Puzzle" or "Subiku", but "Takuzu" is as Qwerp-Derp mentioned the original name. – Kevin Cruijssen Sep 1 '17 at 12:05
• Some more test cases would be nice (I’m missing large, valid boards.) – Lynn Sep 1 '17 at 12:56

# Brachylog, 20 18 bytes

≠\≠,?¬{∋s₃=|∋ọtᵐ≠}


Try it online!

### Explanation

≠                           All rows are different
\                          Transpose
≠                         All columns are different
,?                       Append the list of rows to the list of columns
¬{          }          It is impossible that:
∋                      A row/column of the matrix…
s₃=                   …contains a substring of 3 equal elements
|                Or that:
∋ọ                The occurences of 1s and 0s in a row/column…
tᵐ≠             …are not equal

• "Append the list of rows to the list of columns" smart way to golf it! And here I thought your 20-byte answer was to the point and golfed as much as could be. I see Brachylog is as good in validating the matrices as it is in solving them. :) – Kevin Cruijssen Sep 1 '17 at 12:40
• Shouldn't it output false for this? – H.PWiz Sep 1 '17 at 13:12
• @H.PWiz Good find, thanks. Reverted to the 18 bytes version that worked. – Fatalize Sep 1 '17 at 13:22
• @LuisMendo I'm just putting all rows and all columns in the same list basically. – Fatalize Sep 2 '17 at 7:13
• @Zgarb Correct, thanks. That's the third time I've had to rollback an edit, the opening post is in desperate need of better test cases... – Fatalize Sep 2 '17 at 15:53

# Husk, 19 18 bytes

S=‼(Tf§=LṁDum(ṁ↑2g


Try it online!

1 byte saved thanks to H.PWiz!

The main idea is applying a series of transformations to the input that are identities for a valid board and checking if the final result is the same as the original input.

### Explanation

S=‼(Tf§=LṁDum(ṁ↑2g
m(ṁ↑2g    in each line, take at most two items for each sequence of equal items
u          remove duplicate lines
f§=LṁD          keep only those lines where the sum of each element doubled is equal to the length of the line
T                 transpose the matrix (swap rows with columns)
‼                   do all the previous operations again
S=                    check if the final result is equal to the original input

• Some reshuffling to remove a ) – H.PWiz Sep 1 '17 at 14:05
• @H.PWiz that was almost obvious, dumb me! – Leo Sep 1 '17 at 23:40

# Jelly, 17 bytes

-*S;E3Ƥ€F$TȯQZµ⁺⁼  Try it online! -6 bytes thanks to miles and Jonathan Allan. • I believe you can shorten this to 21 bytes. TIO – miles Sep 1 '17 at 20:21 • @miles ...maybe even 19 bytes? – Jonathan Allan Sep 1 '17 at 23:54 • @JonathanAllan that's 18 bytes...yeah you did the µZ$⁺ thing again :p...and 17 bytes by swapping a bit :D now I beat brachylog hehe – Erik the Outgolfer Sep 2 '17 at 9:48
• @EriktheOutgolfer Not anymore, it's a tie! – Fatalize Sep 2 '17 at 15:37
• @JonathanAllan Nice. Also I believe this is the first time the prefix/infix quick I added has been useful. – miles Sep 2 '17 at 23:17

# Mathematica, 143 bytes

And@@Flatten@(((s=#;Equal@@(Count[s,#]&/@{0,1})&&FreeQ[Subsequences@s,#]&/@{{1,1,1},{0,0,0}})&/@#)&&(DeleteDuplicates@#==#)&/@{#,Transpose@#})&


input

[{{0, 0, 1, 1}, {1, 1, 0, 0}, {0, 1, 0, 1}, {1, 0, 1, 0}}]

# Python 2, 127 bytes

a=input()
n=len(a)
b=zip(*a)
print[n/2]*n*2==map(sum,a+b)>len(set(a))==len(set(b))==n<'0, 0, 0'not ina+b>'1, 1, 1'not ina+b


Try it online!

Reads a list of n n-tuples as input.

I could output by exit code by writing 1/(…) instead of print… but it feels scummy. Should I?

## Explanation

n is the size of the board; b is a list of columns (transpose of a). The rest is one long chained comparison:

• [n/2]*n*2==map(sum,a+b) checks rule 2. Each row and column should sum to n/2.
• map(sum,a+b)>len(set(a)) is always true (list > int).
• len(set(a))==len(set(b))==n checks rule 3.
• n<'0, 0, 0' is always true (int < str).
• '0, 0, 0'not ina+b>'1, 1, 1'not ina+b checks rule 1. a+b is the string representation of all the rows and columns; for the example input on TIO it is

"[(0, 0, 1, 1), (1, 1, 0, 0), (0, 1, 0, 1), (1, 0, 1, 0), (0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1), (1, 0, 1, 0)]"


The a+b>'1, 1, 1' in the center is always true since this string is guaranteed to start with "[", which is greater than "1".

• If you want to output by exit code, you could do [n/2]*n*2==map(sum,a+b)>len(set(a))==len(set(b))==n<'0, 0, 0'not ina+b>'1, 1, 1'not ina+b>x, which is 2 bytes shorter than division and results in a NameError for truthy inputs. – ovs Sep 1 '17 at 13:53

# Husk, 27 25 bytes

Λ§&Λȯ¬VEX3§&Λ§=#0#1S=uSeT


Input is a list of lists and output is 1 for True and 0 for False

Try it online!

### Explaination

                      SeT    Create a list with the input and itself transposed
Λ                            Is the following function true for all in the list
§&                          And the results of the following functions
Λȯ¬VEX3                     Test for rule 1
§&                   The and of:
Λ§=#0#1                Test for rule 2
S=u             Test for rule 3


### Test 1

Λȯ¬VEX3
Λ         Is it True for all ...
V      Are any of the ...
X3   Substrings of length 3 ...
E     All equal
ȯ¬       Logical not


### Test 2

Λ§=#0#1
Λ         Is it true for all that ...
§=       The results of the two functions are equal
#0         Number of 0s
#1       Number of 1s


### Test 3

S=u
S=    Is the result of the following function equal two its argument
u   Remove duplicates


# Retina, 12989 85 bytes

.+
$&,$&
O#$.(?=.*,)$.%
.+
$&;$&
+(01|10)(?=.*;)

1ms(.)\1\1|\d,?;|(\D\d+\b).*\2


Try it online! Outputs 0 for valid, 1 for invalid. Edit: Saved 4 bytes thanks to @MartinEnder. Explanation:

.+
$&,$&


Duplicate each row with , separators.

O#$.(?=.*,)$.%


Transpose the first duplicate.

.+
$&;$&


Duplicate again, this time with ; separators.

+(01|10)(?=.*;)


Delete all matching pairs of digits that precede a semicolon.

1ms(.)\1\1|\d,?;|(\D\d+\b).*\2


Check to see whether any column or row fails any of the rules; (.)\1\1 checks for three identical digits in a row, \d,?; checks for an unpaired digit and (\D\d+\b).*\2 checks for a duplicate.

• If the purpose of the (...).* in the last stage is just to do max(matches,1) then you can save three bytes by using a 1 in the configuration instead. – Martin Ender Sep 1 '17 at 13:29
• And .\b\d+\b can be \D\d+\b. – Martin Ender Sep 1 '17 at 13:31
• @MartinEnder Originally I replaced invalid output with no output and tested it at the end... I eventually honed it down to a single test at the end and realised I could omit the leading .* I had previously been using but didn't think to use a configuration to limit the result, thanks! – Neil Sep 1 '17 at 13:35

# Pyth, 31 bytes

Thanks a lot to @Leaky Nun.

.Asm++mqy/k\0lQdm<hk3srL8d{Id,C


Verify all the test cases or Try it here!

# Pyth,  48 46 44  42 bytes

This is the initial solution.

&{IQ&{I.TQ.Am&q/d\0/d\1!+/d*3\0/d*3\1sC,.T


Verify all the test cases or Try it here!

&{IQ&{I.TQ.Am&q/d\0/d\1!+/d*3\0/d*3\1sC,.T     Full program with implicit input.

{IQ                                           Is the input invariant under deduplicating?
&    {I.TQ                                     And is its transpose invariant too?
.TQ    Transpose.
Q   The input.
sC,       Zip the above, [^, ^^] (and flatten).
&                                          And is the following condition met?
.Am                                  All elements are truthy when mapping over ^^.
q/d\0/d\1                        There are as many 0s as 1s.
&         !+/d*3\0/d*3\1          And there are no runs of 3 equal elements.


# MATL, 27 bytes

,G@?!]tEqts~w7BZ+|3<bXBSdvA


Input is a matrix containing 0 and 1. Output is 0 for falsy, 1 for truthy.

Try it online! Or see test cases: 1, 2, 3, 4, 5.

### Explanation

,       % Do twice. First iteration will use the input, second its transpose
G     %   Push input
@     %   Push iteration index: first 0, then 1
?     %   If nonzero
!   %     Transpose
]     %   End
t     %   The top of the stack contains the input or its transpose. Duplicate
Eq    %   Convert to bipolar form, i.e. replace 0 by -1
t     %   Duplicate
s     %   Sum of each column
~     %   Negate. If all results are true, condition 2 is fulfilled
w     %   Swap. Moves copy of bipolar input/transposed input to top
7B    %   Push [1 1 1], obtained as 7 converted to binary
Z+    %   2D convolution. Gives a matrix of the same size as the input
|3<   %   Is each entry less than 3 in absolute value? If all results are true,
%   condition 1 is fulfilled
b     %   Bubble up. Moves copy of input/transposed input to top
XB    %   Convert each row from binary to a number
Sd    %   Sort, consecutive differences. If all results are nonzero, condition 3
%   is fulfilled
v     %   Concatenate all results so far into a column vector
A     %   True if all entries are nonzero
% End (implicit). Display (implicit)


# R, 114 107 bytes

-7 thanks to Giuseppe, calling functions out of order and really compressing the conditions down

function(x)any(f(x),f(t(x)))
f=function(x)c(apply(x,1,function(y)max(rle(y)$l)>2+mean(y)-.5),duplicated(x))  Try it online! This just applies the rules to the columns of the matrix, then the columns of the transpose of the matrix. Takes input in the form: matrix(c(0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,0), ncol=4)  Which is just how R takes 2D arrays. Outputs TRUE for failures, FALSE for passes. • 107 bytes – Giuseppe Sep 1 '17 at 14:03 • General updates: used mean(y)-.5 inside the internal f function to get the means rather than colMeans, and made g anonymous. It will add warnings for converting double to logical in the call to any but that's OK. – Giuseppe Sep 1 '17 at 14:04 • @Giuseppe Thanks! I really like that combined apply, very clever change! I had it as 2 seperate applys in an early stage and didn't realise how cleanly you could combine them. – CriminallyVulgar Sep 1 '17 at 14:14 • here's a way of getting input in a little more nicely – Giuseppe Sep 1 '17 at 20:08 # Perl 6, 100 93 bytes Junctions FTW! They save 7 bytes. For the time being, this seems to be beating all the other submissions written in non-golfy languages. Yippie! {!max (@(.map(*.join)).&{.repeated| |.map:{$_~~/000|111/|.comb(0)-.comb(1)}}for @^a,[Z] @^a)}


Try it online!

Explanation: It's a block that takes the board as list of lists. We make a transpose with [Z] @^a (reduce the list of lists with zip operator). So @^a,[Z] @^a is a list of the board and its transpose. We loop over it with for which works exactly like map, just being 1 char cheaper in this case.

Inside, we first join the lists constituting rows into strings, so we have list of strings instead of list of lists (@(.map(*.join))). Then we use an anonymous block on it (.&{...}), where we actually evaluate the rules. We'll evaluate them only row-wise. (Since we do it for the original array and the transpose as well.)

To save quite some !'s, we use a bit of logic and instead of testing (NO repeated rows) AND (NO 3 consecutive same symbols) AND (NOT different counts of 0 and 1), we test NOT[ (repeated rows) OR (3 consecutive same symbols) OR (different counts) ]. That's what we do in the anonymous block: .repeated gives all rows that occur more than once, then we map over the rows, try to match 3 consecutive symbols using a regex, and subtract the counts of 0's and 1's. These are OR'red with the |. (Actually it creates a very powerful thing called a junction, but we don't use any of its powers :)) After all of this, we get a list of 2 "bools" (uncollapsed junctions). We finally or them (using max) and negate (!), which gives the desired result.

# J, 4038 55 bytes

0=[:([:+/^:_(3(0=3|+/)\"1 ]),:-.@~:,:#=[:+/"1+:@])|:,:]


Try it online!

Defines a function taking a square matrix as input.

At least it's beating Pyth (for now...) (erroneously). I should go back to counting the emoji hidden in my code since J also lends itself well to that:

[: /^: :1 |: :] :-.@ :# :@] :~@

# Explanation (slightly outdated)

This looks different from my answer, and I may get to updating it. Parts of it are still the same -- I just was not checking for rule 3 for and improperly checking for rule 2 before.

Split into a few functions and ungolfed:

join_trans  =. |: ,: ]
part_3      =. 3 (0 = 3 | +/)\"1 ]
f           =. 1 - 2 * ]
main        =. 0 = [: ([: +/^:_ part_3 , f) join_trans


# join_trans

|: ,: ]
|:       Transpose
,:    Laminated to
]  Input


This joins the transpose of the matrix to itself, creating an array of matrices.

# part_3

3 (0 = 3 | +/)\"1 ]
]  Input (matrix and transpose)


This checks the sum of partitions of 3 row-wise to see if it is 3 or 0 (since either of these means an invalid board), returning 1 if it is and 0 otherwise. It operates on both the matrix and its transpose since it's given both.

# f

1 - 2 * ]


For lack of a better name, I call this f. It replaces the 0s with _1 and leaves the 1s unchanged. This is to allow me to eventually check if the number of 0s and 1s are equal in each row and column (the sum of each of the rows should be 0).

### main

0 = [: ([: +/^:_ part_3 , f) join_trans
join_trans  Join transpose to input
part_3 , f              Apply the validity checks and join them
+/^:_                         Sum until it converges
0 =                                      Equate to 0


Basically, I leverage the fact that I've set it up so that f join_trans and part_3 join_trans both should sum to 0 iff the board is valid. part_3 should be all zeroes for a valid board and the entirety of f should sum to zero for a valid board, meaning that the sum of their sums is 0 only for a valid board.

• At least it's beating Pyth (for now...). - I really need to golf my answer – Mr. Xcoder Sep 1 '17 at 13:41
• @Mr.Xcoder haha yeah, you always seem to pull through which is why I added the "for now" bit. Not that my answer doesn't have room for golfing -- I just don't know how to do it too well. – cole Sep 1 '17 at 13:44
• You can remove that part now – Mr. Xcoder Sep 1 '17 at 14:05
• This code for 33 bytes should be equivalent to yours */@,@,&(~:,(0~:3|3+/\]),#=2*+/)|: – miles Sep 1 '17 at 19:28

9 bytes saved thanks to Lynn!

import Data.List
j=isSubsequenceOf
l x=x==nub x&&and[sum y*2==length x&&not(j[0,0,0]y||j[1,1,1]y)|y<-x]
g x=l x&&l(transpose x)


Try it online!

• Roll both alls into one and: l x=x==nub x&&and[sum y*2==length x&&not(j[0,0,0]y||j[1,1,1]y)|y<-x] – Lynn Sep 3 '17 at 10:35
• @Lynn Thanks! I was trying to roll those two together for a while. Don't know why I couldn't figure that out. – Post Rock Garf Hunter Sep 3 '17 at 13:53
• Could you change j=isSubSequenceOf to j x=isSubSequenceOf[x,x,x]? – Cyoce Sep 6 '17 at 22:49
• @Cyoce Seems to lose me a byte. If you have a way of doing it that saves me a byte I'd be happy to implement it. The idea seems like a good one. – Post Rock Garf Hunter Sep 7 '17 at 0:24
• On mobile, hmmm... Maybe instead of j a b invoke (and define) it as a#b? – Cyoce Sep 7 '17 at 1:26

# Java 8, 350326325312303299298259 255 bytes

int r,z,c,p,i,j,k,d,u,v=1;int c(int[][]b){v(b);k=v-=u=1;v(b);return r;}void v(int[][]b){String m="",x;for(d=b.length;j<d|k<d;k+=u,j+=v,r=m.contains(x)|z!=0?1:r,m+=x)for(x="#",c=0,k*=u,j*=v;j<d&k<d;z+=i|i-1,c*=i^p^1,x+=p=i,r=++c>2?1:r,k+=v,j+=u)i=b[k][j];}


Returns 0 when it's a valid board; 1 if it's invalid for one or more of the three rules.

-95 bytes thanks to @Nevay.

Explanation:

Try it here.

int r,z,c,p,i,j,k,d,u,v=1;
// Temp integers on class-level

int c(int[][]b){     // Method (1) with int-matrix parameter and int return-type
v(b);              //  Validate the rows
k=v-=u=1;          //  Switch rows with columns, and reset u to 1
v(b);              //  Validate the columns
return r;          //  Return the result
}                    // End of method (1)

void v(int[][]b){    // Separated method (2) with int-matrix parameter and no return-type
String m="",s;     //  Two temp Strings to validate uniqueness of rows
for(d=b.length;    //  Set the dimension of the matrix to d
j<d|k<d        //  Loop (1) as long as either j or k is smaller than d
;                //   After every iteration:
k+=u,j+=v       //    Increase the loop-indexes
r=m.contains(s) //    If we've found a duplicated row,
|z!=0?          //    or if the amount of zeroes and ones on this row aren't equal
1:r,           //     Set r to 1 (invalid due to either rule 2 or 3)
m+=s)           //    Append the current row to the String m
for(s=",",       //   Set String x to a separator-character
c=0,         //   Reset the counter to 0
k*=u,j*=v,   //   Increase the loop-indexes
j<d&k<d      //   Inner loop (2) as long as both j and k are smaller than d
;               //    After every iteration:
z+=i|i-1,      //     Increase or decrease z depending on whether it's a 0 or 1
c*=i^p^1,      //     Reset c if current digit i does not equal previous p
s+=p=i,        //     Set previous p to current digit, and append it to String s
r=++c>2?       //     If three of the same adjacent digits are found:
1:r;        //      Set r to 1 (invalid due to rule 1)
k+=v,j+=u)   //      Increase the loop-indexes
i=b[k][j];     //    Set i to the current item in the matrix
//   End of inner loop (2) (implicit / single-line body)
//  End of loop (2) (implicit / single-line body)
}                    // End of separated method (2)


# Python 3, 187 bytes

lambda m,c=lambda m:all([len({*m})==len(m),sum(~-("000"in x)*~-("111"in x)and x.count("1")==x.count("0")for x in m)==len(m)]):c(["".join(x[i]for x in m)for i in range(len(m))])and c(m)


Try it online!

Takes input as a list of lines.

• 187 bytes – Mr. Xcoder Sep 1 '17 at 11:23
• 171 bytes – Mr. Xcoder Sep 1 '17 at 11:50
• 147 bytes, based on @Mr.Xcoder's suggestion. – ovs Sep 1 '17 at 12:25

# 05AB1E, 29 bytes

ø‚D€ÙQIDøì©O·IgQP®εŒ3ù€Ë_P}PP


Try it online!

Explanation

Rule: 3

ø‚        # pair the input with the zipped input
D       # duplicate
€Ù     # deduplicate each
Q    # check for equality with the unmodified copy


Rule: 2

IDøì          # prepend zipped input to input
©         # store a copy in register for rule 1
O        # sum each row/column
·       # double
IgQ    # check each for equality to length of input
P   # product


Rule: 1

®ε            # apply to each row/column in register
Œ3ù         # get sublists of length 3
€Ë       # check each if all elements are equal
_      # logical not
P     # product
}    # end apply
P   # product


Then we take the product of the result of all 3 rules with P

# Dyalog APL, 64525149 48 bytes

Requires ⎕IO←0

{⍲/{(∨/∊⍷∘⍵¨3/¨⍳2)∧((⊢≡∪)↓⍵)∧∧/(≢=2×+/)⍵}¨⍵(⍉⍵)}


Try it online!

# PHP, 245+1 bytes

ew this is bulky. linebreaks are for reading convenience only:

$t=_;foreach($a=($i=str_split)($s=$argn)as$i=>$c)$t[$i/($e=strlen($s)**.5)+$i%$e*$e]=$c; for(;$k++<2;$s=$t)$x|=preg_match("#000|111|(\d{"."$e}).*\\1#s",chunk_split($s,$e))
|($m=array_map)(array_sum,$m($i,$i($s,$e)))!=array_fill(0,$e,$e/2);echo!\$x;


Takes a single string without newlines, prints 1 for truthy, nothing for falsy.

Run as pipe with -nR or try it online.