Is this a valid Takuzu board?

Question

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.

Task:

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 code-golf, so shortest code in bytes wins!

Answer 1

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

Answer 2

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

Answer 3

Jelly, 17 bytes

-*S;E3Ƥ€F$TȯQZµ⁺⁼

Try it online!

-6 bytes thanks to miles and Jonathan Allan.

Answer 4

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}}]

Answer 5

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 in`a+b`>'1, 1, 1'not in`a+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 in`a+b`>'1, 1, 1'not in`a+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".

Answer 6

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)

Answer 7

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

Answer 8

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.

Answer 9

Retina, 129 89 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.

Answer 10

Java 8, 350 326 325 312 303 299 298 259 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)

Answer 11

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.

Answer 12

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.

Answer 13

J, _{40 38} 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.

Answer 14

Haskell, 137 136 127 bytes

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!

Answer 15

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[0]))])and c(m)

Try it online!

Takes input as a list of lines.

Answer 16

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

Answer 17

Dyalog APL, 64 52 51 49 48 bytes

Requires ⎕IO←0

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

Try it online!

Answer 18

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.