Validate Blokus Board

Question

Blokus is a board game in which players take turns placing pieces on a \$ n \times n \$ square grid. In this version of the game, there will be just one person playing. The person is given \$ 21 \$ unique polyominoes, ranging from \$ 1 \$ to \$ 5 \$ tiles each. They then proceed to place down a subset of the pieces onto the board. After the pieces have been placed, it is your job to determine whether it could be a valid Blokus board.

There are \$ 3 \$ key rules for placing down pieces, which must be followed:

\$ 1. \$ The first piece being placed must touch one of the four corners of the board

\$ 2. \$ After the first piece, each subsequent piece must not contain a tile that is adjacent to another piece in any of the four cardinal directions (not including diagonals)

\$ 3. \$ After the first piece, each subsequent piece must contain at least one tile that is diagonally adjacent to another piece, (that is, all pieces should form a single connected component which are connected only by corners touching)

Task

The task is to determine, given an \$ n \times n \$ square grid, whether it could be a valid Blokus board. A Blokus board is considered valid if it obeys the \$ 3 \$ rules given above.

In addition, you can assume that the board will consist only of the \$ 21 \$ valid Blokus pieces. However, you may not assume that there are no duplicates. A board which contains a duplicate is automatically considered invalid.

Very Important

You may notice that sometimes a single board can have multiple orientations of the pieces. For example,

...
.XX
XXX

might be a single P piece, but it could also be a V3 piece directly adjacent to a 2 piece, among other things. If this is ever the case, you should output a Truthy value if any of these orientations match. So in the above example, it would return true, because while it could be a V3 and a 2 piece, which breaks Rule 2, it could also be a single P piece, making it a valid board.

Clarifications

• The board will be inputted as a grid of two distinct values, denoting whether a given tile is occupied by a polyomino
• The input can be taken in any reasonable format (e.g. 2D array, flattened string, list of coordinates + dimensions)
• The pieces can be rotated or reflected before placing on to the board
• Not all the pieces are required to be placed down to be considered a valid position

Test Cases

Truthy

('X' for occupied, '.' for unoccupied)

.X.
.XX
X..

XX.X
XXX.
...X
..XX

.....
.....
.....
.....
.....

......
......
......
......
......
X.....

X....XXX.
X..XX.X..
X..XX..X.
X.....XXX
X.XX.X.X.
.X.XX....
.X..X.XXX
.X.X.X...
.X.XXX...

Falsey

('X' for occupied, '.' for unoccupied)

Invalid configuration, there is no such piece, unless two pieces are joined to
look as one (e.g. 'L4' piece is directly adjacent to '2' piece), which would
break Rule 2.
XXX
X.X
X..

Invalid, since a valid board can contain no duplicates.
X....
X....
X....
X....
.XXXX

Invalid configuration. Even though the pieces are all valid, it doesn't start in
one of the four corners, which breaks Rule 1.
.....
..X..
.XXX.
.X...
..X..

Invalid configuration. All pieces are valid and are not adjacent horizontally
or vertically, however they are disjoint (they do not form a single chain, which
breaks Rule 3).
X...XX
X.X.XX
X.X..X
..XXX.
.....X
X..XXX

Invalid configuration. The two components are disjoint.
.XX..
X....
X.X..
X..XX
X..XX

Invalid configuration. It breaks Rule 1, 2, and 3 (board may be portrayed as an
'L4' piece at the bottom, and an 'O' and a '2' piece at the top).
.....
.XXXX
...XX
.X...
.XXX.

This is code-golf, so the shortest code in bytes wins!

Answer 1

Python 2, 446 422 385 384 bytes

-1 byte thanks to @ovs

l=len
A=abs
s="""def v(O,N):
 def c():
 qp:
    qp:
        if(i!=j)*any(A(t-T)==1qiqj):i+=j;p.remove(j);c();return
 p=[[a]qO];c();r=C=p[:1];i=[sum(A(b-a)*A(c-b)qPqPqP)qp];N-=1
qC:
  if l(o)>5:r=0
 qp:C+=[P]*(1-all(A(a-b)-2**0.5qoqP)-(P in C))
 print(l(p)-l(C)+l(i)-l(set(i))==0)*any(k in Oq[0,N*1j,N+N*1j,N])*r,p>[]"""
exec eval("s"+".replace('q',' for %s in ',1)"*14%tuple("ijtTaabcPoPabk"))

