# Decide whether a given field of the board game 'Qwirkle' is valid (according to game rules)

The famous game of Qwirkle has simple but intricate rules (See part 2 of this question for a summary of the rules!)

1. The Challenge You are somehow (text input, function parameter, whatever) given a board of a Qwirkle game, like a snapshot from any current timeframe within a game. This board can be anything from completely empty to completely filled with tiles (max board size should be at least 32x32). Each tile can be one of six colors (red r, green g, blue b, orange o, purple p, yellow y) and one if six shapes (circle c, square s, flower f, zacks z, small star m, rhombus r). You can use any distinct letters as well! There are exactly three tiles of each shape-color combination in the whole set of tiles.

Simple rules are:

• each line (horizontal or vertical) of touching tiles must contain any distinct tile at most once and only tiles of different color and same shape OR tiles of different shape and same color!

• every tile has to touch ar least one neighboring tile! No single/islands of tiles!

Your task is to calculate wether the given board is in a valid state (see rules down below). That is, wether the given board does not break any of the rules. It can also be interpreted as 'a board that was created from a valid game, not breaking any of the game's rules'. The result is thus one of two possible values, either true or false, 1 or 0 or whatever you prefer.

The result can be anything from a text output, a returned boolean or other variable type or whatever you want. Just somehow publish the result (don't just keep it inside a variable)

1. The Game Rules In a possibly infinite 2d checked board, tiles get laid. On every field on the board can either be one or no tile.

There are 36 different types of stones, each 3 times, makes a total of 108 tiles. A board doesn't contain more than one set of tiles. (you only play with one sack. When it's empty, the game ends)

1. Special Things to Check
• It's important to note that a valid game evolves around one start position. This means, any tile on the field has to touch any other tile through other tiles. There can't be single tiles or islands of tiles disconnected from the main starter island. So, any tile has to touch at least one other tile.

• there are only 3 tiles of each color and shape in total. So there can't be, for example, 4 red square tiles or 4 green circles.

1. Example Image This is an example of a valid qwirkle field: I think all of your questions can be answered by studying this image:

1. Test Cases Note that test cases are going to be in an array (string with linebreaks or similar), for example: your program can take some other format (for example tabbed strings, semicolons as dividers or whatever! Doesn't have to accept any one! Just choose one specific format)
0,0,rs,rc,0,0
0,0,gs,gc,0,0


(this would be valid!)

In this case i specified the input as color first letter, shape second letter. So rs is red square, gc is green circle etc. Any other format is ok!

1. This is so shortest working code in bytes wins!

## Test cases (based from comments, commas separate columns, semicolons separate rows):

Truthy:

""
rc,gc,bc,oc,pc,yc;rs,gs,bs,os,ps,ys;rf,gf,bf,of,pf,yf;rz,gz,bz,oz,pz,yz;rm,gm,bm,om,pm,ym;rr,gr,br,or,pr,yr


Falsy:

rc,rs,rf,rz,rm,rr,rf
rc,rs,rf,yc

• Suggested test case: "" (empty string) -> truthy Nov 20, 2022 at 21:02
• I've never played Quirkle with a rule that e.g. you can't have both horizontal and vertical rows of red tiles.
– Neil
Nov 21, 2022 at 14:38
• @Lecdi alright, maybe me and my friends invented that rule, thanks for pointing it out, I have removed that point from the rules! Nov 21, 2022 at 20:04
• Can you please provide some test cases? Nov 23, 2022 at 8:37
• @Jonah yeah thats fine Nov 23, 2022 at 16:57

import Data.Maybe
import Data.List
i=isJust
(#)=map
a=all
j=fromJust
t([]:_)=[];t x=(h#x):t(tail#x)
v b=a(a(\z->any(a id)$t$(zipWith(==)$j$h z)#(j#z)))$map(filter(i.h).groupBy((.i).(==).i))b f b=v b&&v(t b)&&(a((==1).length)$group$sort$concatMap catMaybes b)


Attempt This Online!

• I think you can replace the map in the definition of v with # to save 2 bytes Nov 23, 2022 at 19:01

# 05AB1E, 71 69 bytes

ø«ε0¡ε€Sø€ËàyD¢*]˜PI˜áD¢4‹PIa©˜ƶIgäΔ2Fø0δ.ø}2Fø€ü3}®*εεÅsyøÅs«à]˜0KËP


Input as a matrix of 2-char strings, with 0 as gaps. Outputs a 05AB1E truthy/falsey result, so 1 for truthy, or 0 or a positive integer for falsey.

Explanation:

Step 1: Verify that each connected portion in a row or column is valid, where valid means they're either all the same shape and/or the same color, and in addition there aren't any duplicated pieces in a connected row/column.

ø           # Zip/transpose; swapping rows/columns of the (implicit) input-matrix
«          # Merge this list of columns to the (implicit) input-list of rows
ε           # Map over each inner row/column:
0¡         #  Split it on 0s (the gaps)
ε        #  Map over each connected portion:
€S      #   Split each 2-char string to a pair of characters
ø     #   Zip/transpose; swapping rows/columns
€Ë   #   Check for each inner list whether they're all the same
à  #   Pop and get the maximum, to check if this is truthy for either
y       #   Push the current connected portion again
D      #   Duplicate it
¢     #   Pop both, and count how many times each piece occurs
*       #   Multiply the earlier check to each count in the list
]           # Close the nested maps
˜          # Flatten the list of list of list of checks
P         # Check if everything was truthy by taking the product


Step 2: Check that each individual piece does not occur more than 3 times:

