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 ... 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, verbose=False)¶
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.
INPUT:
ignore_incomplete
– bool (defaultTrue
)extra
– integer (default:4
)solver
– string (defaultNone
)verbose
– bool (defaultFalse
)
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] (..., ...) -- (..., ...) ... (..., ...) -- (..., ...); \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]