Comments on Determine if a polyomino is "prime"
Post
Determine if a polyomino is "prime"
An $n$-polyomino is a connected subset of the square tiling consisting of $n$ squares. We will not require that polyominos be simply connected, that is they can have holes.
We will say a $n$-polyomino is prime if it cannot be disected into disjoint $k$-polyominos for any 1<$k$<$n$. For example this square 4-polyomino:
XX
XX
can be dissected into two 2-polyominos, but this "T"-shaped 4-polyomino cannot:
XXX
X
The $k$-polyominos do not need to be equal for example:
XXXXX
X XX
This 8-polyomino can be subdivided into the two polyominos shown in the last examples. They are not equal but they are both 4-polyominos so the example is not prime.
Naturally if $n$ is a prime number all $n$-polyominos are prime, however as shown above there are prime $n$-polyominos where $n$ is not prime. Here are examples for the next couple composite numbers
6
X
XXXX
X
8
X
XXXXX
X X
9
XXXXXXXX
X
10
XXXXXX
X
XXX
12
XXXXXXXXX
X X
X
14
XXXXXXXXXXXX
X X
15
XXX
X X X
XXXXXX
X X
X
Challenge
Given a polyomino as input output one consistent value if it is prime and another consistent distinct value if it is not prime.
This is code-golf the goal being to minimize the size of your source code as measured in bytes.
3 comment threads