Aperiodic monotile

The hat: an aperiodic monotile

This module contains code to construct tilings of rectangles by the aperiodic monotile discovered by David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss in March 2023.

It makes a reduction to an instance of the Universal Cover problem, which can be solved in SageMath using Donald Knuth’s dancing links algorithm, SAT solvers or Mixed-Integer Linear programs (MILP).

The code uses the coordinate system defined in the file validate/kitegrid.pdf found in the source code associated to the article.

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(20,20)
sage: s.the_dlx_solver()                               # long time (1s)
Dancing links solver for 4800 columns and 10320 rows
sage: s.one_solution(solver='glucose') is not None     # long time (3s)  # optional glucose
True
sage: G = s.draw_one_solution(solver='glucose')        # long time (12s) # optional glucose
sage: G                                                # long time (3s)  # optional glucose
Graphics object consisting of 4465 graphics primitives
sage: G.save('solution_20x20.png', figsize=20)         # not tested
class slabbe.aperiodic_monotile.MonotileSolver(width=10, heigth=10)

Bases: object

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver()
canonical_kite(v)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.canonical_kite((2,3))
[(0, 0), (1, 1), (0, 2), (-1, 2)]
canonical_vertex(v)

Return the vertex in the fundamental domain [(0,1), (1,0), (1,-1), (0,-1), (-1,0), (-1,1)] which is in the same orbit under the translations by matrix.column([(-2,4), (2,2)])

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: H = [(0,1), (1,0), (1,-1), (0,-1), (-1,0), (-1,1)]
sage: s = MonotileSolver(2,2)
sage: [s.canonical_vertex(h) for h in H]
[(0, 1), (1, 0), (1, -1), (0, -1), (-1, 0), (-1, 1)]
sage: set(s.canonical_vertex(v) for v in s.the_box())
{(-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0)}
columns(extra=4)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(1,1)
sage: s.columns()
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
draw_one_solution(ignore_incomplete=True, extra=4, solver=None, color_by_id=False, illustrate_3_mod_6=False)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.draw_one_solution()
Graphics object consisting of 17 graphics primitives
draw_the_12_shapes()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.draw_one_solution()
Graphics object consisting of 17 graphics primitives
hexagonal_projection()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(20,20)
sage: s.hexagonal_projection()
[        1       1/2]
[        0 1/2*sqrt3]
kite_edges(v)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.kite_edges((2,3))
[((3, sqrt3), (9/2, 3/2*sqrt3)),
 ((9/2, 3/2*sqrt3), (4, 2*sqrt3)),
 ((4, 2*sqrt3), (3, 2*sqrt3)),
 ((3, 2*sqrt3), (3, sqrt3))]
one_solution(extra=4, solver=None)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.one_solution()           # random
[5, 4, 89, 108, 79, 62, 24, 86, 21, 25]
sage: s = MonotileSolver(8,8)
sage: s.one_solution(solver='glucose') is not None   # optional glucose
True
one_solution_list_of_edges(ignore_incomplete=True, extra=4, solver=None)

Return the list of edges of a solution.

Each edge appears only once in the output. This allows to avoid the laser cut machine to pass twice at the same place.

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: L = s.one_solution_list_of_edges()
sage: sorted(L)                                # random
[frozenset({(3, 0), (4, 0)}),
 frozenset({(3, 2*sqrt3), (4, 2*sqrt3)}),
 frozenset({(-3/2, 1/2*sqrt3), (-1, sqrt3)}),
 frozenset({(0, sqrt3), (0, 2*sqrt3)}),
 frozenset({(3, sqrt3), (3, 2*sqrt3)}),
 frozenset({(9/2, -1/2*sqrt3), (6, 0)}),
 frozenset({(9/2, 5/2*sqrt3), (6, 2*sqrt3)}),
 frozenset({(6, 0), (6, sqrt3)}),
 frozenset({(0, 0), (3/2, 1/2*sqrt3)}),
 frozenset({(-1, sqrt3), (0, sqrt3)}),
 frozenset({(0, 2*sqrt3), (3/2, 5/2*sqrt3)}),
 frozenset({(6, sqrt3), (7, sqrt3)}),
 frozenset({(15/2, 3/2*sqrt3), (8, 2*sqrt3)}),
 frozenset({(6, 2*sqrt3), (15/2, 5/2*sqrt3)}),
 frozenset({(4, 0), (9/2, 1/2*sqrt3)}),
 frozenset({(3/2, 1/2*sqrt3), (2, 0)}),
 frozenset({(4, 2*sqrt3), (9/2, 5/2*sqrt3)}),
 frozenset({(-3/2, 1/2*sqrt3), (0, 0)}),
 frozenset({(7, sqrt3), (15/2, 3/2*sqrt3)}),
 frozenset({(3/2, 5/2*sqrt3), (2, 2*sqrt3)}),
 frozenset({(4, 0), (9/2, -1/2*sqrt3)}),
 frozenset({(2, 2*sqrt3), (3, 2*sqrt3)}),
 frozenset({(2, 0), (3, 0)}),
 frozenset({(3, sqrt3), (9/2, 1/2*sqrt3)}),
 frozenset({(15/2, 5/2*sqrt3), (8, 2*sqrt3)})]
