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.

posted over 1 year ago

CC BY-SA 4.0

1y ago

WheatWizard‭

469 reputation 16 5 46 26