Is it a checkered tiling?

Question

Background

A checkered tiling of a rectangular grid is a tiling using some polyominoes, where each region can be colored either black or white so that no two polyominoes sharing an edge has the same color. In graph-theoretic terms, the chromatic number of the adjacency graph is 2.

Terminology adapted from a Fillomino variant recently posted on GMPuzzles.

The following is an example of a checkered tiling, with a possible black-and-white coloring on the right:

+-+-+-+-+-+   +-+-+-+-+-+
|A A A|B|C|   |X X X| |X|
+ +-+-+-+ +   + +-+-+-+ +
|A|D D|C C|   |X|   |X X|
+-+-+ + +-+   +-+-+ + +-+
|E|F|D|C|G|   | |X| |X| |
+ +-+-+-+ +   + +-+-+-+ +
|E E|H|G G|   |   |X|   |
+ + + +-+-+   + + + +-+-+
|E E|H H H|   |   |X X X|
+-+-+-+-+-+   +-+-+-+-+-+

The following is not a checkered tiling, because it is not possible to color E, H, I with two colors.

+-+-+-+-+-+
|A A A|B|C|
+ +-+-+-+ +
|A|D D|C C|
+-+-+ + +-+
|E|F|D|C|G|
+ +-+-+-+ +
|E E|H|G G|
+ +-+ +-+-+
|E|I|H H H|
+-+-+-+-+-+

Task

Given a tiling, test if it is a checkered tiling.

A tiling can be input as a 2D array or string where each region is represented by a unique single alphanumeric character or integer. For example, the top array can be represented as

AAABC
ADDCC
EFDCG
EEHGG
EEHHH

or

[[0, 0, 0, 1, 2],
 [0, 3, 3, 2, 2],
 [4, 5, 3, 2, 6],
 [4, 4, 7, 6, 6],
 [4, 4, 7, 7, 7]]

For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Test cases

Truthy

0

00
00

012

0011
2013
2233

01234
56789
ABCDE
FGHIJ

000
010
002

Falsy

01
22

00
12

01
02

01234
05674

0011
0221
3244
3345

Brownie points to the first answer that beats or ties with 17 bytes in Dyalog APL (any version) or 96 bytes in JS (latest browser support, not very well golfed).

Answer 1

JavaScript, 106 101 bytes

s=>[...s,'!',s].reverse().join``.match(`(.)((?!\\1).)[^!]{${s.indexOf`
`-1}}((?!\\1|\\2).)(\\2|\\3)`)

Try it online!

(Returns inverted truthy/falsy.)

-5 by using spread syntax.

Focus on the boundaries of the tiling.

Suppose the tiling is not checkered. Then there is an odd cycle in the adjacency graph. Draw the odd cycle by connecting adjacent squares' centres, like this:

Since the cycle is odd, the route crosses an odd number of boundaries.

Now divide the space enclosed by the route into small squares.

Notice that the route's boundary-crossing count has the same parity as the sum of the squares' boundary-crossing counts. Thus at least one of the squares has an odd boundary-crossing count. It cannot be 1, so it must be 3, giving a T shape.

A regular expression is used to look for a T shape oriented as ┤ or ┴, and applied to a combination of the given string and its reverse to cover all four orientations. This relies on . not matching \n by default, and ! not being a character used in the input.

Answer 2

Python 3, 100 99 88 bytes

lambda a:2in[len({i,l}^{k,j})for x,y in zip(a,a[1:])for i,j,k,l in zip(x,x[1:],y,y[1:])]

Try it online!

Return True if it isn't checkered tiling, False otherwise

-1 byte by inversing True/False for return value

-11 thanks to @xnor

How it works:

The pattern is True if any of the following sub-pattern appears in the pattern :

AA  Ax  xy  xA
xy  Ay  AA  yA

We will then check each 2 by 2 sub-pattern.

• for x,y in zip(a,a[1:]) allows me to iterate through 2 adjacent row at the same time

• for i,j,k,l in zip(x,x[1:],y,y[1:]) define the 4 elements of our subpattern,

• len({i,l}^{k,j}) do the mutual difference on the 2 diagonals (keeps only the elements which are not in both) and compute the length. This value is equal to 2 only for all the truthy sub-patterns (and for a case not possible geometricaly in this puzzle)

