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!