Conway criterion is a method to test if a given polygon can tile (i.e. cover without overlapping) an infinite plane. It states that a polygon can tile the plane if the following conditions are met:

  • The given polygon does not have any holes in it.
  • It is possible to choose six consecutive1 points \$A,B,C,D,E,F\$ on its perimeter, so that
    • The boundary part of \$A\$ to \$B\$ must be equal to that of \$E\$ to \$D\$ in its size, shape, and orientation;
    • Each of the boundary parts \$BC\$, \$CD\$, \$EF\$, and \$FA\$ must have 180-degrees rotational symmetry; and
    • At least 3 out of the six points must be distinct from each other.

1) By consecutive, the six points must appear in the given order if you walk around the shape in one direction (either CW (clockwise) or CCW (counter-clockwise)). A boundary part between two consecutive points may contain zero, one, or multiple line segments.

If all the conditions are met, the given shape can tile the plane using only translation and 180-degree rotation. However, failing the condition doesn't mean the piece can't tile the plane. This happens when the tiling involves 90-degree rotations and/or reflections, or the tiling does not use 180-degree rotation at all.

The following is one example that satisfies Conway criterion:

enter image description here

with its plane tiling:

enter image description here


Given a polyomino without holes as input, determine if it satisfies Conway criterion.

You can take the input in any sensible ways, including but not limited to

  • a 2D grid;
  • a list of coordinates of the cells;
  • a list of coordinates on the boundary (including non-vertices or not);
  • a list of steps starting from some point on the perimeter in NSEW notation, ...

If you use the input format that describes the perimeter (e.g. the last two formats above), you can assume that the input (the sequence of points or steps on the perimeter) is given in certain direction (either CW or CCW), but you cannot assume that it starts at any certain position.

Standard rules apply. The shortest code in bytes wins.

Test cases

The test cases are given as 2D grid, where O is a part of the polyomino and . is an empty space.


the example above

the F pentomino
one possible set of points:
  |   |
+-+ +-+
|   |
B-+ D
  | |

|     |
F +-+ +-+
| | |   |
+-+ A---B

a nonomino that can tile with or without 180 degrees rotation

can you spot ABCDEF here? (hint: two points out of ABCDEF are not on the vertices)

how about this? (hint: AB and DE are zero-length)


can tile the plane, but needs 90 deg rotation

cannot tile the plane at all

can tile with only translation, but not with 180 degrees rotation

  • \$\begingroup\$ Can we assume that the six indicated points can always be taken to be lattice points on the boundary? \$\endgroup\$ Commented May 12, 2020 at 15:32
  • \$\begingroup\$ @GregMartin Yes, this can be proven. \$\endgroup\$
    – Nitrodon
    Commented May 12, 2020 at 18:54

1 Answer 1


Python 3.8 (pre-release), 371 ... 338 336 bytes

Takes as input a list of complex numbers, denoting the boundary coordinates in counterclockwise order.

-9 bytes thanks to @ovs
-2 bytes thanks to @Bubbler

import itertools as Z
def f(P):Q=P*2;I=Q.index;L=len;return any(L({*map(complex.__sub__,T:=(J:=lambda x,y:Q[(j:=I(p[x])):I(p[y],j)+1])(0,1),U:=J(3,4)[::-1])})<2<L({*p})and(L(T)==L(U))&all((B:=J(a,-~a%6))==[B[L(B)//2]-E+B[~L(B)//2]for E in B][::-1]for a in[1,2,4,5])for S in zip(*[Q[I(i):]for i in P])for p in eval('Z.'+dir(Z)[11])(S,6))

Try it online!

  • 2
    \$\begingroup\$ 338 bytes with import itertools as Z and eval('Z.'+dir(Z)[11]) instead of combinations_with_replacement. \$\endgroup\$
    – ovs
    Commented May 12, 2020 at 7:21
  • 1
    \$\begingroup\$ Try it online! \$\endgroup\$
    – ovs
    Commented May 12, 2020 at 7:25
  • \$\begingroup\$ @ovs Very nice! That's a smart way of reducing extremely long function names. \$\endgroup\$ Commented May 12, 2020 at 16:09
  • \$\begingroup\$ You still have a len. \$\endgroup\$
    – Bubbler
    Commented May 13, 2020 at 0:00
  • \$\begingroup\$ @Bubbler Good catch :) \$\endgroup\$ Commented May 13, 2020 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.