# Is it a checkered tiling?

## 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|
+-+-+-+-+-+


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
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).

• Suggested test cases: 00¶12 and 01¶02, which prevent solutions from simply scanning rows once and columns once. Jun 23 '21 at 6:21
• In fact, every non-checkered tiling contains 00¶12 or a rotation/renumbering in some 2x2 subregion. Jun 23 '21 at 14:23
• Can we assume that the labels form a contiguous sequence? That is, can we assume that the label numbers (if going for a matrix of integers) consists of, say, 1, 2, 3, 4, 5, 6, and not 1, 2, 4, 5, 7, 8? To put it yet another way, can we assume that the third truthy test case will be 012 and not 013? Jun 24 '21 at 4:04
• @GlenO No, it's not guaranteed. Jun 24 '21 at 4:13

# 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. • absolutely brilliant! i'm still trying to figure out how that back-referencing regex is doing the trick, but this works for all input test cases at least. kudos on such a clever first contribution! Jun 23 '21 at 17:30 • Welcome to Code Golf, and nice first answer! And yes, detecting existence of a T-junction is a correct approach in this challenge. For the ! separator, I slightly edited the challenge to explicitly allow it. Jun 23 '21 at 23:16 # 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 • I think this works for 88. The condition len({i,l}^{k,j})==2 requires the two sets of diagonal opposites to each hold two distinct elements and overlap in exactly one. The case i=l, j=k, i!=j is geometrically impossible. – xnor Jun 24 '21 at 6:19 • @xnor good finding. Thanks Jun 24 '21 at 7:44 # Python 2, 167153 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  • p in m and m[p] can be m.get(p,0). Jun 23 '21 at 5:14 • You can invert the second if condition to remove the space. – user100690 Jun 23 '21 at 5:18 • @Bubbler Good idea! I was able to omit ,0 for one of the .get calls because None is falsey (just like 0) and behaves as negative infinity in comparisons. Jun 23 '21 at 5:21 • @RecursiveCo. Good catch as well. Found it simultaneously I suppose. Jun 23 '21 at 5:22 • 142 bytes – ovs Jun 23 '21 at 5:51 # 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 )  • What does ??= do? Jun 23 '21 at 7:23 • Jun 23 '21 at 7:34 • @RecursiveCo. well that's not strictly true as you would know had you read that link... – Neil Jun 23 '21 at 10:51 • Can you do m=l=>... instead of doing an explicit object initialization? Jun 23 '21 at 12:58 • @Arnauld Good catch – tsh Jun 24 '21 at 2:18 # 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! # 05AB1E, 363327 26 bytes Prints 1 if the input is a checkered tiling and 0 if not. ˜Ù2.Œε€ã€€ÙIDø«€ü2€Ãg]0å  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?  # 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.  • ;ZQ€,Ɲ€Ẏ or ;ZQṡ¥€2Ẏ save a byte. Jun 23 '21 at 20:26 • @JonathanAllan I think they fail for 0000\n0110\n0120 Jun 23 '21 at 20:32 • Ah yes, you need both forward and reverse pairs, oops. Jun 23 '21 at 20:36 # 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. # 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.  # 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  # 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. # 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!

f(x,a)b=(x/=(a/=b),b)