Sage version 8.3 or above should work:
version()
'SageMath version 8.4.beta1, Release Date: 2018-08-14'
The installation of the optional Sage package slabbe v0.4.3 is a prerequisite. Remove the dash sign (#
) and evaluate the following cell to install slabbe optional package:
#!sage -pip install slabbe==0.4.3
The installation of graphviz and of the optional Sage package dot2tex is a prerequisite to construct the graphs at the end of the notebook.
#!sage -pip install dot2tex
The time it takes to evaluate all cells of this notebook depend on the chosen available solver.
Solver | Time to run this notebook |
---|---|
Gurobi | about 4 minutes |
dancing_links | about 69 minutes |
other MILP solver | unknown |
The above timing were computed on a 2017 computer with 8 available cpus.
Gurobi is a proprietary software, but it is free for researchers and students. See this tutorial to make Gurobi available through Sage.
from sage.doctest.external import has_gurobi
if has_gurobi():
solver = 'gurobi'
else:
solver = 'dancing_links'
print("We are using solver = '{}'".format(solver))
We are using solver = 'gurobi'
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()})
from slabbe import WangTileSet, Substitution2d
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 = [map(str,t) for t in tiles]
T0 = WangTileSet(tiles)
T0.tikz(font=r'\small', size=1, ncolumns=11, color=color)
%time T0.find_markers(i=2, radius=1, solver=solver) # 47s with dancing_links, 1.4s with Gurobi
CPU times: user 1.06 s, sys: 196 ms, total: 1.26 s Wall time: 1.23 s
[[0, 1]]
M0 = [0,1]
T1,s0,_ = T0.find_substitution(M=M0, i=2, side='left', solver=solver)
T1.tikz(font=r'\small', size=1.2)
show(s0)
%time T1.find_markers(i=2, radius=1, solver=solver) #1min 16s with dancing_links, 2s with Gurobi
CPU times: user 1.64 s, sys: 240 ms, total: 1.88 s Wall time: 1.85 s
[[8, 9, 10, 11, 12]]
M1 = [8, 9, 10, 11, 12]
T2,s1,_ = T1.find_substitution(M=M1, i=2, side='left', solver=solver)
T2.tikz(font=r'\small', size=1.2)
show(s1)
%time T2.find_markers(i=2, radius=2, solver=solver) # 5min 25s with dancing_links, 15s with Gurobi
CPU times: user 13.3 s, sys: 752 ms, total: 14.1 s Wall time: 13.9 s
[[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]]
M2 = [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
T3,s2,_ = T2.find_substitution(M=M2, i=2, side='left', radius=2, solver=solver)
T3.tikz(font=r'\small', size=1.2)
show(s2)
%time T3.find_markers(i=2, radius=3, solver=solver) # 10min 12s with dancing_links, 59s with Gurobi
CPU times: user 1min 7s, sys: 1.66 s, total: 1min 9s Wall time: 54.1 s
[[0, 1, 2, 3]]
M3 = [0, 1, 2, 3]
T4p,s3p,_ = T3.find_substitution(M=M3, i=2, side='right', radius=3, solver=solver)
T4p.tikz(font=r'\small', size=1.2)
show(s3p)
Only Gurobi can solve this in a reasonable amount of time (6s)
def check_2_tiles_to_remove_from_T4p():
assert T4p[18] == ('21103', '1', '23310', '0')
S = T4p.solver(width=71, height=9, preassigned_tiles={(35,4):18})
return S.has_solution(solver='Gurobi')
%time check_2_tiles_to_remove_from_T4p()
CPU times: user 14.4 s, sys: 352 ms, total: 14.8 s Wall time: 5.45 s
False
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)
T4.tikz(font=r'\small', size=1.2)
show(iota)
s3 = s3p * iota
show(s3)
tiles5 = [('2030', '1', '2103', '0'),
('2033', '1', '2113', '0'),
('2103', '5', '2310', '0'),
('2113', '5', '2130', '1'),
('2113', '5', '2330', '0'),
('2130', '6', '2300', '0'),
('2130', '1', '2103', '5'),
('2133', '1', '2113', '1'),
('2300', '0', '2030', '6'),
('2300', '1', '2033', '6'),
('2310', '1', '2033', '6'),
('2330', '0', '2130', '6'),
('2330', '1', '2133', '6'),
('20330', '0', '21130', '0'),
('21030', '6', '23100', '0'),
('21030', '1', '21103', '1'),
('21033', '1', '21113', '1'),
('21103', '5', '21310', '1'),
('21113', '5', '21330', '1'),
('21130', '6', '21300', '1'),
('21130', '6', '23300', '0'),
('21300', '0', '21030', '5'),
('21300', '1', '21033', '5'),
('21310', '0', '21030', '5'),
('21310', '1', '21033', '5'),
('21330', '0', '21130', '1'),
('21330', '0', '21130', '5'),
('23100', '0', '20330', '6'),
('23300', '0', '21330', '6')]
T5 = WangTileSet(tiles5)
T5.tikz(font=r'\small', size=1.2)
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
s4_pi = Substitution2d.from_permutation(d)
show(s4_pi)
%time T6,s5_sheer = T5.shear(radius=2) # 20s with dancing_links, 22s with Gurobi
T6.tikz(font=r'\small', size=1.2)
CPU times: user 19 s, sys: 712 ms, total: 19.7 s Wall time: 19.5 s
show(s5_sheer)
%time T6.find_markers(i=1, radius=1, solver=solver) #14min 31s with dancing_links, 17s with Gurobi
CPU times: user 14.2 s, sys: 1.33 s, total: 15.5 s Wall time: 15.4 s
[[2, 3, 4, 5, 14, 17, 18, 19, 20], [6, 8, 9, 10, 11, 12, 21, 22, 23, 24, 26, 27, 28], [0, 1, 7, 13, 15, 16, 25]]
M6 = [6, 8, 9, 10, 11, 12, 21, 22, 23, 24, 26, 27, 28]
T7,s6,_ = T6.find_substitution(M=M6, i=1, radius=1, side='left', solver=solver)
T7.tikz(font=r'\small', size=1.2)
show(s6)
%time T7.find_markers(i=1, radius=1, solver=solver) #4min 44s with dancing_links, 6s with Gurobi
CPU times: user 5.21 s, sys: 660 ms, total: 5.87 s Wall time: 5.8 s
[[0, 1, 2, 9, 10, 11, 12]]
M7 = [0, 1, 2, 9, 10, 11, 12]
T8,s7,_ = T7.find_substitution(M=M7, i=1, radius=1, solver=solver)
T8.tikz(font=r'\small', size=1.2)
show(s7)
%time T8.find_markers(i=2, radius=2, solver=solver) # 5min 9s with dancing_links, 15s with Gurobi
CPU times: user 13.4 s, sys: 632 ms, total: 14.1 s Wall time: 13.9 s
[[0, 1, 2, 3, 4, 5, 6, 7]]
M8 = [0, 1, 2, 3, 4, 5, 6, 7]
T9,s8,_ = T8.find_substitution(M=M8, i=2, radius=2, solver=solver)
T9.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
210300 | 60 | 203300 | 60 | |
211300 | 60 | 210300 | 51 | |
211300 | 60 | 210331 | 51 | |
211300 | 60 | 213300 | 60 | |
203300 | 600 | 210331 | 510 | |
210300 | 510 | 210300 | 511 | |
210300 | 510 | 210331 | 511 | |
210331 | 511 | 211300 | 511 | |
213300 | 600 | 210331 | 511 | |
21030021031 | 51 | 20330020331 | 60 | |
21030021300 | 60 | 20330020300 | 60 | |
21030021300 | 60 | 20330020331 | 60 | |
21130021031 | 51 | 21030020331 | 51 | |
21130021031 | 51 | 21330020331 | 60 | |
20330020300 | 510 | 21030020331 | 510 | |
20330020300 | 510 | 21330020331 | 600 | |
20330020331 | 511 | 21030021300 | 510 | |
20330020331 | 511 | 21033121331 | 510 | |
21030020331 | 511 | 21030021031 | 511 | |
21033121331 | 511 | 21130021031 | 511 | |
21330020331 | 511 | 21030021300 | 511 | |
21330020331 | 511 | 21033121331 | 511 |
show(s8)
%time T9.find_markers(i=1, radius=1, solver=solver) # 6min 23s with dancing_links, 8s with Gurobi
CPU times: user 6.91 s, sys: 700 ms, total: 7.61 s Wall time: 7.55 s
[[0, 1, 2, 3, 9, 10, 11, 12, 13], [5, 7, 16, 18, 19, 20], [4, 6, 8, 14, 15, 17, 21]]
M9 = [0, 1, 2, 3, 9, 10, 11, 12, 13]
T10,s9,_ = T9.find_substitution(M=M9, i=1, radius=1, solver=solver)
T10.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
210331 | 511 | 211300 | 511 | |
210300 | 60060 | 210331 | 51060 | |
211300 | 51060 | 210300 | 51151 | |
211300 | 51060 | 210331 | 51151 | |
211300 | 51160 | 211300 | 51151 | |
211300 | 60060 | 210331 | 51160 | |
21030020331 | 511 | 21030021031 | 511 | |
21033121331 | 511 | 21130021031 | 511 | |
21330020331 | 511 | 21030021300 | 511 | |
21030021031 | 51151 | 21030021300 | 51060 | |
21030021031 | 51151 | 21033121331 | 51060 | |
21030021300 | 51060 | 21030020331 | 51060 | |
21030021300 | 51060 | 21330020331 | 60060 | |
21030021300 | 51160 | 21030021300 | 51060 | |
21030021300 | 51160 | 21033121331 | 51060 | |
21130021031 | 51151 | 21030021031 | 51151 | |
21130021031 | 51151 | 21030021300 | 51160 | |
21130021031 | 51151 | 21033121331 | 51160 |
show(s9)
%time T10.find_markers(i=2, radius=2, solver=solver) # 3min 37s with dancing_links, 11s with Gurobi
CPU times: user 9.94 s, sys: 604 ms, total: 10.5 s Wall time: 10.4 s
[[0, 1, 2, 3, 4, 5]]
M10 = [0, 1, 2, 3, 4, 5]
T11,s10,_ = T10.find_substitution(M=M10, i=2, radius=2, solver=solver)
T11.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
21030020331 | 511 | 21030021031 | 511 | |
21033121331 | 511 | 21130021031 | 511 | |
21330020331 | 511 | 21030021300 | 511 | |
21030021031 | 51151 | 21030021300 | 51060 | |
21030021300 | 51060 | 21030020331 | 51060 | |
21030021300 | 51060 | 21330020331 | 60060 | |
21030021300 | 51160 | 21030021300 | 51060 | |
21030021300 | 51160 | 21033121331 | 51060 | |
21130021031 | 51151 | 21030021300 | 51160 | |
21030020331210331 | 511 | 21030021031211300 | 511 | |
21033121331210331 | 511 | 21130021031211300 | 511 | |
21330020331210331 | 511 | 21030021300211300 | 511 | |
21030021031211300 | 51060 | 21030021300210300 | 51060 | |
21030021031211300 | 51060 | 21033121331210331 | 51060 | |
21030021300210300 | 60060 | 21030020331210331 | 51060 | |
21030021300210300 | 60060 | 21330020331210331 | 60060 | |
21030021300211300 | 60060 | 21033121331210331 | 51060 | |
21130021031211300 | 51060 | 21030021300210300 | 51160 | |
21130021031211300 | 51060 | 21033121331210331 | 51160 | |
21130021031211300 | 51160 | 21030021031211300 | 51151 | |
21130021031211300 | 51160 | 21030021300211300 | 51160 |
show(s10)
%time T11.find_markers(i=1, radius=1, solver=solver) # 5min 25s with dancing_links, 7s with Gurobi
CPU times: user 6 s, sys: 668 ms, total: 6.66 s Wall time: 6.6 s
[[0, 1, 2, 9, 10, 11], [3, 6, 8, 12, 17, 19, 20], [4, 5, 7, 13, 14, 15, 16, 18]]
M11 = [0, 1, 2, 9, 10, 11]
T12,s11,_ = T11.find_substitution(M=M11, i=1, radius=1, solver=solver)
T12.table()
Id | Right | Top | Left | Bottom |
---|---|---|---|---|
21030021300 | 51060 | 21030020331 | 51060 | |
21030021300 | 51060 | 21330020331 | 60060 | |
21030020331 | 51151511 | 21030021300 | 51060511 | |
21033121331 | 51151511 | 21030021300 | 51160511 | |
21330020331 | 51060511 | 21030020331 | 51060511 | |
21330020331 | 51060511 | 21330020331 | 60060511 | |
21330020331 | 51160511 | 21030021300 | 51060511 | |
21330020331 | 51160511 | 21033121331 | 51060511 | |
21030021031211300 | 51060 | 21033121331210331 | 51060 | |
21030021300210300 | 60060 | 21030020331210331 | 51060 | |
21030021300210300 | 60060 | 21330020331210331 | 60060 | |
21030021300211300 | 60060 | 21033121331210331 | 51060 | |
21030020331210331 | 51060511 | 21030021300210300 | 51060511 | |
21030020331210331 | 51060511 | 21033121331210331 | 51060511 | |
21033121331210331 | 51060511 | 21030021300210300 | 51160511 | |
21033121331210331 | 51060511 | 21033121331210331 | 51160511 | |
21033121331210331 | 51160511 | 21030021031211300 | 51151511 | |
21033121331210331 | 51160511 | 21030021300211300 | 51160511 | |
21330020331210331 | 60060511 | 21033121331210331 | 51060511 |
show(s11)
tilesU = ['FOJO','FOHL','JMFP','DMFK','HPJP','HPHN','HKFP','HKDP','BOIO','GLEO','GLCL',
'ALIO','EPGP','EPIP','IPGK','IPIK','IKBM','IKAK','CNIP',]
tilesU = map(tuple, tilesU)
U = WangTileSet(tilesU)
U.tikz(size=1.2)
U.is_equivalent(T12, certificate=True)
(True, {'A': '21030021300211300', 'B': '21030021031211300', 'C': '21330020331210331', 'D': '21033121331', 'E': '21030020331210331', 'F': '21030021300', 'G': '21030021300210300', 'H': '21330020331', 'I': '21033121331210331', 'J': '21030020331'}, {'K': '51160511', 'L': '60060', 'M': '51151511', 'N': '60060511', 'O': '51060', 'P': '51060511'}, Substitution 2d: {0: [[0]], 1: [[1]], 2: [[2]], 3: [[3]], 4: [[4]], 5: [[5]], 6: [[6]], 7: [[7]], 8: [[8]], 9: [[9]], 10: [[10]], 11: [[11]], 12: [[12]], 13: [[13]], 14: [[14]], 15: [[15]], 16: [[16]], 17: [[17]], 18: [[18]]})
%time U.find_markers(i=2, radius=2, solver=solver) # 4min 39s with dancing_links, 13s with Gurobi
CPU times: user 11.6 s, sys: 736 ms, total: 12.3 s Wall time: 12.2 s
[[0, 1, 2, 3, 4, 5, 6, 7]]
M12 = [0, 1, 2, 3, 4, 5, 6, 7]
T13,s12,_ = U.find_substitution(M=M12, i=2, radius=2, solver=solver)
T13.tikz(size=1.2)
show(s12)
%time T13.find_markers(i=1, radius=1, solver=solver) # 5min 34s with dancing_links, 7s with Gurobi
CPU times: user 6.16 s, sys: 684 ms, total: 6.84 s Wall time: 6.74 s
[[0, 1, 3, 8, 9, 14, 15], [4, 5, 6, 11, 16, 17, 18, 20], [2, 7, 10, 12, 13, 19]]
M13 = [0, 1, 3, 8, 9, 14, 15]
T14,s13,_ = T13.find_substitution(M=M13, i=1, radius=1, solver=solver)
T14.tikz(size=1.2)
show(s13)
is_equiv,f,g,permUtoT14 = U.is_equivalent(T14, certificate=True)
assert is_equiv
s12to12 = s12 * s13 * permUtoT14
show(s12to12)
s12to12.wang_tikz(U, U, font=r'\scriptsize', scale=1, codomain_color=color, ncolumns=4,
direction='right', extra_space=1.5)
s0to4 = s0*s1*s2*s3p*iota
s0to4.wang_tikz(T4, T0, font=r'\scriptsize', scale=.8, codomain_color=color, ncolumns=10, direction='down',
extra_space=1.5)
s5to12 = s5_sheer*s6*s7*s8*s9*s10*s11
M = matrix(2, [1,1,0,1])
s5to12sheer = s5to12.apply_matrix_transformation(M)
s5to12sheer.wang_tikz(U, T5, font=r'\scriptsize', scale=.9, ncolumns=2, extra_space=1.5)
s4to12 = s4_pi*s5to12
M = matrix(2, [1,1,0,1])
s4to12sheer = s4to12.apply_matrix_transformation(M)
s4to12sheer.wang_tikz(U, T4, font=r'\scriptsize', scale=.9, ncolumns=2, extra_space=1.5)
s0to12 = s0to4*s4to12sheer
s0to12.wang_tikz(U, T0, font=r'\scriptsize', scale=.8, codomain_color=color, id=None,
ncolumns=4, direction='right', extra_space=1.5)
from slabbe import TikzPicture
G = s12to12.prolongable_origins()
TikzPicture.from_graph(G, rankdir='right')
Gh = DiGraph(T12.dominoes_with_surrounding(i=1,radius=2), format='list_of_edges')
TikzPicture.from_graph(Gh)
Gv = DiGraph(T12.dominoes_with_surrounding(i=2,radius=2), format='list_of_edges')
TikzPicture.from_graph(Gv)
Inverse of frequencies of tiles in $\Omega_4$:
M = matrix(s12to12)
z = polygen(QQ, 'z')
K.<phi> = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
MK = M.change_ring(K)
v = MK.eigenvectors_right()[0][1][0]
v4 = matrix(s4to12) * v
sorted((1/a, i) for (i,a) in enumerate(v4/sum(v4)))
[(5*phi + 3, 19), (6*phi + 4, 25), (8*phi + 5, 1), (8*phi + 5, 21), (10*phi + 6, 2), (10*phi + 6, 4), (10*phi + 6, 10), (10*phi + 6, 13), (10*phi + 6, 14), (10*phi + 6, 16), (10*phi + 6, 18), (10*phi + 6, 26), (13*phi + 8, 22), (16*phi + 10, 3), (16*phi + 10, 5), (16*phi + 10, 6), (16*phi + 10, 11), (16*phi + 10, 15), (16*phi + 10, 17), (16*phi + 10, 20), (16*phi + 10, 27), (26*phi + 16, 0), (26*phi + 16, 7), (26*phi + 16, 8), (26*phi + 16, 12), (26*phi + 16, 23), (42*phi + 26, 9), (42*phi + 26, 24)]
Inverse of frequencies of tiles in $\Omega_0$:
v0 = matrix(s0to4)*matrix(s4to12) * v
sorted((1/a, i) for (i,a) in enumerate(v0/sum(v0)))
[(12/5*phi + 14/5, 7), (2*phi + 6, 0), (2*phi + 6, 1), (2*phi + 6, 3), (2*phi + 6, 6), (2*phi + 6, 9), (5*phi + 4, 5), (8*phi + 2, 4), (8*phi + 2, 8), (8*phi + 2, 10), (18*phi + 10, 2)]