sage: sum(line(edge) for edge in L)
Graphics object consisting of ... graphics primitives
one_solution_tikz(ignore_incomplete=True, extra=4, solver=None)

Return the list of edges of a solution.

Each edge appears only once in the output. This allows to avoid the laser cut machine to pass twice at the same place.

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.one_solution_tikz()
\documentclass[tikz]{standalone}
\begin{document}
\begin{tikzpicture}
\draw[red] (..., ...) -- (..., ...);
\draw[red] (..., ...) -- (..., ...);
\draw[red] (..., ...) -- (..., ...);
\draw[red] (..., ...) -- (..., ...);
...
\draw[red] (..., ...) -- (..., ...);
\draw[red] (..., ...) -- (..., ...);
\draw[red] (..., ...) -- (..., ...);
\draw[red] (..., ...) -- (..., ...);
\end{tikzpicture}
\end{document}
plot_domain()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: s.plot_domain()
Graphics object consisting of 1 graphics primitive
plot_kite(v, color, **kwds)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: G = s.plot_domain() + s.plot_kite((2,3), color='red')
row_number_to_coord()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(10, 10)
sage: len(s.row_number_to_coord())
1200
rows(extra=4)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(2,2)
sage: len(s.rows())
168
the_box()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: MonotileSolver(1,1).the_box()
Polyomino: [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1,
2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)], Color: gray
sage: len(MonotileSolver(1,1).the_box())
12
sage: len(MonotileSolver(1,2).the_box())
24
sage: len(MonotileSolver(2,1).the_box())
24
sage: len(MonotileSolver(2,2).the_box())
48
the_dlx_solver(extra=4)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(1,1)
sage: d = s.the_dlx_solver(); d
Dancing links solver for 12 columns and 60 rows
sage: d.one_solution()                 # random
[0, 12, 30]

Extra = 4 seems sufficeent:

sage: s = MonotileSolver(2,4)
sage: s.the_dlx_solver(extra=1)
Dancing links solver for 96 columns and 288 rows
sage: s.the_dlx_solver(extra=2)
Dancing links solver for 96 columns and 288 rows
sage: s.the_dlx_solver(extra=3)
Dancing links solver for 96 columns and 288 rows
sage: s.the_dlx_solver(extra=4)
Dancing links solver for 96 columns and 288 rows

No solution?:

sage: s = MonotileSolver(5,5)
sage: s.the_dlx_solver(extra=0)
Dancing links solver for 300 columns and 600 rows
sage: s.the_dlx_solver(extra=1)
Dancing links solver for 300 columns and 780 rows
sage: s.the_dlx_solver(extra=2)
Dancing links solver for 300 columns and 780 rows
sage: d = s.the_dlx_solver(extra=2)
sage: L = d.one_solution()
sage: type(L)
<class 'list'>
the_monotiles_in_a_box(extra=0, verbose=False)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(1,1)
sage: len(s.the_monotiles_in_a_box(extra=0))
24
sage: len(s.the_monotiles_in_a_box(extra=1))
216
sage: len(s.the_monotiles_in_a_box(extra=2))
600
tile_positions_in_solution(solution, extra=4)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import MonotileSolver
sage: s = MonotileSolver(4,4)
sage: solution = s.one_solution()
sage: s.tile_positions_in_solution(solution)    # random
{0: [(3, 5), (-5, 9), (5, 1), (9, 5)],
 1: [(3, 10)],
 2: [(0, 3)],
 3: [(8, 0), (12, 4), (16, 2)],
 4: [(13, 0), (5, 10), (11, 10)],
 5: [(-2, 7)],
 7: [(10, 9)],
 9: [(4, 6)],
 11: [(-5, 4)]}