I           # Push the input-matrix again
˜          # Flatten it
á         # Remove all gaps by only keeping the letters
D        # Duplicate it
¢       # Pop both, and count how many times each piece occurs
4‹     # Check for each that it's smaller than 4
P    # Check if everything was truthy by taking the product


Step 3: Flood-fill the matrix to check if everything is a single connected island (which I've done before in this answer and this answer of mine):

I           # Push the input-matrix yet again
a          # Convert all pieces to 1s with the is_alphabetic builtin
©         # Store this matrix of 1s/0s in variable ® (without popping)
˜        # Flatten it
ƶ       # Multiply each value by its 1-based index
Igä    # Mold it back to a matrix matching the input:
I      #  Push the input
g     #  Pop and push the length (the amount of rows)
ä    #  Split the list into that many equal-sized parts
Δ           # Loop until the result no longer changes:
2Fø0δ.ø}   #  Add a border of 0s around the matrix:
2F     }   #   Loop 2 times:
ø        #    Zip/transpose; swapping rows/columns
δ      #    Map over each inner list:
0 .ø    #     Surround it with both a leading and trailing 0
2Fø€ü3}    #  Then split it into overlapping 3x3 blocks:
2F         #   Loop 2 times again:
ø        #    Zip/transpose; swapping rows/columns again
€       #    Map over each inner list again:
ü3     #     Split this list into overlapping triplets
®*         #  Multiply this matrix of 3x3 blocks and matrix ® together,
#  so all 3x3 blocks at the 0-positions will become a block of 0s
εεÅsyøÅs«à #   Get the largest value from the horizontal/vertical cross of each
#   3x3 block:
εε         #    Nested map over each 3x3 block:
Ås       #      Pop and push its middle row
y      #      Push the 3x3 block again
ø     #      Zip/transpose; swapping rows/columns
Ås   #      Pop and push its middle row as well (the middle column)
«  #      Merge the middle row and column together to a single list
à #      Pop and push its maximum
]           # Close the nested maps and flood-fill loop
˜          # Flatten the resulting flood-filled matrix
0K        # Remove all 0s (the gaps)
Ë       # Check if all remaining values are the same, so we have a single island


Step 4: Combine all three checks of the previous steps, and output the result:

P           # Simply take the product of all three values on the stack
# (which is output implicitly as result)

• Looks very good! Thank you so much for participating! Nov 24, 2022 at 22:03

# J, 90 87 85 78 74 bytes

((#@~."1@|:e.~1,#)@#~*/@,&,[:g+/@])(,:&(-/~)0j1&*)(g=.+./ .*^:_~)"[email protected]:@1


Try it online!

## argument encoding

We take the list positions (encoded as complex numbers) as the right arg, and the list of pieces as the left arg. For example, for the board:

rc,gc,bc
__,gs,__
__,gf,__


the left and right arguments would look like this (boxed for clarity):

┌──┬─────────────────┐
│rc│0 0j1 0j2 1j1 2j1│
│gc│                 │
│bc│                 │
│gs│                 │
│gf│                 │
└──┴─────────────────┘


## idea

The high-level idea is the interesting part, so I'll focus on that.

1. Find all horizontally connected pieces. To do this, we create an adjacency matrix of all the positions, where adjacency is defined by the distance between two elements being in the set _1 0 1:

      0    0j1  0j2  1j1  2j1
+-----------------------
0   |1    1    0    0    0
0j1 |1    1    1    0    0
0j2 |0    1    1    0    0
1j1 |0    0    0    1    0
2j1 |0    0    0    0    1


And then take the transitive closure of that matrix "or-multiplied" by itself until a fixed point. The result shows all the horizontal connections:

  1 1 1 0 0  <- 0 is connected to 0, 0j1, 0j2
1 1 1 0 0  <- 0j1 is connected to 0, 0j1, 0j2
1 1 1 0 0  <- 0j2 is connected to 0, 0j1, 0j2
0 0 0 1 0  <- 1j1 is only connected to itself
0 0 0 0 1  <- 2j1 is only connected to itself

2. Find all vertically connected pieces. To do this, we reuse the logic in step 1, by first multiplying every position by 0j1, which has the effect of rotating the entire board 45 degress left. Now vertical connections will be horizontal ones. The resulting final matrix this time is:

 1 0 0 0 0
0 1 0 1 1
0 0 1 0 0
0 1 0 1 1
0 1 0 1 1

3. Next, we use the rows from the previous steps as masks to define the groups of pieces we need to validate:

 ┌──┬──┬──┬──┬──┐
│rc│gc│bc│gc│gc│  <- Vertically connected pieces
│  │gs│  │gs│gs│
│  │gf│  │gf│gf│
├──┼──┼──┼──┼──┤
│rc│rc│rc│gs│gf│  <- Horizontally connected pieces
│gc│gc│gc│  │  │
│bc│bc│bc│  │  │
└──┴──┴──┴──┴──┘

4. For each group, we validate that one property is all the same, and that the other property is all different. This part should have been easier to golf but the best approach I came up with was (#@~."1@|:e.~1,#). This takes the transpose of the input:

 ggg
csf


and takes the length of the uniq of each row, giving: 1 3. We then check if both 1 and "input length" are members of that list.

5. Finally, we check that all elements are connected. Here we use our adjacency matrix trick a third time, except now adjacency is defined as a horizontal or vertical connection:

 1 1 0 0 0
1 1 1 1 0
0 1 1 0 0
0 1 0 1 1
0 0 0 1 1


and we check that its transitive closure becomes the matrix consisting of all ones:

 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1