Sébastien Labbé, version 1 of arXiv:1808.07768, August 2018
Sébastien Labbé, version 2 of arXiv:1808.07768, April 2019
Sébastien Labbé, first online version in DCG, November 2019. We did changes to make the code work in Python 3 which is used in Sage starting from version 9.0.
Références:
A self-similar aperiodic set of 19 Wang tiles, Geometriae Dedicata, (2018)
doi:10.1007/s10711-018-0384-8, arXiv:1802.03265
Substitutive structure of Jeandel-Rao aperiodic tilings, August 2018, 38 p. arXiv:1808.07768
Sage version 8.7 or above should work:
version()
The installation of the optional Sage package slabbe is a prerequisite. Remove the dash sign (#
) and evaluate the following cell to install slabbe optional package.
The installation of graphviz and of the optional Sage package dot2tex is a prerequisite to construct the graphs at the end of the notebook.
Finally, I am using rise for the presentation and tikzmagic in Jupyter cells.
#!sage -pip install slabbe>=0.4.4
#!sage -pip install dot2tex
#!sage -pip install rise
#!sage -pip install git+git://github.com/robjstan/tikzmagic.git
The time it takes to evaluate all cells of this notebook depend on the chosen available solver.
Solver | Type | Time to run this notebook |
---|---|---|
dancing_links | Exact cover solver | about 2 minutes |
Gurobi | MILP solver | about 4 minutes |
Glucose | SAT solver | about 30 minutes (estimated) |
The above timing were computed on a 2019 computer with 8 available cpus.
Dancing links is an algorithm proposed by D. Knuth to solve the Exact Cover Problem and is available in plain Sage.
Gurobi is a MILP solver. It is a proprietary software, but it is free for researchers and students. See this tutorial to make Gurobi available through Sage.
Glucose is a SAT solver developped at LaBRI (Bordeaux). It can be installed in sage>=8.7.beta0 easily:
sage -i glucose
from sage.misc.package import is_package_installed
from sage.doctest.external import has_gurobi
if has_gurobi():
solver = 'gurobi'
elif is_package_installed('glucose'):
solver = 'glucose'
else:
solver = 'dancing_links'
solver = 'dancing_links' # more time efficient
print("We are using solver = '{}'".format(solver))
Colors setup:
from collections import defaultdict
color = defaultdict(lambda : 'white')
color.update({0:'white', 1:'red', 2:'cyan', 3:'green', 4:'lightgray'})
color.update({str(k):v for k,v in color.items()})
Loading modules from slabbe and tikzmagic.
If needed, here is the command to install tikzmagic:
sage -pip install git+git://github.com/robjstan/tikzmagic.git
from slabbe import WangTileSet, Substitution2d
import tikzmagic
Latex macros:
$\newcommand{T}{{\mathcal{T}}}$ $\newcommand{U}{{\mathcal{U}}}$ $\newcommand{N}{{\mathbb{N}}}$ $\newcommand{Z}{{\mathbb{Z}}}$ $\newcommand{R}{{\mathbb{R}}}$
tiles = [(2,4,2,1), (2,2,2,0), (1,1,3,1), (1,2,3,2), (3,1,3,3), (0,1,3,1), (0,0,0,1), (3,1,0,2), (0,2,1,2), (1,2,1,4), (3,3,1,2)]
tiles = [[str(a) for a in t] for t in tiles]
T0 = WangTileSet(tiles)
T0.tikz(font=r'\small', size=1.2, ncolumns=11, color=color)
Let $$\Omega_0=\Omega_{\T_0}=\{w:\Z\times\Z\to\T_0\mid w \text{ is a valid Wang tiling}\}$$ be the set of tilings made with the 11 Jeandel-Rao tiles.
%time solution = T0.solver(30,15).solve(solver='glucose')
solution.tikz(color=color)
The substitutive structure of Jeandel-Rao tilings $\Omega_0$ looks like this:
%tikz -i subs-struct.tikz --no-wrap
The current Jupyter notebook computes
Algorithm.
INPUTS: $\T$ is a Wang tile set; $i\in\{1,2\}$ is a direction $e_i$; $r\in\N$ is some radius.
FindMarkers($\mathcal{T}$, $i$, $r$)
Return ${S \in\textbf{Subsets}(U) \mid
\left(S\times S\right) \cap D_i=\varnothing\}$
The output contains zero, one or more subsets of markers in the direction $i$.
T0.tikz(font=r'\small', ncolumns=11, size=1.2, color=color)
%time T0.find_markers(i=2, radius=1, solver=solver) # 229ms with dancing_links, 32s with Glucose, 1.4s with Gurobi
M0 = [0,1]
T1,omega0 = T0.find_substitution(M=M0, i=2, side='left', solver=solver)
show(omega0)
T1.tikz(font=r'\small', size=1.2, ncolumns=13)
T1.tikz(font=r'\small', ncolumns=20, size=1.2)
%time T1.find_markers(i=2, radius=1, solver=solver) #385ms with dancing_links, 46s with Glucose, 2s with Gurobi
M1 = [8, 9, 10, 11, 12]
T2,omega1 = T1.find_substitution(M=M1, i=2, side='left', solver=solver)
show(omega1)
T2.tikz(font=r'\small', size=1.2, ncolumns=20)
T2.tikz(font=r'\small', size=1, ncolumns=20)
%time T2.find_markers(i=2, radius=2, solver=solver) # 4s with dancing_links, 2min 23s with Glucose, 15s with Gurobi
M2 = [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
T3,omega2 = T2.find_substitution(M=M2, i=2, side='left', radius=2, solver=solver)
show(omega2)
T3.tikz(font=r'\small', size=1, ncolumns=24)
T3.tikz(font=r'\small', size=1, ncolumns=24)
%time T3.find_markers(i=2, radius=3, solver=solver) # 13s with dancing_links, 4min 55s with Glucose, 59s with Gurobi
M3 = [0, 1, 2, 3]
T4p,omega3p = T3.find_substitution(M=M3, i=2, side='right', radius=3, solver=solver)
show(omega3p)
T4p.tikz(font=r'\small', size=1.2, ncolumns=15)
T4p.tikz(font=r'\small', size=1.2, ncolumns=15)
We check that tiles #24 and #28 can be removed from T4p. Since tile #28 is always to the left of #24, it suffices to check that the tile #24 does not admit a large enough surrounding (here of width 71 and heigth 9).
Gurobi or Glucose can solve this in a reasonable amount of time (<6s):
%%time
assert T4p[24] == ('21103', '1', '23310', '0')
S = T4p.solver(width=71, height=9, preassigned_tiles={(35,4):24})
print(S.has_solution(solver='glucose')) # 6s with Gurobi, 4s with Glucose
forbidden = ('21103', '1', '23310', '0'), ('23310', '0', '21330', '0')
id_tiles = [(i,t) for (i,t) in enumerate(T4p) if t not in forbidden]
indices,tiles = zip(*id_tiles)
d = dict(enumerate(indices))
iota = Substitution2d.from_permutation(d)
T4 = WangTileSet(tiles)
omega3 = omega3p * iota
show(omega3)
T4.tikz(font=r'\small', size=1.2, ncolumns=15)
omega0to4 = omega0*omega1*omega2*omega3
show(omega0to4)
omega0to4.wang_tikz(T4, T0, font=r'\scriptsize', scale=.8, codomain_color=color, ncolumns=10, direction='down', extra_space=1.5)
T4.tikz(font=r'\small', size=1, ncolumns=15)
%time T4.find_markers(i=1, radius=1, solver=solver)
%time T4.find_markers(i=2, radius=1, solver=solver)
We have a problem: the Wang tile set $\T_4$ has markers neither in the direction $e_1$ nor $e_2$
So increasing the surrounding radius
will not help here.
Even worse, we have two problems...
The first problem is the presence of horizontal fracture lines which we can break by adding decorations on the horizontal edges of few tiles. We have to do it in a way that we forbid sliding along fracture lines and without destroying the overall structure of Wang tilings in $\Omega_4$.
We create the tile set $\mathcal{T}_5$ by adding decorations on $\mathcal{T}_4$.
For few tiles, the horizontal color 0 is replaced by color 6.
For few tiles, the horizontal color 1 is replaced by color 5.
tiles5 = [('2113', '5', '2130', '1'),
('2130', '1', '2103', '5'),
('2133', '1', '2113', '1'),
('2113', '5', '2330', '0'),
('2130', '6', '2300', '0'),
('2103', '5', '2310', '0'),
('2310', '1', '2033', '6'),
('2300', '1', '2033', '6'),
('2300', '0', '2030', '6'),
('2030', '1', '2103', '0'),
('2033', '1', '2113', '0'),
('2330', '1', '2133', '6'),
('2330', '0', '2130', '6'),
('21113', '5', '21330', '1'),
('21130', '6', '21300', '1'),
('21103', '5', '21310', '1'),
('21310', '1', '21033', '5'),
('21310', '0', '21030', '5'),
('21300', '1', '21033', '5'),
('21300', '0', '21030', '5'),
('21030', '1', '21103', '1'),
('21033', '1', '21113', '1'),
('21330', '0', '21130', '1'),
('21330', '0', '21130', '5'),
('21130', '6', '23300', '0'),
('21030', '6', '23100', '0'),
('23100', '0', '20330', '6'),
('20330', '0', '21130', '0'),
('23300', '0', '21330', '6')]
T5 = WangTileSet(tiles5)
T5.tikz(font=r'\small', size=1.2, ncolumns=15)
The morphism $\pi$ erases the decorations on tiles of $\mathcal{T}_5$.
It projects the horizontal color 6 back to color 0, and the horizontal color 5 back to color 1.
On tiles, the map $\pi:\mathcal{T}_5\to\mathcal{T}_4$ is not injective as it maps two tiles (#22 and #23) onto the same (#22).
def project_56(t, p56='10'):
L = []
d = dict(zip('56', p56))
for w in t:
for a in '56':
w = w.replace(a, d[a])
L.append(w)
return tuple(L)
T4_tiles_list = T4.tiles()
d = {}
for i,t in enumerate(T5):
pt = project_56(t, p56='10')
j = T4_tiles_list.index(pt)
d[i] = j
omega4_pi = Substitution2d.from_permutation(d)
show(omega4_pi)
But surprise, on tilings, the map $\pi:\Omega_5\to\Omega_4$ defines a $2$-dimensional morphism which is an embedding, i.e., injective.
T5.tikz(font=r'\small', size=1, ncolumns=15)
%time T5.find_markers(i=1, radius=1, solver=solver)
%time T5.find_markers(i=2, radius=1, solver=solver)
We still have a problem: the Wang tile set $\T_5$ has markers neither in the direction $e_1$ nor $e_2$
So increasing the surrounding radius
will not help here.
Let's look at tilings in $\Omega_5$.
tiling = T5.solver(30,10).solve(solver='glucose')
P = tiling.tile_positions([1, 6, 7, 8, 11, 12, 16, 17, 18, 19, 23, 26, 28])
s = '\n'.join([r'\fill[yellow] {} rectangle {};'.format((a,b), (a+1,b+1)) for (a,b) in P])
tiling.tikz(extra_before=s)
The second problem is that $\T_5$ does not have markers, it has diagonal markers, i.e., markers appears on lines of slope 1.
To fix this, instead of introducing the notion of diagonal markers, we choose to transform the Wang tile set in a way that it shears the tiling by the matrix $\left(\begin{smallmatrix} 1 & -1 \\ 0 & 1\end{smallmatrix}\right)$ so that markers become vertical.
%tikz -i shear.tikz -p amssymb --no-wrap
This transformation on tiles yields a homeomorphism $\eta:\Omega_6\to\Omega_5$ which commutes the normal shift on $\Omega_5$ into the sheared shift on $\Omega_6$.
%time T6,omega5_sheer = T5.shear(radius=2, solver=solver) # 6s with dancing_links, 3min 12s with Glucose, 22s with Gurobi
show(omega5_sheer)
T6.tikz(font=r'\small', size=1.2, ncolumns=15)
T6.tikz(font=r'\small', size=1.2, ncolumns=15)
%time T6.find_markers(i=1, radius=1, solver=solver) # 5s with dancing_links, 4min 25s with Glucose, 17s with Gurobi
Youpi! The tile set $\T_6$ has 3 subsets of markers in the direction $e_1$. Thus, we may chose one, desubstitute and compute $\T_7$.
M6 = [1, 6, 7, 8, 11, 12, 16, 17, 18, 19, 23, 26, 28]
T7,omega6 = T6.find_substitution(M=M6, i=1, radius=1, side='left', solver=solver)
show(omega4_pi*omega5_sheer*omega6)
T7.tikz(font=r'\small', size=1.2)
T7.tikz(font=r'\small', size=1.2)
%time T7.find_markers(i=1, radius=1, solver=solver) # 2s with dancing_links, 2min with Glucose, 6s with Gurobi
M7 = [0, 1, 2, 3, 4, 5, 6]
T8,omega7 = T7.find_substitution(M=M7, i=1, radius=1, solver=solver)
show(omega7)
T8.tikz(font=r'\small', size=1.2)