MAX_SIZE = 9
V = set()
def go(positions):
if positions in V:
return
V.add(positions)
if len(positions) == MAX_SIZE:
return
for (x, y) in positions:
for dx, dy in zip([0, -1, 0, +1], [-1, 0, +1, 0]):
nx, ny = x + dx, y + dy
new_positions = list(positions) + [(nx, ny)]
new_positions = tuple(sorted(set(new_positions)))
go(new_positions)
go(((0,0),))
print(f"WITH AT MOST {MAX_SIZE} PIECES THERE ARE {len(V)} SETS.")
TUFYX1NJWkUgPSA5ClYgPSBzZXQoKQoKZGVmIGdvKHBvc2l0aW9ucyk6CiAgICBpZiBwb3NpdGlvbnMgaW4gVjoKICAgICAgICByZXR1cm4KCiAgICBWLmFkZChwb3NpdGlvbnMpCgogICAgaWYgbGVuKHBvc2l0aW9ucykgPT0gTUFYX1NJWkU6CiAgICAgICAgcmV0dXJuCgogICAgZm9yICh4LCB5KSBpbiBwb3NpdGlvbnM6CiAgICAgICAgZm9yIGR4LCBkeSBpbiB6aXAoWzAsIC0xLCAwLCArMV0sIFstMSwgMCwgKzEsIDBdKToKICAgICAgICAgICAgbngsIG55ID0geCArIGR4LCB5ICsgZHkKICAgICAgICAgICAgbmV3X3Bvc2l0aW9ucyA9IGxpc3QocG9zaXRpb25zKSArIFsobngsIG55KV0KICAgICAgICAgICAgbmV3X3Bvc2l0aW9ucyA9IHR1cGxlKHNvcnRlZChzZXQobmV3X3Bvc2l0aW9ucykpKQogICAgICAgICAgICBnbyhuZXdfcG9zaXRpb25zKQoKZ28oKCgwLDApLCkpCnByaW50KGYiV0lUSCBBVCBNT1NUIHtNQVhfU0laRX0gUElFQ0VTIFRIRVJFIEFSRSB7bGVuKFYpfSBTRVRTLiIpCg==