• 2in[ ... ] verify that at least one of the subpatterns has his value equal to 2

Answer 3

Python 2, 167 153 143 bytes

def f(a):
 m={a[0][0]:1}
 for R in a+zip(*a)+a:
  p=0
  for c in R:
    P=m.get(p);Q=m.get(c,0)
    if(c==p)*2<Q==P:return 1
    if(P>0)>Q:m[c]=3-P
    p=c

Try it online!

-10 or so bytes from @Bubbler

-1 byte independently from @Recursive Co.

-11 bytes from @ovs

+2 bytes from fixing a bug spotted by @tsh

Returns None for truthy and 1 for falsey. Takes input as a list of lists of strings (it was numbers before, but strings saves a byte by making them distinct from 0 on line 4).

Using Python 2 to save indentation by mixing tabs and spaces.

Ungolfed

def is_checkered(arr):
    # mark the top-left column as color 0
    m = {arr[0][0]: 0}
    # zip(*arr) is the transpose of arr
    # iterate over each row and column, then row again
    # 1) loop over rows to guarantee computing colors for the top row
    # 2) loop over columns to guarantee computing colors for the entire grid
    #   - at the same time, this checks that horizontally adjacent tiles have different colors
    # 3) loop over rows again to check that vertically adjacent tiles have different colors
    for transposal in [arr, zip(*arr), arr]:
        for row in transposal:
            prev = row[0]
            for c in row:
                if c != prev and c in m and prev in m and m[c] == m[prev]:
                    # this tile and the previous are the same color
                    return False
                if c not in m and prev in m:
                    # this tile does not yet have a color,
                    # but the previous tile does, so assign the opposite color
                    m[c] = 1 - m[prev]
                prev = c
    return True

Answer 4

JavaScript, 98 bytes

-3 bytes by Arnauld

a=>a.every(m=l=>a=!l.some((c,x)=>m[v=a[x],u=l[x-1]]==(M=m[c]??=-m[u??v]|1)&&c-u||m[v]==M&&c-v)&&l)

f=

a=>a.every(m=l=>a=!l.some((c,x)=>m[v=a[x],u=l[x-1]]==(M=m[c]??=-m[u??v]|1)&&c-u||m[v]==M&&c-v)&&l)

testcases = `
0

00
00

012

0011
2013
2233

01234
56789
ABCDE
FGHIJ

000
010
002

01
22

00
12

01
02

01234
05674

0011
0221
3244
3345
`.trim().split('\n\n').map(x => x.trim().split('\n').map(l => [...l].map(v => Number.parseInt(v, 36) + 1)));

testcases.forEach(t => {
  console.log(f(t));
});

Input a 2-d array with positive numbers.

Output true / false.

a=>a.every( // For each row
m= // m is the mapping from regions to its color (-1 or 1)
l=>
a= // `a` is reused to storage last row
!l.some((c,x)=>
m[
v=a[x], // `v` is its upper neighbor
u=l[x-1] // `u` is its left neighbor
]==(
M=m[c]??= // If we haven't assign a color to current grid, assign color
-m[u??v]|1 // If this is first column, we use its upper neighbor
           // Otherwise we use its left neighbor
           // We use different color to its neighbor
           // If this is the most top left one, we use 1
)&& // If this cell have same color with its left neighbor
c-u|| // But they are in different region
m[v]==M&&c-v // Check its upper neighbor this time
)&&l // Assign `l` to `a` for so you can access it when check next row
)

Answer 5

Ruby, 108 bytes

->a{w,i,j,q=0;a.map{|x|w,i=(j=x.zip(j||x).map{|y,c|[y==i ?w:w^=1,i=y,q||=((c[0]==w)^(c[1]==i))&&j]})[0]};!q}

Try it online!

Answer 6

05AB1E, 36 33 27 26 bytes

Prints 1 if the input is a checkered tiling and 0 if not.

˜Ù2.Œε€ã€`€ÙIDø«€ü2€`Ãg]0å

Try it online! or Try more cases.