The output format is a bit strange: it prints more than 7 characters for truthy output, and 7 or fewer characters for falsey output (7 characters is the length of "[] True". This may be stretching it, so the p>[] can be replaced by if p!=[] else 1 for +11 characters to give more traditional truthy/falsey output.

The input is a list of coordinates given as complex numbers, along with the dimension n.

Try it online!

All testcases

The invariant may be the most interesting part. Since it must be conserved on rotations and reflections, distance between corresponding tiles is just about the only thing that stays constant. Also, I could not rely on the order that the tiles are listed in the piece. Using the product/sum of distances between every tile led to collisions, but using triples of tiles worked well.

I used for _ in fourteen times (wow), so the exec/eval saves 37 bytes.

Ungolfed:

def invariant(piece):
    inv=1
    for a in piece:
        for b in piece:
            for c in piece:
                inv+=abs((b-a)*(c-b))
    return inv

def valid(occupied,n):
    # convert list of rows into coordinates of Xs
    if not len(occupied):
        return True
    # generate list of pieces (this takes care of rule #2)
    pieces = [[a] for a in occupied]
    def consolidate():
        for i in pieces:
            for j in pieces:
                # merge two pieces if they share an edge
                if i!=j and any(abs(tile1-tile2)==1 for tile1 in i for tile2 in j):
                    i += j
                    pieces.remove(j)
                    # this repeats consolidate until no change (nothing left to combine)
                    consolidate()
                    return
    consolidate()
    # get a connected component of pieces (for rule #3)
    connected = [pieces[0]]
    for connected_piece in connected:
        # eventually every piece should be connected if the board is otherwise valid, so
        # we can check for valid-size pieces in this outer loop
        # all polyominoes with at most 5 tiles are valid
        if len(connected_piece) > 5:
            return False
        for piece in pieces:
            if any(abs(a-b)==abs(1+1j) for a in connected_piece for b in piece) and piece not in connected:
                connected += [piece]
    # check that all pieces are only used once
    ids = [invariant(piece) for piece in pieces]
    used_once = len(ids) == len(set(ids))
    nm = n-1
    rule_1_met = any(k in occupied for k in [0, nm*1j, nm+nm*1j, nm])
    return used_once and rule_1_met and len(pieces) == len(connected)

Answer 2

JavaScript (ES7),  344 330 328  326 bytes

Takes a binary matrix as input. Returns 0 or 1.

m=>[-1,C=E=I=0,1,2,1,4].map(Z=t=>(m=m.sort(_=>t-3).map((r,y)=>r.map((_,x)=>m[x][y])),C|=!!m[0][0],g=(X,Y)=>m.map((r,y)=>r.map((v,x)=>(q=(x-X)**2+(y-Y)**2,t&1?v>0:v<0)?~t?1/X?q-1||g(x,y,S.push(x-H,y-V),r[x]=t?-v:I,n++):E|=Z[g(H=x,V=y,K=r[x]=t?-v:++I,S=[d=n=1]),S]-(Z[S]=K*K)|n>5|v==1:q<3|!I&&g(x,y,r[x]=-1,I=1):0)))())|I<2|C&!E

Try it online!

How?

About the 2nd rule

The 2nd rule is implicitly enforced if we:

1. Assume that adjacent tiles always belong to the same piece.
2. Make sure that all pieces are made of at most 5 tiles.
3. Make sure that there are no duplicate pieces (either rotated or reflected).

Main algorithm

Our algorithm works with 6 iterations.

The pieces are identified by flood-filling the occupied tiles of the grid.

During the first iteration, we look for the first occupied tile as a starting point and flood-fill in all directions (including diagonals) with \$-1\$. If a piece is not connected to the other ones, it will still be filled with \$1\$'s after this process, as the secluded red tile in the example below.

During the second iteration, each piece is renumbered with a distinct ID, starting at \$2\$.

Example:

^{(ignoring the transformations that are described in the next paragraph)}

$$\begin{pmatrix} 1&1&0&1\\ 1&1&1&0\\ 0&0&0&1\\ \color{red}1&0&1&1 \end{pmatrix}\rightarrow \begin{pmatrix} -1&-1&0&-1\\ -1&-1&-1&0\\ 0&0&0&-1\\ \color{red}1&0&-1&-1 \end{pmatrix}\rightarrow \begin{pmatrix} 2&2&0&3\\ 2&2&2&0\\ 0&0&0&4\\ \color{red}1&0&4&4 \end{pmatrix} $$

During the next iterations, only the sign of the IDs is changed.

Transformations

At each iteration, the matrix is either rotated or reflected in such a way that 2 duplicate pieces are guaranteed to eventually appear with the same shape at some point.

For each piece, we build a shape key consisting of a flatten list \$S\$ of \$(dx,dy)\$ values. It describes the positions of the tiles, using the top-left one as the origin. The keys are stored in the object \$Z\$.

There is a duplicate if we encounter the same key at any iteration for two distinct piece IDs.

Flags and final result

The flag \$E\$ (for error) is set if:

• a duplicate is found
• or a piece is made of more than 5 tiles
• or there's at least one tile which is still marked as \$1\$, meaning that a piece is not connected to the other ones

At each iteration, we test whether the tile at \$(0,0)\$ is occupied and set the flag \$C\$ (for corner) if it is. Because all rotations are tried, it is guaranteed to be set if there's at least one piece in any corner.

Because an empty board is valid although it has no corner, we also need the variable \$I\$, which is the number of pieces + 1.

The final result is given by:

$$(I<2)\text{ or }\big(C\text{ and }(\operatorname{not} E)\big)$$

Answer 3

J, ₁₃₄ 130 bytes

Takes the dimensions and a list of points. I'm not sure if this is the best approach, but it is shorter then a quick matrix attempt.

(((140*/@:>#"1)*[-:~.)@((5 2$0 0,i:1)&n)*2>[:#(,/,"0/~i:1)&n=.]/:~@,@:(-/~)/.~[:+./"2@#~^:_]e./"2+"1/~)@[*(+/@e.~0,3 2$0,<:)+0=#@[

Try it online!

How it works

We check five things:

1. empty list OR all of …
2. corner is in the points
3. all points are connected to each other via 8 directions
4. all groups that are connected to each other via 4 directions have max length of 5
5. the groups of 4 are unique

Most components and the combination of them can probably be golfed further. The most interesting part will be the uniqueness check: it calculates all differences between points and sorts them, flattened down. So 1 2, 2 2 -> 1 0, _1 0 -> _1 0 0 1. Not sure if this would be enough for all polyominoes, but for up to length 5 it seems to work.

A rough ungolfed version looks like this:

points=. 4 2 $ 0 1 , 1 1 , 1 2 , 2 0    NB. input
dims=. 3 3                              NB. input
empty=. 0=# points                      NB. 1
corner=. points (+/@e.~0,3 2$0,<:) dims NB. 2
dir8=. ,/,"0/~i:1                       NB. the 4 directions
dir4=. 5 2$0 0,i:1                      NB. the 8 directions
borders=. ]e./"2+"1/~                   NB. connection matrix: 1 iff. a borders b
expand=. +./"2@#~^:_                    NB. repeat in the matrix:
                                            if a<->b and b<->c then a<->c
group=. ] <./~ expand@borders           NB. partitions points to groups
                                            based on connection matrix
con8=. (2>[:#dir8&group) points             NB. 3
con4=. ([:*/6>#&>) (dir4 group points)      NB. 4
forms=. (/:~@,@:(-/~)&>) (dir4 group points)
unique=. (-:~.) forms                       NB. 5
f=. empty + corner * con4 * con8 * unique

Answer 4

Charcoal, 231 213 bytes

ＷＳ⊞υιυ≔⟦⟧ζ≔⟦⟧θ≔⟦⁰⊖Ｌυ⟧ηＦηＦηＦ⁼X§§υικ⊞θ⟦ικ⟧Ｗθ«≔…θ¹θＦθ«Ｊ⊟κ⊟κ¿⁼XＫＫ«↓#Ｆ⁴«Ｍ✳⊕⊗λ⊞θ⟦ⅉⅈ⟧»»»≔Φ⪪⭆ＫＡ⁼#κＬυΣκθＵＭθ✂κ⌊Ｅθ⌕μ1⊕⌈Ｅθ⊟⌕Ａμ1≔⟦⟧ηＦ⁴«⊞ηθ≔⮌θθ⊞ηθ≔Ｅ§θ⁰⭆θ§νμθ»⊞ζ⌊ηＵＭＫＡ⎇⁼#κ*κ≔⟦⟧θＦ⌕ＡＫＡX«Ｊ﹪κＬυ÷κＬυ¿№ＫＭ*⊞θ⟦ⅉⅈ⟧»»¿№ＫＡX⎚«⎚¬⊙ζ∨⊖№ζι‹⁵Σ⪫ιω

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for valid, nothing if invalid. Explanation:

ＷＳ⊞υιυ

Copy the board to the canvas.

≔⟦⟧ζ

Start with no pieces discovered.

≔⟦⟧θ

Start with no connected squares to check.

≔⟦⁰⊖Ｌυ⟧ηＦηＦη

Check the corners.

Ｆ⁼X§§υικ

If there is a piece in this corner, then...

⊞θ⟦ικ⟧

add that to the list of connected squares.

Ｗθ«

Repeat while there is at least one connected square.

≔…θ¹θ

Take the first square.

Ｆθ«Ｊ⊟κ⊟κ¿⁼XＫＫ«↓#Ｆ⁴«Ｍ✳⊕⊗λ⊞θ⟦ⅉⅈ⟧»»»

Perform a flood fill to complete this piece.

≔Φ⪪⭆ＫＡ⁼#κＬυΣκθＵＭθ✂κ⌊Ｅθ⌕μ1⊕⌈Ｅθ⊟⌕Ａμ1

Represent the piece as a binary matrix (using strings of 0s and 1s originally because Charcoal apparently can't reverse a binary array but it turns out that strings allow me to save another byte anyway) and extract the minimum enclosing rectangle.

≔⟦⟧ηＦ⁴«⊞ηθ≔⮌θθ⊞ηθ≔Ｅ§θ⁰⭆θ§νμθ»

Generate all the rotations and reflections of the piece.

⊞ζ⌊η

Add the minimum to the list of discovered pieces.

ＵＭＫＡ⎇⁼#κ*κ

Change the piece character from # to *.

Ｆ⌕ＡＫＡX«Ｊ﹪κＬυ÷κＬυ¿№ＫＭ*⊞θ⟦ⅉⅈ⟧»

Find all Xs that are adjacent to a *.

»¿№ＫＡX⎚

If there are any Xs left then they were disconnected so just clear the canvas.

«⎚¬⊙ζ∨⊖№ζι‹⁵Σ⪫ιω

Output a - only if all the discovered pieces are unique and have no more than 5 tiles.