slabbe.aperiodic_monotile.polyomino_mirror(p)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import polyomino_mirror
sage: V = [(0,1), (1,0), (1,-1), (0,-1), (-1,0), (-1,1)]
sage: from sage.combinat.tiling import Polyomino
sage: hexagon = Polyomino(V)
sage: image = polyomino_mirror(hexagon)
sage: image == hexagon
True
sage: image
Polyomino: [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0)],
Color: gray
slabbe.aperiodic_monotile.polyomino_reversal(p)

EXAMPLES:

sage: from slabbe.aperiodic_monotile import polyomino_reversal
sage: V = [(0,1), (1,0), (1,-1), (0,-1), (-1,0), (-1,1)]
sage: from sage.combinat.tiling import Polyomino
sage: hexagon = Polyomino(V)
sage: image = polyomino_reversal(hexagon)
sage: image == hexagon
True
sage: image
Polyomino: [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0)],
Color: gray
slabbe.aperiodic_monotile.the_canonical_12_monotiles()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import the_canonical_12_monotiles
sage: the_canonical_12_monotiles()
{Polyomino: [(0, 0), (0, 2), (0, 3), (1, 0), (2, 1), (2, 2), (3, 0), (4, 0)], Color: gray: 0,
 Polyomino: [(0, 0), (0, 1), (0, 3), (0, 4), (1, 1), (2, 0), (2, 2), (3, 1)], Color: gray: 1,
 Polyomino: [(0, 2), (0, 4), (1, 0), (1, 2), (1, 3), (2, 0), (3, 1), (4, 0)], Color: gray: 2,
 Polyomino: [(0, 3), (1, 2), (1, 4), (2, 3), (3, 0), (3, 1), (3, 3), (3, 4)], Color: gray: 3,
 Polyomino: [(0, 3), (1, 3), (2, 1), (2, 2), (3, 3), (4, 0), (4, 1), (4, 3)], Color: gray: 4,
 Polyomino: [(0, 4), (1, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 0), (4, 2)], Color: gray: 5,
 Polyomino: [(0, 0), (0, 1), (0, 3), (0, 4), (1, 2), (2, 0), (2, 2), (3, 0)], Color: gray: 6,
 Polyomino: [(0, 0), (0, 2), (1, 0), (1, 1), (1, 3), (2, 2), (3, 0), (4, 0)], Color: gray: 7,
 Polyomino: [(0, 1), (0, 2), (0, 4), (1, 3), (2, 0), (2, 1), (3, 1), (4, 0)], Color: gray: 8,
 Polyomino: [(0, 3), (1, 3), (2, 1), (3, 0), (3, 2), (3, 3), (4, 1), (4, 3)], Color: gray: 9,
 Polyomino: [(0, 4), (1, 2), (1, 4), (2, 2), (3, 0), (3, 1), (3, 3), (3, 4)], Color: gray: 10,
 Polyomino: [(0, 4), (1, 3), (2, 3), (2, 4), (3, 1), (4, 0), (4, 2), (4, 3)], Color: gray: 11}
slabbe.aperiodic_monotile.the_rotated_reflected_monotiles()

EXAMPLES:

sage: from slabbe.aperiodic_monotile import the_rotated_reflected_monotiles
sage: L = the_rotated_reflected_monotiles()
sage: len(L)
12

TESTS:

sage: monotiles = the_rotated_reflected_monotiles()
sage: box = monotiles[0]
sage: from sage.combinat.tiling import TilingSolver
sage: solver = TilingSolver(monotiles, box, rotation=False,
....:         reflection=False, reusable=True, outside=False)
sage: it = solver.solve()
sage: next(it)
[Polyomino: [(-1, 1), (-1, 3), (-1, 4), (0, 1), (1, 2), (1, 3), (2,
1), (3, 1)], Color: gray]