Validate Blokus Board 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!
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&gt;[] 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) &gt; 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)