This tests if the graph of polyominoes is bipartite by trying all partitions into two subsets until it finds one where no polyominoes in the same subset are adjacent.

Technically Ù is not necessary, but this is already quite slow and would be unusable otherwise.

˜Ù                # all unique integers from the input
  2.Π            # all ways to partition those into two subsets
     ε            # for each partition:
      €ã€`        #   generate pairs of two elements from the same subset
          €Ù      #   deduplicate each pair, if both values were equal, this results into a singleton list

IDø«              #   input and input transpose concatenated (list of rows and columns)
    ۟2           #   for each row or column: get all adjacent pairs
       €`         #   and flatten into a single list of pairs
         Ã        #   list intersection with the list from before
          g       #   take the length

]0å               # after the map: was the result 0 for any partition?

Answer 7

Jelly, 22 bytes

FQŒPðfLḂɗþPẸµ;Z,Ɲ€ẎEÐḟ

Try it online! (comes with test cases)

Uses the same approach as my Pyth answer and ovs's 05AB1E solution.

Turns out I just needed a love-hate relationship to Jelly for like 3 years to finally understand how the chains work.

Explanation

FQŒPðfLḂɗþPẸµ;Z,Ɲ€ẎEÐḟ
F                        Flatten the input rows.
 Q                       Find unique characters (polyominos).
  ŒP                     Get all subsets of the characters.
              Z          Get the columns of the input.
             ;           Append them to the input rows.
               ,Ɲ        Get all overlapping pairs...
                 €       ...of each row/column. (Alternatively, ṡ€2.)
                  Ẏ      Concatenate the lists of pairs.
                    Ðḟ   Filter for pairs where...
                   E     ...the elements are not equal.
         þ               For each subset/pair combination:
     f                     Find items in the subset that are also in the pair.
      L                    Take the length of the result.
       Ḃ                   Take the length modulo 2.
                         This gives a 2D array where the outer index specifies
                         the pair and the inner index the subset.
          P              Take an elementwise product of the rows. This gives
                         1 for each subset that results in a product of 1.
           Ẹ             See if there are any subsets that produced a 1.

Answer 8

Charcoal, 57 bytes

ＷＳ⊞υι≔⭆υ⭆ι⁺⎇κ⁺§§υ⊖κμλω⎇μ⁺§ι⊖μλωθ≔⁻⪪⁺θ⮌θ²Ｅθ⁺ιιη⊙η⊙θ⬤ι№η⁺λν

Try it online! Link is to verbose version of code. Reverse output, i.e. - if not chequered. Explanation:

ＷＳ⊞υι

Input the tiling.

≔⭆υ⭆ι⁺⎇κ⁺§§υ⊖κμλω⎇μ⁺§ι⊖μλωθ

For each cell, concatenate it with the cell above and to the left (if any) and concatenate all of the results together.

≔⁻⪪⁺θ⮌θ²Ｅθ⁺ιιη

Concatenate that with its reverse, split it back into pairs, but remove all identical pairs.

⊙η⊙θ⬤ι№η⁺λν

Does there exist a pair in the adjacency list and a cell having the property that the cell is adjacent to both cells in the pair?

A port of @Jakque's answer is the same length but much faster:

ＷＳ⊞υι⊙υ∧κ⊙ι∧μ¬⁼⁼⁼λ§ι⊖μ⁼§§υ⊖κ짧υ⊖κ⊖μ⁼⁼맧υ⊖κμ⁼§ι⊖짧υ⊖κ⊖μ

Try it online! Link is to verbose version of code. Reverse output, i.e. - if not chequered.

Answer 9

Pyth, 25 bytes

sm!-ml@dk{I#s.:R2+CQQ1y{s

Try it online!

Might time out on test cases with lots of unique characters (polyominos).

Turns out I came up with the exact same algorithm as ovs's 27-byte 05AB1E answer ¯\_(ツ)_/¯

Explanation

Essentially, the program tries all colorings of the tiling, and sees if there is a coloring for which all adjacent pairs have exactly one black tile.

Q is implicitly appended to the program and the input is read into Q.

                        sQ   Concatenate the input rows.
                       {     Find unique characters in input.
                      y      Take the powerset of these.
 m                           For each subset d of the characters:
                  CQ           Get the columns of the input.
                 +  Q          Append the rows of the input.
             .: 2              Get length-2 substrings...
               R               ...of each row/column.
            s                  Concatenate the substring lists of rows/columns.
           #                   Find substrings (pairs) that...
          I                    ...stay the same when...
         {                     ...duplicates are removed.
    m                          For each such pair k:
      @dk                        Find the characters of k that are in d.
     l                           Get the length of that.
   -                 1         Remove all ones from that array of lengths.
  !                            True if the list is now empty.
s                            Sum the booleans in that list.

Answer 10

Julia 1.5, 128 99 bytes

M->(~M=diff(M,dims=1).!=0;!M=~x[M]!=~M;x=1:max(M...).>0;while(s=x[end])&&!M|!M' x.chunks.-=1end;s)

This basically tests each possible way of assigning each number either a 0 or 1 value, and determines whether the assignment keeps the number of boundaries constant (if two adjacent tiles are coloured the same, the boundary between them is removed).

M should take the form of an array of small positive integers (no zero or negatives).

This uses BitVectors - as it turns out, a bitvector is stored internally as an integer, so you can iterate through all combinations by incrementing the bitvector's internal representation (accessed as a "chunks" property of the variable).

Ungolfed:

function f(M)
  # This is the function you use to determine whether the tiling is chequered.
  x=trues(maximum(M)) #Initialise a bitarray, representing the assignment of tiles
  while x[end] #Loop until the assignment of the last tile is changed
               #from that point, all assignments are just bit-flips of the ones before!
    if (diff(M,dims=1).!=0)==(diff(x[M],dims=1).!=0)
      if (diff(M',dims=1).!=0)==(diff(x[M'],dims=1).!=0)
        break #If both horizontal and vertical boundaries are retained...
              #a successful tiling has been found!
      end
    end
    x.chunks.+=1 #Move to the next tile assignment
  end
  return x[end] #x[end] is true if it finds a successful tiling
                #but the loop ends if x[end] becomes false, indicating
                #that no tiling is found.
end

Answer 11

Retina 0.8.2, 109 bytes

1`(?<=(.)*)(.)(?(\2).+¶(?>(?<-1>.)*)(?!\2)(.)(?!\2|\3)|(.).*¶(?>(?<-1>.)*)(?(\2).(?!\2|\4)|(?!\4)(.)(\4|\5)))

Try it online! Reverse output, i.e. 1 if not chequered (-2 bytes if arbitrary non-zero output is allowed for not chequered). Explanation: Port of @Jakque's Python answer.

1`

Only look for 1 match.

(?<=(.)*)

Count the column of this cell.

(.)

Capture the top left cell of a 2×2 square.

(?(\2)...|...)

If the top right cell of the square has the same symbol, ...

.+¶(?>(?<-1>.)*)

Skip ahead to the bottom left cell of the square.

(?!\2)

This must not have the same symbol as the top left cell.

(.)(?!\2|\3)

The bottom right cell must not have the same symbol as either of the other cells.

(.)

Otherwise, capture the top right cell of the square.

.*¶(?>(?<-1>.)*)

Skip ahead to the bottom left cell of the square.

(?(\2).(?!\2|\4)|(?!\4)(.)(\4|\5))

If this has the same symbol as the top left cell, then check that the bottom right cell does not have the same symbol as the either of the other cells, otherwise check that the bottom left cell does not have the same symbol as the top right cell but the bottom right cell has the same symbol as either the top right or bottom left cell.

Answer 12

Haskell, 111 bytes

w=zipWith
s=scanl
f(x,a)b=(x/=(a/=b),b)
u(a:b)=s f(1>0,a)b
z x@(a:b)=w(.tail)(s f<$>u(head<$>x))x==s(w f)(u a)b

Try it online!

Haskell, 116 bytes

f(x,a)b=(x/=(a/=b),b)
(i#j)(a:b)=scanl i(j a)b
k=w f#(f#(,)(1>0))
e=[]:e
t=foldr(w(:))e
w=zipWith
z=((==).t.k.t)<*>k

Try it online!

Probably not going to win any awards, but I had fun with both of these. They are a bit incomprehensible.