Wang tile, tilings and solver¶
Wang tile solver
We solve the problem of tiling a rectangle by Wang tiles by reducing it to other well-known problems like linear problem, exact cover problem and SAT.
We thus use MILP solvers like Coin or Gurobi, Sat solvers like cryptominisat, picosat or glucose and dancing links solver which is already in Sage.
Coin can be installed with:
sage -i cbc sagelib
Cryptominisat can be installed with:
sage -i cryptominisat sagelib
Glucose can be installed with:
sage -i glucose
EXAMPLES:
sage: from slabbe import WangTileSolver
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)]
sage: W = WangTileSolver(tiles,3,4)
sage: tiling = W.solve()
sage: _ = tiling.tikz().pdf(view=False)
Using different kind of solvers:
sage: tiling = W.solve(solver='GLPK')
sage: tiling = W.solve(solver='dancing_links')
sage: tiling = W.solve(solver='Gurobi') # optional Gurobi
sage: tiling = W.solve(solver='cryptominisat') # optional cryptominisat
sage: tiles = [(1/2,1/2,1/2,1/2), (1,1,1,1), (2,2,2,2)]
sage: W = WangTileSolver(tiles,3,4)
sage: tiling = W.solve()
sage: _ = tiling.tikz().pdf(view=False)
sage: tiles = [(0,3,1,4), (1,4,0,3)]
sage: W = WangTileSolver(tiles,3,4)
sage: tiling = W.solve()
sage: tiling._table
[[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
Kari-Culik (Here 0’ is replaced by 10):
sage: divide_by_2 = [(10,0,10,10), (10,1,10,2), (1/2,0,10,1), (1/2,10,10,1),
....: (1/2,0,1/2,10), (1/2,1,1/2,2), (10,1,1/2,1)]
sage: times_3 = [(1,2,0,1), (2,1,0,1), (2,2,1,1), (0,1,1,0), (0,2,2,0),
....: (1,1,2,0)]
sage: tiles = divide_by_2 + times_3
sage: W = WangTileSolver(tiles,3,4)
sage: tiling = W.solve()
sage: _ = tiling.tikz().pdf(view=False)
Rao-Jeandel:
sage: 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)]
sage: W = WangTileSolver(tiles,3,4)
sage: tiling = W.solve()
sage: _ = tiling.tikz().pdf(view=False)
-
class
slabbe.wang_tiles.
WangTileSet
(tiles)¶ Bases:
object
Construct a Wang tile set.
INPUT:
tiles
– list of tiles, a tile is a 4-tuple (right color, top color, left color, bottom color)
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles)
sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles)
-
admissible_horizontal_words
(length, width, height)¶ Return the horizontal word of given length appearing in every position inside a rectangle of given width and height.
INPUT:
length
– integerwidth
– integerheight
– integer
OUTPUT:
set of tuplesEXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles) sage: T.admissible_horizontal_words(2,2,2) {(0, 0), (1, 1), (2, 2)}
The horizontal word 22 is impossible after looking at large enough boxes:
sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: T.admissible_horizontal_words(2,2,2) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 2)} sage: T.admissible_horizontal_words(2,3,3) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)} sage: T.admissible_horizontal_words(2,4,4) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)} sage: T.admissible_horizontal_words(2,5,5) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}
-
admissible_vertical_words
(length, width, height)¶ Return the vertical word of given length appearing in every position inside a rectangle of given width and height.
INPUT:
length
– integerwidth
– integerheight
– integer
OUTPUT:
set of tuplesEXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles) sage: T.admissible_vertical_words(2,2,2) {(0, 0), (1, 1), (2, 2)}
Every word of length 2 appear as a vertical word in every position of a \(5\times 5\) box:
sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: T.admissible_vertical_words(2,2,2) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)} sage: T.admissible_vertical_words(2,5,5) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}
-
clean_sources_and_sinks
()¶ TODO: do it for the dual?
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (3,2,4,8), (0,5,0,7)] sage: T = WangTileSet(tiles) sage: T.clean_sources_and_sinks().tiles() [(0, 0, 0, 0), (0, 5, 0, 7), (1, 1, 1, 1)] sage: T.dual().clean_sources_and_sinks().tiles() [(0, 0, 0, 0), (1, 1, 1, 1)]
-
create_macro_file
(filename='macro.tex', command_name='Tile', color=None, size=1, scale=1, font='\\normalsize', label_color='black', rotate=None, label=True, label_shift=0.2, id=True, id_color='', id_format='{}', draw_H=None, draw_V=None)¶ INPUT:
filename
– string (default:r'macro.tex'
)comand_name
– string (default:r'Tile'
)color
– dict (default: None)size
– number (default:1
)scale
– number (default:1
)font
– string (default:r'\normalsize'
)rotate
– list orNone
(default:None
) list of four angles in degrees like(0,0,0,0)
, the rotation angle to apply to each label of Wang tiles. IfNone
, it performs a 90 degres rotation for left and right labels taking more than one character.label
– boolean (default:True
), presence of the colorslabel_shift
– number (default:.2
) translation distance of the label from the edgelabel_color
– string (default:'black'
)id
– boolean (default:True
), presence of the tile idid_color
– string (default:''
)id_format
– string (default:r'{}'
) to be called withid_format.format(key)
draw_H
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {{}} -- ++ (1,0);'
. Dict values must be stringss
such thats.format((x,y))
works.draw_V
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {{}} -- ++ (0,1);'
. Dict values must be stringss
such thats.format((x,y))
works.
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: T.create_macro_file() # not tested creation of file macro.tex
sage: color = {0:'white',1:'red',2:'cyan',3:'green',4:'white'} sage: T.create_macro_file(color=color) # not tested creation of file macro.tex
-
create_tikz_pdf_files
(prefix='tile', color=None)¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: T.create_tikz_pdf_files() # not tested
This creates tile0.pdf, tile1.pdf, etc. in the repository.
-
desubstitute
(substitution, function=None)¶ Return the Wang tile set obtained from the desubstitution of the given Wang tile set.
INPUT:
substitution
– substitution 2dfn
– a function (default:None
) to apply to the new colors which are tuple of previous colors
OUTPUT:
dict, key -> tileEXAMPLES:
sage: from slabbe import Substitution2d, WangTileSet sage: A = [[0,1,2],[1,0,0]] sage: B = [[0,1,2]] sage: d = {4:A, 5:B} sage: s = Substitution2d(d) sage: tiles = [(0,3,1,4), (1,4,0,3), (5,6,7,8)] sage: W = WangTileSet(tiles) sage: W.desubstitute(s) {4: ((1, 0, 0), (6, 3), (1, 0, 7), (4, 3)), 5: ((0, 1, 5), (6,), (1, 0, 7), (4,))}
Providing a function which gets back to integers:
sage: fn = lambda colors:int(''.join(map(str, colors))) sage: W.desubstitute(s, fn) {4: (100, 63, 107, 43), 5: (15, 6, 107, 4)}
Providing a function which concatenate label as strings:
sage: fn = lambda colors:''.join(map(str, colors)) sage: W.desubstitute(s, fn) {4: ('100', '63', '107', '43'), 5: ('015', '6', '107', '4')}
-
dominoes_with_surrounding
(i=2, radius=1, solver=None, ncpus=1, verbose=False)¶ INPUT:
i
- integer (default:2
), 1 or 2radius
- integer or 2-tuple (default:1
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
- string or None (default:None
)ncpus
– integer (default:1
), maximal number of subprocesses to use at the same time, used only ifsolver
is'dancing_links'
.verbose
- bool
Note
The
solver='dancing_links'
is fast for this question.EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB', 'EBEB'] sage: T = WangTileSet(tiles) sage: sorted(T.dominoes_with_surrounding(i=1)) [(3, 3), (4, 4)] sage: sorted(T.dominoes_with_surrounding(i=2)) [(3, 3), (3, 4), (4, 3), (4, 4)] sage: sorted(T.dominoes_with_surrounding(i=2, radius=2)) [(3, 3), (3, 4), (4, 3), (4, 4)] sage: sorted(T.dominoes_with_surrounding(i=2, radius=(1,2))) [(3, 3), (3, 4), (4, 3), (4, 4)]
TESTS:
sage: tiles = [('02', '4', '02', '4'), ('32', '4', '02', '4')] sage: T = WangTileSet(tiles) sage: sorted(T.dominoes_with_surrounding(1)) [(0, 0)] sage: sorted(T.dominoes_with_surrounding(2)) [(0, 0)]
-
dual
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: dual = T.dual() sage: dual Wang tile set of cardinality 7 sage: dual.tiles() [(0, 0, 2, 0), (0, 1, 1, 0), (1, 2, 0, 0), (0, 0, 0, 1), (2, 1, 1, 1), (1, 1, 0, 2), (0, 2, 1, 2)]
-
find_markers
(i=2, radius=1, solver=None, ncpus=1, verbose=False)¶ Return a list of lists of marker tiles.
INPUT:
i
– integer (default:2
), 1 or 2.radius
- integer or 2-tuple (default:1
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
– string (default:None
)ncpus
– integer (default:1
)verbose
– boolean (default:False
)
Note
The
solver='dancing_links'
is fast for this question.OUTPUT:
list of listsEXAMPLES:
sage: from slabbe import WangTileSet sage: 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)] sage: tiles = [[str(a) for a in t] for t in tiles] sage: T = WangTileSet(tiles) sage: T.find_markers(i=1) [] sage: T.find_markers(i=2) [[0, 1]]
sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB'] sage: T = WangTileSet(tiles) sage: T.find_markers(i=1) [[0], [1], [2]] sage: T.find_markers(i=2) [[0], [1], [2]]
-
find_markers_with_slope
(i=2, slope=None, radius=1, solver=None, ncpus=1, verbose=False)¶ Return a list of lists of marker tiles.
INPUT:
i
– integer (default:2
), 1 or 2.slope
– -1, 0, 1 or Infinity (default:None
)radius
- integer or 2-tuple (default:1
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
– string (default:None
)ncpus
– integer (default:1
)verbose
– boolean (default:False
)
OUTPUT:
list of listsEXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB'] sage: T = WangTileSet(tiles) sage: T.find_markers_with_slope(i=1, slope=1) # known bug [{0, 3}, {1}, {2}] sage: T.find_markers_with_slope(i=2, slope=1) # known bug [{0, 2, 3}, {1}]
-
find_substitution
(M=None, i=2, side='right', radius=1, solver=None, ncpus=1, function=<slot wrapper '__add__' of 'str' objects>, initial='', verbose=False)¶ Return the derived Wang tile set obtained from desubstitution using a given set of marker tiles.
INPUT:
M
– markers, set of tile indicesi
– integer 1 or 2side
–'right'
or'left'
radius
- integer or 2-tuple (default:1
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
– string (default:None
)ncpus
– integer (default:1
)function
– function (default:str.__add__
), monoid- operation
initial
– object (default:''
), monoid neutralverbose
– boolean
OUTPUT:
a 3-tuple (Wang tile set, substitution2d, set of markers)Note
The
solver='dancing_links'
is fast for this question.EXAMPLES:
sage: from slabbe import WangTileSet sage: 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)] sage: tiles = [[str(a) for a in t] for t in tiles] sage: T = WangTileSet(tiles) sage: T.find_markers(i=2) [[0, 1]] sage: T.find_substitution(M=[0,1], i=2) (Wang tile set of cardinality 12, Substitution 2d: {0: [[2]], 1: [[3]], 2: [[4]], 3: [[5]], 4: [[7]], 5: [[8]], 6: [[9]], 7: [[10]], 8: [[4, 0]], 9: [[5, 0]], 10: [[6, 1]], 11: [[7, 0]]})
-
fusion
(other, direction, function=<slot wrapper '__add__' of 'str' objects>, initial='', clean_graph=True)¶ Return the fusion of wang tile sets in the given direction.
TODO: check if and when to do the clean
INPUT:
other
– WangTileSetdirection
– integer (1 or 2)function
– function (default:str.__add__
), monoid operationinitial
– object (default:''
), monoid neutralclean_graph
– boolean (default:False
), clean the graph by recursively removing sources and sinks transitions (or tiles).
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB'] sage: tiles = map(tuple, tiles) sage: T = WangTileSet(tiles) sage: T1T = T.fusion(T, 1) sage: T1T.tiles() [('A', 'BB', 'A', 'BB')] sage: T2T = T.fusion(T, 2) sage: T2T.tiles() [('AA', 'B', 'AA', 'B')]
To keep integers, one way is to wrap them into a tuple and do tuple operations:
sage: tiles = [(0,1,0,1)] sage: tiles = [tuple((a,) for a in tile) for tile in tiles] sage: T = WangTileSet(tiles) sage: T2T = T.fusion(T, 2, function=tuple.__add__, initial=tuple()) sage: T2T2T = T2T.fusion(T, 2, function=tuple.__add__, initial=tuple()) sage: T2T2T.tiles() [((0, 0, 0), (1,), (0, 0, 0), (1,))]
TESTS:
sage: tiles = [('02', '2', '02', '2'), ('32', '2', '02', '2')] sage: T = WangTileSet(tiles) sage: T.fusion(T, 1) Wang tile set of cardinality 2 sage: T.fusion(T, 2) Wang tile set of cardinality 1
-
horizontal_alphabet
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,1,2,3), (4,5,6,7), (8,9,10,11)] sage: T = WangTileSet(tiles) sage: T.horizontal_alphabet() {1, 3, 5, 7, 9, 11}
-
is_equivalent
(other, certificate=False, verbose=False)¶ INPUT:
other
– wang tile setcertificate
– boolean (default:False
)verbose
– boolean (default:False
)
Note
This code depends on the following bug to be fixed: https://trac.sagemath.org/ticket/24964
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(1,6,1,8), (2,6,1,7), (3,7,1,6), (1,6,2,6), ....: (2,8,2,7), (2,7,3,6), (3,6,3,7)] sage: T = WangTileSet(tiles) sage: d = {1:'a', 2:'b', 3:'c', 6:'x', 7:'y', 8:'z'} sage: L = [tuple(d[a] for a in t) for t in tiles] sage: U = WangTileSet(L) sage: T.is_equivalent(U) True sage: T.is_equivalent(U,certificate=True) (True, {1: 'a', 2: 'b', 3: 'c'}, {6: 'x', 7: 'y', 8: 'z'}, Substitution 2d: {0: [[0]], 1: [[1]], 2: [[2]], 3: [[3]], 4: [[4]], 5: [[5]], 6: [[6]]})
Not equivalent example:
sage: _ = L.pop() sage: U = WangTileSet(L) sage: T.is_equivalent(U) False sage: T.is_equivalent(U,certificate=True) (False, None, None, None)
When graphs admits non trivial automorphisms:
sage: T = WangTileSet([(1,3,0,2), (0,2,1,3)]) sage: U = WangTileSet([(7,'c',6,'z'), (6,'z',7,'c')]) sage: V = WangTileSet([(7,9,6,8), (6,8,7,9)]) sage: W = WangTileSet([(7,8,6,9), (6,9,7,8)]) sage: T.is_equivalent(T, certificate=True) (True, {0: 0, 1: 1}, {2: 2, 3: 3}, Substitution 2d: {0: [[0]], 1: [[1]]}) sage: T.is_equivalent(U, certificate=True) (True, {0: 6, 1: 7}, {2: 'z', 3: 'c'}, Substitution 2d: {0: [[0]], 1: [[1]]}) sage: T.is_equivalent(V, certificate=True) (True, {0: 6, 1: 7}, {2: 8, 3: 9}, Substitution 2d: {0: [[0]], 1: [[1]]}) sage: T.is_equivalent(W, certificate=True) (True, {0: 6, 1: 7}, {2: 9, 3: 8}, Substitution 2d: {0: [[0]], 1: [[1]]}) sage: T.is_equivalent(W, certificate=True, verbose=True) True V_perm= {0: 6, 1: 7} True H_perm= {2: 8, 3: 9} Found automorphisms p=() and q=(2,3) (True, {0: 6, 1: 7}, {2: 9, 3: 8}, Substitution 2d: {0: [[0]], 1: [[1]]})
-
is_forbidden_product
(A, B, i=2, radius=1, solver=None, ncpus=None)¶ Return whether A odot^i B is forbidden using a given radius around the product and a given solver.
INPUT:
A
– list of tile indicesB
– list of tile indicesi
– integer, 1 or 2radius
– integer (default:1
)solver
– string (default:None
)ncpus
– integer (default:None
)
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB'] sage: T = WangTileSet(tiles) sage: T.is_forbidden_product([3],[3]) False sage: T.is_forbidden_product([0],[0]) True sage: T.is_forbidden_product([0,1],[0,1]) True sage: T.is_forbidden_product([0,1],[0,1,2]) True sage: T.is_forbidden_product([0,1],[0,1,2,3]) True sage: T.is_forbidden_product([0,1,3],[0,1,2,3]) False
-
is_pattern_surrounded
(pattern, radius=1, solver=None, ncpus=None)¶ Return whether the rectangular pattern allows a surrounding of given radius.
INPUT:
pattern
– list of lists of tile indicesradius
- integer or 2-tuple (default:1
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
– string (default:None
)ncpus
– integer (default:None
)
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles) sage: T.is_pattern_surrounded([[0,0]], solver='dancing_links') True sage: T.is_pattern_surrounded([[0,1]], solver='dancing_links') False sage: T.is_pattern_surrounded([[0],[1]], solver='dancing_links') False sage: T.is_pattern_surrounded([[0],[0]], solver='dancing_links') True
-
not_forbidden_dominoes
()¶ Deprecated: Use
dominoes_with_surrounding()
instead. See trac ticket #123456 for details.
-
not_forbidden_tilings
()¶ Deprecated: Use
tilings_with_surrounding()
instead. See trac ticket #123456 for details.
-
polyhedron_of_densities
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: P = T.polyhedron_of_densities() sage: P A 2-dimensional polyhedron in QQ^7 defined as the convex hull of 3 vertices sage: P.vertices() (A vertex at (0, 2/7, 1/7, 3/7, 0, 1/7, 0), A vertex at (0, 0, 1/5, 1/5, 0, 1/5, 2/5), A vertex at (2/7, 0, 1/7, 1/7, 2/7, 1/7, 0)) sage: (0, 0, 1/5, 1/5, 0, 1/5, 2/5) in P True
Jeandel-Rao tiles:
sage: 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)] sage: T = WangTileSet(tiles) sage: P = T.polyhedron_of_densities() sage: P A 4-dimensional polyhedron in QQ^11 defined as the convex hull of 10 vertices sage: P.vertices() (A vertex at (0, 1/5, 1/5, 0, 1/5, 0, 1/5, 0, 0, 0, 1/5), A vertex at (0, 1/5, 0, 1/5, 1/5, 0, 1/5, 0, 0, 0, 1/5), A vertex at (0, 1/5, 1/5, 0, 0, 0, 1/5, 1/5, 1/5, 0, 0), A vertex at (0, 1/5, 0, 1/5, 0, 0, 1/5, 1/5, 1/5, 0, 0), A vertex at (0, 1/4, 0, 0, 0, 1/4, 1/4, 1/4, 0, 0, 0), A vertex at (1/4, 0, 0, 0, 0, 1/4, 0, 1/4, 0, 1/4, 0), A vertex at (1/5, 0, 1/5, 0, 1/5, 0, 0, 0, 0, 1/5, 1/5), A vertex at (1/5, 0, 1/5, 0, 0, 0, 0, 1/5, 1/5, 1/5, 0), A vertex at (1/5, 0, 0, 1/5, 1/5, 0, 0, 0, 0, 1/5, 1/5), A vertex at (1/5, 0, 0, 1/5, 0, 0, 0, 1/5, 1/5, 1/5, 0))
-
shear
(radius=0, solver=None, ncpus=1, function=<slot wrapper '__add__' of 'str' objects>, verbose=False)¶ Shears the Wang Tile set by the
matrix(2,(1,-1,0,1))
.It is currently not implemented for other matrices.
INPUT:
radius
- integer or 2-tuple (default:0
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
– string (default:None
)ncpus
– integer (default:1
)function
– function (default:str.__add__
), monoid operationverbose
– boolean (default:False
)
OUTPUT:
- (WangTileSet, Substitution2d)
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [('aa','bb','cc','bb'), ('cc','dd','aa','dd')] sage: T = WangTileSet(tiles) sage: U,s = T.shear() sage: s Substitution 2d: {0: [[0]], 1: [[1]]} sage: U.tiles() [('aadd', 'dd', 'ccbb', 'bb'), ('ccbb', 'bb', 'aadd', 'dd')] sage: T.shear()[0].shear()[0].tiles() [('aaddbb', 'bb', 'ccbbdd', 'bb'), ('ccbbdd', 'dd', 'aaddbb', 'dd')]
sage: tiles = [('aa','bb','cc','bb'), ('aa','dd','cc','bb'), ('cc','dd','aa','dd')] sage: T = WangTileSet(tiles) sage: U,s = T.shear() sage: s Substitution 2d: {0: [[0]], 1: [[1]], 2: [[2]], 3: [[2]]} sage: sorted(U.tiles()) [('aadd', 'dd', 'ccbb', 'bb'), ('aadd', 'dd', 'ccdd', 'bb'), ('ccbb', 'bb', 'aadd', 'dd'), ('ccdd', 'dd', 'aadd', 'dd')] sage: U,s = T.shear(radius=1) sage: s Substitution 2d: {0: [[0]], 1: [[2]]} sage: U.tiles() [('aadd', 'dd', 'ccbb', 'bb'), ('ccbb', 'bb', 'aadd', 'dd')]
-
solver
(width, height, preassigned_color=None, preassigned_tiles=None, color=None)¶ Return the Wang tile solver of this Wang tile set inside a rectangle of given width and height.
INPUT:
width
– integerheight
– integerpreassigned_color
– None or list of 4 dict or the form[{}, {}, {}, {}]
right, top, left, bottom colors preassigned to some positions (on the border or inside)preassigned_tiles
– None or dict of tiles preassigned to some positionscolor
– None or dict
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: T = WangTileSet(tiles) sage: W = T.solver(3,3) sage: W.solve() A wang tiling of a 3 x 3 rectangle
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles) sage: W = T.solver(3,3, preassigned_tiles={(1,1):0}) sage: W.solve().table() [[0, 0, 0], [0, 0, 0], [0, 0, 0]] sage: W = T.solver(3,3, preassigned_tiles={(1,1):1}) sage: W.solve().table() [[1, 1, 1], [1, 1, 1], [1, 1, 1]] sage: W = T.solver(3,3, preassigned_tiles={(1,1):2}) sage: W.solve().table() [[2, 2, 2], [2, 2, 2], [2, 2, 2]]
When incompatible preassigned tiles:
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles) sage: W = T.solver(3,3, preassigned_tiles={(0,0):0,(0,1):1}) sage: W.has_solution() False
TESTS:
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: T = WangTileSet(tiles) sage: W = T.solver(3,3, preassigned_tiles={(1,1):3}) sage: W.solve().table() Traceback (most recent call last): ... MIPSolverException: ...
-
substitution_tikz
(substitution, function=None, color=None, size=1, scale=1, font='\\normalsize', rotate=None, label_shift=0.2, ncolumns=4, tabular='tabular', align='l')¶ Return the tikz code showing what the substitution A->B* does on Wang tiles.
Note: we assume that the tiles in self are the elements of B.
INPUT:
substitution
– substitution 2dfn
– a function (default:None
) to apply to the new colors which are tuple of previous colorscolor
– dict (default:None
) from tile values -> tikz colorssize
– number (default:1
), size of the tilescale
– number (default:1
), scale of tikzpicturefont
– string (default:r'\normalsize'
rotate
– list orNone
(default:None
) list of four angles in degrees like(0,0,0,0)
, the rotation angle to apply to each label of Wang tiles. IfNone
, it performs a 90 degres rotation for left and right labels taking more than one character.label_shift
– number (default:.2
) translation distance of the label from the edgencolumns
– integer (default:4
)tabular
– string (default:'tabular'
) or'longtable'
align
– character (default:'l'
), latex alignment symbol'l'
,'r'
or'c'
.
OUTPUT:
dict, key -> tile
-
system_of_density_equations
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: M = T.system_of_density_equations() sage: M [ 1 1 1 1 1 1 1 1] [ 1 1 -1 0 0 -1 1 0] [ 0 1 1 -1 0 0 0 0] [ 0 0 -1 0 0 1 0 0] [ 0 -1 1 0 -1 1 -1 0] [ 0 -1 0 1 0 -1 0 0] [-1 0 0 0 1 0 0 0] sage: M.rank() 5
-
table
()¶ Return a table representation of the tile set.
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: T.table() Id Right Top Left Bottom +----+-------+-----+------+--------+ 0 0 0 0 2 1 1 0 0 1 2 2 1 0 0 3 0 0 1 0 4 1 2 1 1 5 1 1 2 0 6 2 0 2 1
-
tikz
(ncolumns=10, color=None, size=1, space=0.1, scale=1, font='\\normalsize', rotate=None, label=True, id=True, id_format='{}', id_color='', label_shift=0.2, label_color='black', right_edges=True, top_edges=True, left_edges=True, bottom_edges=True, draw_H=None, draw_V=None)¶ INPUT:
ncolumns
– integer (default:10
)color
– dict (default: None)size
– number (default:1
)space
– number (default:.1
)scale
– number (default:1
)font
– string (default:r'\normalsize'
)rotate
– list orNone
(default:None
) list of four angles in degrees like(0,0,0,0)
, the rotation angle to apply to each label of Wang tiles. IfNone
, it performs a 90 degres rotation for left and right labels taking more than one character.label
– boolean (default:True
), presence of the colorsid
– boolean (default:True
), presence of the tile idid_color
– string (default:''
)id_format
– string (default:r'{}'
) to be called withid_format.format(key)
label_shift
– number (default:.2
) translation distance of the label from the edgelabel_color
– string (default:'black'
)right_edges
– bool (default:True
)top_edges
– bool (default:True
)left_edges
– bool (default:True
)bottom_edges
– bool (default:True
)draw_H
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {{}} -- ++ (1,0);'
. Dict values must be stringss
such thats.format((x,y))
works.draw_V
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {{}} -- ++ (0,1);'
. Dict values must be stringss
such thats.format((x,y))
works.
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: color = {0:'white',1:'red',2:'cyan',3:'green',4:'white'} sage: _ = T.tikz(color=color).pdf(view=False)
-
tiles
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: T = WangTileSet(tiles) sage: T.tiles() [(0, 0, 0, 0), (1, 1, 1, 1), (2, 2, 2, 2)]
-
tiles_allowing_surrounding
(radius, solver=None, ncpus=None, verbose=False)¶ Return the subset of tiles allowing a surrounding of given radius.
INPUT:
radius
- integersolver
- string or Nonencpus
- integerverbose
- boolean
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: T = WangTileSet(tiles) sage: U = T.tiles_allowing_surrounding(1) sage: U Wang tile set of cardinality 3 sage: U.tiles() [(0, 0, 0, 0), (1, 1, 1, 1), (2, 2, 2, 2)]
sage: T.tiles_allowing_surrounding(1, verbose=True) Solution found for tile 0: [[0, 0, 3], [0, 0, 0], [0, 0, 0]] Solution found for tile 1: [[1, 1, 1], [1, 1, 1], [1, 1, 1]] Solution found for tile 2: [[2, 2, 2], [2, 2, 2], [2, 2, 2]] Wang tile set of cardinality 3
-
tiling_with_surrounding
()¶ Deprecated: Use
tilings_with_surrounding()
instead. See trac ticket #123456 for details.
-
tilings_with_surrounding
(width, height, radius=1, solver=None, verbose=False)¶ Return the set of valid tiling of a rectangle of given width and height allowing a surrounding of itself of given radius.
INPUT:
width
- integerheight
- integerradius
- integersolver
- string or Noneverbose
- boolean
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: tiles = [[str(a) for a in tile] for tile in tiles] sage: T = WangTileSet(tiles) sage: S = T.tilings_with_surrounding(2,2) sage: S [A wang tiling of a 2 x 2 rectangle, A wang tiling of a 2 x 2 rectangle, A wang tiling of a 2 x 2 rectangle] sage: [a.table() for a in S] [[[0, 0], [0, 0]], [[1, 1], [1, 1]], [[2, 2], [2, 2]]]
sage: S = T.tilings_with_surrounding(3,3) sage: S [A wang tiling of a 3 x 3 rectangle, A wang tiling of a 3 x 3 rectangle, A wang tiling of a 3 x 3 rectangle] sage: [a.table() for a in S] [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[1, 1, 1], [1, 1, 1], [1, 1, 1]], [[2, 2, 2], [2, 2, 2], [2, 2, 2]]]
TESTS:
sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB', 'EBEB'] sage: T = WangTileSet(tiles) sage: solutions = T.tilings_with_surrounding(1,2) sage: [t.table() for t in solutions] [[[3, 3]], [[3, 4]], [[4, 3]], [[4, 4]]]
sage: tiles = [('02', '4', '02', '4'), ('32', '4', '02', '4')] sage: T = WangTileSet(tiles) sage: [t.table() for t in T.tilings_with_surrounding(1,2)] [[[0, 0]]] sage: [t.table() for t in T.tilings_with_surrounding(2,1)] [[[0], [0]]]
-
tilings_with_surrounding_new_method
(width, height, radius=1, solver=None, ncpus=1, verbose=False)¶ Return the set of valid tiling of a rectangle of given width and height allowing a surrounding of itself of given radius.
INPUT:
width
- integerheight
- integerradius
- integer or 2-tuple (default:1
), if 2-tuple is given, then it is interpreted as(xradius, yradius)
solver
- string or None (default:None
)ncpus
– integer (default:1
), maximal number of subprocesses to use at the same time, used only ifsolver
is'dancing_links'
.verbose
- bool
Note
The
solver='dancing_links'
is fast for this question (I think)EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: tiles = [[str(a) for a in tile] for tile in tiles] sage: T = WangTileSet(tiles) sage: S = T.tilings_with_surrounding_new_method(2,2) sage: S {((0, 0), (0, 0)), ((1, 1), (1, 1)), ((2, 2), (2, 2))}
sage: S = T.tilings_with_surrounding_new_method(3,3) sage: S {((0, 0, 0), (0, 0, 0), (0, 0, 0)), ((1, 1, 1), (1, 1, 1), (1, 1, 1)), ((2, 2, 2), (2, 2, 2), (2, 2, 2))}
TESTS:
sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB', 'EBEB'] sage: T = WangTileSet(tiles) sage: solutions = T.tilings_with_surrounding_new_method(1,2) sage: solutions {((3, 3),), ((3, 4),), ((4, 3),), ((4, 4),)}
sage: tiles = [('02', '4', '02', '4'), ('32', '4', '02', '4')] sage: T = WangTileSet(tiles) sage: T.tilings_with_surrounding_new_method(1,2) {((0, 0),)} sage: T.tilings_with_surrounding_new_method(2,1) {((0,), (0,))}
-
to_transducer
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,0,0,2), (1,0,0,1), (2,1,0,0), (0,0,1,0), ....: (1,2,1,1), (1,1,2,0), (2,0,2,1)] sage: T = WangTileSet(tiles) sage: T.to_transducer() Transducer with 3 states
-
to_transducer_graph
(label_function=<class 'tuple'>, merge_multiedges=True)¶ Return the graph of the transducer.
Labels are cleaned. Label of multiedges are merged with commas.
INPUT:
label_function
– function (default:tuple
), a function to apply to each list of labels when merging multiedges into onemerge_multiedges
– boolean (default:True
)
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = ['ABCD', 'EFGH', 'AXCY'] sage: tiles = map(tuple, tiles) sage: T = WangTileSet(tiles) sage: G = T.to_transducer_graph() sage: G Digraph on 4 vertices
The edge labels are clean:
sage: G.edges() [('C', 'A', ('D|B', 'Y|X')), ('G', 'E', ('H|F',))]
Using
label_function
:sage: fn = lambda L: ','.join(map(str, L)) sage: G = T.to_transducer_graph(label_function=fn) sage: G.edges() [('C', 'A', 'D|B,Y|X'), ('G', 'E', 'H|F')]
Using
label_function
with latex expressions:sage: fn = lambda L: LatexExpr(','.join(map(str, L))) sage: G = T.to_transducer_graph(label_function=fn) sage: G.edges() [('C', 'A', D|B,Y|X), ('G', 'E', H|F)]
This is to compared to:
sage: T.to_transducer().graph().edges() [('C', 'A', "'D'|'B'"), ('C', 'A', "'Y'|'X'"), ('G', 'E', "'H'|'F'")]
It works for integers entries:
sage: tiles = [(0,1,2,3), (0,5,2,3)] sage: T = WangTileSet(tiles) sage: G = T.to_transducer_graph() sage: G Digraph on 2 vertices sage: G.edges() [(2, 0, ('3|1', '3|5'))]
-
unsynchronized_graph
(i=1, size=2, verbose=False)¶ INPUT:
i
– integer, 1 or 2size
– integer, 2 or moreverbose
– boolean (default:False
)
OUTPUT:
- graph of vertices (delays, blocks)
Signification of the nodes (d,b):
+-----------+ | | | b[1] | | | +----+-----+-----+ | | | | b[0] | d[1] | | +----------+ | d[0]
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [('aa','bb','cc','bb'), ('cc','dd','aa','dd')] sage: T = WangTileSet(tiles) sage: G = T.unsynchronized_graph() sage: sorted(G.vertices()) # known bug [(d=(0, 0), b=(0, 0)), (d=(0, 0), b=(1, 1)), (d=(2, 0), b=(0, 1)), (d=(2, 0), b=(1, 0))] sage: G.edges() # known bug [((d=(0, 0), b=(1, 1)), (d=(2, 0), b=(0, 1)), (1, 0)), ((d=(0, 0), b=(0, 0)), (d=(2, 0), b=(1, 0)), (0, 1)), ((d=(2, 0), b=(1, 0)), (d=(0, 0), b=(1, 1)), (0, 1)), ((d=(2, 0), b=(0, 1)), (d=(0, 0), b=(0, 0)), (1, 0))] sage: [node.lengths_x() for node in G] [[2, 2], [2, 2], [2, 2], [2, 2]] sage: [node.is_synchronized() for node in G] [True, True, True, True] sage: from slabbe import TikzPicture sage: _ = TikzPicture.from_graph(G).pdf(view=False)
-
unsynchronized_graph_size2
(i=1)¶ INPUT:
i
– integer, 1 or 2
Signification of the nodes (u,v,w,d):
d = 0 |w| = d > 0 -|w| = d < 0 | | | v| v| v| | w | | + +-----+ +-----+ | | w | u| u| u| | | |
EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [('aa','bb','cc','bb'), ('cc','dd','aa','dd')] sage: T = WangTileSet(tiles) sage: G = T.unsynchronized_graph_size2() sage: sorted(G.vertices()) [('aa', 'aa', '', 0), ('cc', 'cc', '', 0)]
-
vertical_alphabet
()¶ EXAMPLES:
sage: from slabbe import WangTileSet sage: tiles = [(0,1,2,3), (4,5,6,7), (8,9,10,11)] sage: T = WangTileSet(tiles) sage: T.vertical_alphabet() {0, 2, 4, 6, 8, 10}
-
class
slabbe.wang_tiles.
WangTileSolver
(tiles, width, height, preassigned_color=None, preassigned_tiles=None, color=None)¶ Bases:
object
Wang tile solver inside a rectangle of given width and height.
INPUT:
tiles
– list of tiles, a tile is a 4-tuple (right color, top color, left color, bottom color)width
– integerheight
– integerpreassigned_color
– None or list of 4 dict or the form[{}, {}, {}, {}]
right, top, left, bottom colors preassigned to some positions (on the border or inside)preassigned_tiles
– None or dict of tiles preassigned to some positionscolor
– None or dict
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles, 3, 3) sage: tiling = W.solve() sage: tiling._table [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
With color 2 preassigned to the right part of tile at position (1,1):
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: right = {(1,1):2} sage: W = WangTileSolver(tiles,3,3,preassigned_color=[right,{},{},{}]) sage: tiling = W.solve() sage: tiling._table [[2, 2, 2], [2, 2, 2], [2, 2, 2]]
With tile 2 preassigned at position (0,1):
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: preassigned = {(0,1):1} sage: W = WangTileSolver(tiles,3,3,preassigned_tiles=preassigned) sage: tiling = W.solve() sage: tiling._table [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
When constraints are inconsistent:
sage: right = {(1,1):1, (2,2):0} sage: W = WangTileSolver(tiles,3,3,preassigned_color=[right,{},{},{}]) sage: W.solve(solver='GLPK') Traceback (most recent call last): ... MIPSolverException: GLPK: Problem has no feasible solution
TESTS:
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: preassigned = {(0,1):1} sage: W = WangTileSolver(tiles,3,3,preassigned_tiles=preassigned) sage: tiling = W.solve() sage: tiling._table [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
-
all_solutions
(ncpus=8)¶ Return the list of all solutions.
Note
This uses the reduction to dancing links.
INPUT:
ncpus
– integer (default:8
), maximal number of subprocesses to use at the same time
OUTPUT:
list of wang tilingsEXAMPLES:
sage: from slabbe import WangTileSolver sage: 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)] sage: W = WangTileSolver(tiles,3,4) sage: W.number_of_solutions() 908 sage: L = W.all_solutions() sage: len(L) 908
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles,2,2) sage: W.all_solutions() [A wang tiling of a 2 x 2 rectangle, A wang tiling of a 2 x 2 rectangle, A wang tiling of a 2 x 2 rectangle]
With preassigned colors and tiles:
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: t = {(0,1):0} sage: c = [{},{},{(1,1):0},{}] sage: W = WangTileSolver(tiles,3,3,preassigned_tiles=t,preassigned_color=c) sage: S = W.all_solutions() sage: sorted([s._table for s in S]) [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 3], [0, 0, 0], [0, 0, 0]]]
With preassigned colors and tiles:
sage: right = {(0, 1): 'A', (0, 0): 'A'} sage: top = {(0, 1): 'B'} sage: left = {(0, 1): 'A', (0, 0): 'A'} sage: bottom = {(0, 0): 'B'} sage: preassigned_color=[right,top,left,bottom] sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB', 'EBEB'] sage: W = WangTileSolver(tiles, 1, 2, preassigned_color=preassigned_color) sage: [t.table() for t in W.all_solutions()] [[[3, 3]]]
-
all_solutions_tikz
(ncpus=8)¶ INPUT:
ncpus
– integer (default:8
), maximal number of subprocesses to use at the same time
EXAMPLES:
sage: from slabbe import WangTileSolver sage: 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)] sage: W = WangTileSolver(tiles,2,2) sage: t = W.all_solutions_tikz() sage: view(t) # long # not tested
-
dlx_solver
()¶ Return the sage DLX solver of that Wang tiling problem.
OUTPUT:
DLX SolverEXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: dlx = W.dlx_solver() sage: dlx Dancing links solver for 63 columns and 24 rows sage: dlx.number_of_solutions() 2
TESTS:
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles,2,2) sage: dlx = W.dlx_solver() sage: list(dlx.solutions_iterator()) [[1, 7, 4, 10], [6, 0, 9, 3], [8, 2, 5, 11]]
-
has_solution
(solver=None, solver_parameters=None, ncpus=1)¶ Return whether there is a solution.
INPUT:
solver
– string or None (default:None
),'dancing_links'
or the name of a MILP solver in Sage like'GLPK'
,'Coin'
or'Gurobi'
.solver_parameters
– dict (default:{}
), parameters given to the MILP solver using methodsolver_parameter
. For a list of available parameters for example for the Gurobi backend, see dictionaryparameters_type
in the filesage/numerical/backends/gurobi_backend.pyx
ncpus
– integer (default:1
), maximal number of subprocesses to use at the same time, used only ifsolver
is'dancing_links'
.
OUTPUT:
a wang tiling objectEXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: W.has_solution() True
Allowing more threads while using Gurobi:
sage: W = WangTileSolver(tiles,3,4) sage: kwds = dict(Threads=4) sage: tiling = W.has_solution(solver='Gurobi', kwds) # optional Gurobi True
Using dancing links:
sage: W = WangTileSolver(tiles,3,4) sage: W.has_solution(solver='dancing_links', ncpus=8) True
Using cryptominisat:
sage: W = WangTileSolver(tiles,3,4) sage: W.has_solution(solver='cryptominisat') # optional cryptominisat True
-
horizontal_alphabet
()¶
-
meet_of_all_solutions
(ncpus=8)¶ Return the tiling of the rectangle with tiles that are imposed at each position (this is the meet of the partially ordered set of all partial solutions inside the rectangle).
INPUT:
ncpus
– integer (default:8
), maximal number of subprocesses to use at the same time
OUTPUT:
A Wang tiling (withNone
at positions where more than one tile can occur)EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: t = {(0,1):0} sage: W = WangTileSolver(tiles,3,3,preassigned_tiles=t) sage: tiling = W.meet_of_all_solutions() sage: tiling A wang tiling of a 3 x 3 rectangle sage: tiling.table() [[0, 0, None], [0, 0, 0], [0, 0, 0]]
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: W = WangTileSolver(tiles,3,3) sage: tiling = W.meet_of_all_solutions() sage: tiling.table() [[None, None, None], [None, None, None], [None, None, None]]
-
milp
(solver=None)¶ Return the Mixed integer linear program.
INPUT:
solver
– string or None (default:None
), other possible values are'Coin'
or'Gurobi'
OUTPUT:
a tuple (p,x) where p is the MILP and x is the variable
Note
In some cases, calling this method takes much more time (few minutes) than calling the method
solve
which takes few seconds.EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles,3,4) sage: p,x = W.milp(solver='GLPK') sage: p Boolean Program (maximization, 36 variables, 29 constraints) sage: x MIPVariable of dimension 1
Then you can solve it and get the solutions:
sage: p.solve() 1.0 sage: soln = p.get_values(x) sage: support = [key for key in soln if soln[key]] sage: sorted(support) [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 0), (0, 2, 1), (0, 2, 2), (0, 2, 3)]
Other solver can be used:
sage: p,x = W.milp(solver='Gurobi') # optional gurobi
TESTS:
Colors do not have to be integers:
sage: tiles = [('a','a','a','a'), ('b','b','b','b')] sage: W = WangTileSolver(tiles,3,4) sage: p,x = W.milp() sage: tiling = W.solve()
-
number_of_solutions
(ncpus=8)¶ Return the number of solutions
INPUT:
ncpus
– integer (default:8
), maximal number of subprocesses to use at the same time
EXAMPLES:
sage: from slabbe import WangTileSolver sage: 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)] sage: W = WangTileSolver(tiles,3,4) sage: W.number_of_solutions() 908
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles,2,2) sage: W.number_of_solutions() 3
-
rows_and_information
(verbose=False)¶ Return the rows to give to the dancing links solver.
INPUT:
verbose
– bool (default:False
)
OUTPUT:
Two lists:
- the rows
- row information (j,k,i) meaning tile i is at position (j,k)
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles, 4, 1) sage: rows,row_info = W.rows_and_information() sage: rows [[1, 2, 9], [0, 2, 9], [2, 9], [0, 4, 5, 10], [1, 3, 5, 10], [0, 1, 5, 10], [3, 7, 8, 11], [4, 6, 8, 11], [3, 4, 8, 11], [6, 12], [7, 12], [6, 7, 12]] sage: row_info [(0, 0, 0), (0, 0, 1), (0, 0, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (3, 0, 0), (3, 0, 1), (3, 0, 2)] sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: dlx = dlx_solver(rows) sage: dlx Dancing links solver for 13 columns and 12 rows sage: dlx.search() 1 sage: dlx.get_solution() [1, 4, 7, 10] sage: row_info[1] (0, 0, 1) sage: row_info[4] (1, 0, 1) sage: row_info[7] (2, 0, 1) sage: row_info[10] (3, 0, 1)
… which means tile 1 is at position (0,0), (1,0), (2,0) and (3,0)
TESTS:
sage: tiles = [(0,0,0,0), (1,1,1,1)] sage: W = WangTileSolver(tiles, 4, 1) sage: W.rows_and_information(verbose=True) Vertical colors (coded using 3 bits): color 0 represented by bits [0] when on left color 0 represented by bits [1, 2] when on right color 1 represented by bits [1] when on left color 1 represented by bits [0, 2] when on right Horizontal colors (coded using 3 bits): color 0 represented by bits [0] when on bottom color 0 represented by bits [1, 2] when on top color 1 represented by bits [1] when on bottom color 1 represented by bits [0, 2] when on top ([[1, 2, 9], [0, 2, 9], [0, 4, 5, 10], [1, 3, 5, 10], [3, 7, 8, 11], [4, 6, 8, 11], [6, 12], [7, 12]], [(0, 0, 0), (0, 0, 1), (1, 0, 0), (1, 0, 1), (2, 0, 0), (2, 0, 1), (3, 0, 0), (3, 0, 1)])
sage: tiles = [(0,0,0,0)] sage: W = WangTileSolver(tiles, 4, 1) sage: W.rows_and_information(verbose=True) Vertical colors (coded using 2 bits): color 0 represented by bits [0] when on left color 0 represented by bits [1] when on right Horizontal colors (coded using 2 bits): color 0 represented by bits [0] when on bottom color 0 represented by bits [1] when on top ([[1, 6], [0, 3, 7], [2, 5, 8], [4, 9]], [(0, 0, 0), (1, 0, 0), (2, 0, 0), (3, 0, 0)])
With preassigned colors:
sage: right = {(0, 1): 'A', (0, 0): 'A'} sage: top = {(0, 1): 'B'} sage: left = {(0, 1): 'A', (0, 0): 'A'} sage: bottom = {(0, 0): 'B'} sage: preassigned_color=[right,top,left,bottom] sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB', 'EBEB'] sage: W = WangTileSolver(tiles, 1, 2, preassigned_color=preassigned_color) sage: W.rows_and_information() ([[4], [4], [4], [1, 2, 3, 4], [4], [5], [5], [5], [0, 5], [5]], [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4)])
-
sat_solver
(solver=None)¶ Return the SAT solver.
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: s = W.sat_solver() sage: s # random an ILP-based SAT Solver CryptoMiniSat solver: 24 variables, 58 clauses. sage: L = s() sage: list(L) [None, ...]
-
sat_variable_to_tile_position_bijection
()¶ Return the dictionary giving the correspondence between variables and tiles indices i at position (j,k)
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: d1,d2 = W.sat_variable_to_tile_position_bijection() sage: d1 {1: (0, 0, 0), 2: (0, 0, 1), 3: (0, 0, 2), 4: (0, 0, 3), 5: (0, 1, 0), 6: (0, 1, 1), 7: (0, 1, 2), 8: (0, 1, 3), 9: (0, 2, 0), 10: (0, 2, 1), 11: (0, 2, 2), 12: (0, 2, 3), 13: (1, 0, 0), 14: (1, 0, 1), 15: (1, 0, 2), 16: (1, 0, 3), 17: (1, 1, 0), 18: (1, 1, 1), 19: (1, 1, 2), 20: (1, 1, 3), 21: (1, 2, 0), 22: (1, 2, 1), 23: (1, 2, 2), 24: (1, 2, 3)}
-
solutions_iterator
()¶ Iterator over all solutions
Note
This uses the reduction to dancing links.
OUTPUT:
iterator of wang tilingsEXAMPLES:
sage: from slabbe import WangTileSolver sage: 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)] sage: W = WangTileSolver(tiles,3,4) sage: it = W.solutions_iterator() sage: next(it) A wang tiling of a 3 x 4 rectangle sage: next(it) A wang tiling of a 3 x 4 rectangle
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles,2,2) sage: list(W.solutions_iterator()) [A wang tiling of a 2 x 2 rectangle, A wang tiling of a 2 x 2 rectangle, A wang tiling of a 2 x 2 rectangle]
With preassigned colors and tiles:
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2), (0,1,2,0)] sage: t = {(0,1):0} sage: c = [{},{},{(1,1):0},{}] sage: W = WangTileSolver(tiles,3,3,preassigned_tiles=t,preassigned_color=c) sage: S = list(W.solutions_iterator()) sage: [s._table for s in S] [[[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 3], [0, 0, 0], [0, 0, 0]]]
With preassigned colors and tiles:
sage: right = {(0, 1): 'A', (0, 0): 'A'} sage: top = {(0, 1): 'B'} sage: left = {(0, 1): 'A', (0, 0): 'A'} sage: bottom = {(0, 0): 'B'} sage: preassigned_color=[right,top,left,bottom] sage: tiles = ['ABCD', 'EFGH', 'AXCY', 'ABAB', 'EBEB'] sage: W = WangTileSolver(tiles, 1, 2, preassigned_color=preassigned_color) sage: solutions = list(W.solutions_iterator()) sage: [t.table() for t in solutions] [[[3, 3]]]
-
solve
(solver=None, solver_parameters=None, ncpus=1)¶ Return a dictionary associating to each tile a list of positions where to find this tile.
INPUT:
solver
– string or None (default:None
),'dancing_links'
or the name of a MILP solver in Sage like'GLPK'
,'Coin'
,'cplex'
or'Gurobi'
.solver_parameters
– dict (default:{}
), parameters given to the MILP solver using methodsolver_parameter
. For a list of available parameters for example for the Gurobi backend, see dictionaryparameters_type
in the filesage/numerical/backends/gurobi_backend.pyx
ncpus
– integer (default:1
), maximal number of subprocesses to use at the same time, used only ifsolver
is'dancing_links'
.
OUTPUT:
a wang tiling objectEXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve() sage: table = tiling._table sage: table [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
The tile at position (1,3) is:
sage: table[1][3] 0
Allowing more threads while using Gurobi:
sage: W = WangTileSolver(tiles,3,4) sage: kwds = dict(Threads=4) sage: tiling = W.solve(solver='Gurobi', kwds) # optional Gurobi sage: tiling._table # optional Gurobi [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
Using dancing links:
sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve(solver='dancing_links', ncpus=8) sage: tiling A wang tiling of a 3 x 4 rectangle
Using dancing links with tile 2 preassigned at position (0,1):
sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: preassigned = {(0,1):1} sage: W = WangTileSolver(tiles,3,3,preassigned_tiles=preassigned) sage: tiling = W.solve(solver='dancing_links') sage: tiling._table [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Using dancing links when constraints are inconsistent:
sage: right = {(1,1):1, (2,2):0} sage: W = WangTileSolver(tiles,3,3,preassigned_color=[right,{},{},{}]) sage: W.solve(solver='dancing_links') Traceback (most recent call last): ... ValueError: no solution found using dancing links, the return value from dancing links solver is None
Using SatLP solver:
sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve('LP') sage: tiling A wang tiling of a 3 x 4 rectangle
Using SatLP solver with preassigned tiles:
sage: preassigned = {(0,0):0} sage: W = WangTileSolver(tiles,3,4,preassigned_tiles=preassigned) sage: tiling = W.solve(solver='LP') sage: tiling._table [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
Using cryptominisat solver:
sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve('cryptominisat') # optional cryptominisat sage: tiling._table # optional cryptominisat [[1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]
REFERENCES:
How do I set solver_parameter to make Gurobi use more than one processor?, https://ask.sagemath.org/question/37726/
-
vertical_alphabet
()¶
-
class
slabbe.wang_tiles.
WangTiling
(table, tiles, color=None)¶ Bases:
object
INPUT:
table
– list of liststiles
– list of tiles, a tile is a 4-tuple (right color, top color, left color, bottom color)color
– dict (default: None)
Note
table[x][y]
refers to the tile at position \((x,y)\) using the cartesian coordinates. Thus, it is not using the matrix-like coordinates.EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling A wang tiling of a 3 x 4 rectangle
Using some blank tiles:
sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, None, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling A wang tiling of a 3 x 4 rectangle
-
apply_matrix_transformation
(M)¶ INPUT:
M
– matrix in GL(2,Z)
EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: M = matrix(2, (1,1,0,1)) sage: tiling_M = tiling.apply_matrix_transformation(M) sage: tiling_M.table() [[0, None, None, None], [1, 1, None, None], [0, 0, 0, None], [None, 1, 1, 1], [None, None, 0, 0], [None, None, None, 1]]
-
height
()¶ EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.height() 4
-
horizontal_words_dict
(length)¶ Return a dict of horizontal words (left to right) of given length starting at each position (x,y).
INPUT:
length
– integer
OUTPUT:
dict position -> wordEXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.horizontal_words_dict(2) {(0, 0): (4, 3), (0, 1): (3, 4), (0, 2): (4, 3), (0, 3): (3, 4), (0, 4): (4, 3), (1, 0): (3, 4), (1, 1): (4, 3), (1, 2): (3, 4), (1, 3): (4, 3), (1, 4): (3, 4)}
-
horizontal_words_list
(side=3)¶ Return a list of horizontal words of colors appearing on a given side.
INPUT
side
– integer in [0,1,2,3], 3 is for bottom
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve() sage: tiling.horizontal_words_list() [[4, 3, 4], [3, 4, 3], [4, 3, 4], [3, 4, 3]] sage: tiling.horizontal_words_list(0) [[0, 1, 0], [1, 0, 1], [0, 1, 0], [1, 0, 1]]
-
number_of_occurences
(pattern, avoid_border=0)¶ Return the number of occurences of the given pattern in the tiling.
INPUT
pattern
– dictavoid_border
– integer (default: 0), the size of the border to avoid during the computation
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve() sage: tiling.number_of_occurences({(0,0):0}) 6 sage: tiling.number_of_occurences({(0,0):1}) 6 sage: tiling.number_of_occurences({(0,0):1, (1,0):1}) 0 sage: tiling.number_of_occurences({(0,0):1, (1,0):1, (0,1):1}) 0 sage: tiling.number_of_occurences({(0,0):1, (1,0):0, (0,1):0}) 3
The pattern is translation invariant:
sage: tiling.number_of_occurences({(0,-1):1}) 6 sage: tiling.number_of_occurences({(-1,-1):1}) 6 sage: tiling.number_of_occurences({(-100,-100):1}) 6
The x coordinates of the pattern corresponds to the x coordinates when you plot it:
sage: tiles = [(0,3,0,4), (1,4,1,3)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve() sage: tiling.number_of_occurences({(0,0):1}) 6 sage: tiling.number_of_occurences({(0,0):1, (1,0):1}) 4 sage: tiling.number_of_occurences({(0,0):1, (0,1):1}) 0 sage: tiling.tikz().pdf(view=False) # not tested
When avoiding the border:
sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve() sage: tiling.number_of_occurences({(0,0):0}, avoid_border=1) 1
-
pattern_occurrences
(shape, avoid_border=0)¶ Return the number of occurences of every pattern having a given shape.
INPUT
shape
– list, list of coordinatesavoid_border
– integer (default: 0), the size of the border to avoid during the computation
OUTPUT
a dict where each key is a tuple giving the tiles at each coordinate of the shape (in the same order) and values are integers
EXAMPLES:
sage: from slabbe import WangTiling sage: table = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] sage: tiles = [(0, 0, 0, 0), (1, 1, 1, 1), (2, 2, 2, 2)] sage: tiling = WangTiling(table, tiles) sage: tiling.pattern_occurrences([(0,0)]) Counter({(0,): 12})
sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.pattern_occurrences([(0,0)]) Counter({(0,): 6, (1,): 6}) sage: c = tiling.pattern_occurrences([(0,0), (1,0), (0,1)]) sage: sorted(c.items()) [((0, 1, 1), 3), ((1, 0, 0), 3)]
When avoiding the border:
sage: tiling.pattern_occurrences([(0,0)], avoid_border=1) Counter({(0,): 1, (1,): 1}) sage: tiling.pattern_occurrences([(0,0)], avoid_border=2) Counter()
-
plot_points_on_torus
(M, pointsize=5, color_dict=None, start=None)¶ Plot points modulo some values in x and y.
INPUT
M
– M is the matrix projection to \(\mathbb{R}^2/\mathbb{Z}^2\)pointsize
– positive real number (default:5
)color_dict
– dict, tile index -> color or None (default:None
)start
– None or vector
EXAMPLES:
sage: from slabbe import WangTiling sage: z = polygen(QQ, 'z') sage: K.<phi> = NumberField(z^2-z-1, 'phi', embedding=AA(golden_ratio)) sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: T = WangTiling(table, tiles) sage: M = matrix(2, [phi, 0, 0, 0.01]) sage: G = T.plot_points_on_torus(M)
-
slide
(shift, x0=None, y0=1)¶ INPUT:
shift
– integerx0
– integer or None, every tile at (x,y) such that x>=x0 will be shifted by (0,shift)y0
– integer or None, every tile at (x,y) such that y>=y0 will be shifted by (shift,0)
EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.slide(0).table() [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling.slide(3).table() [[0, None, None, None], [1, None, None, None], [0, None, None, None], [None, 1, 0, 1], [None, 0, 1, 0], [None, 1, 0, 1]] sage: tiling.slide(2, x0=2).table() [[0, 1, 0, 1, None, None], [1, 0, 1, 0, None, None], [None, None, 0, 1, 0, 1]] sage: tiling.slide(-2, x0=2).table() [[None, None, 0, 1, 0, 1], [None, None, 1, 0, 1, 0], [0, 1, 0, 1, None, None]]
-
table
()¶ EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.table() [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
-
tikz
(color=None, font='\\normalsize', rotate=None, id=True, id_color='', id_format='{}', label=True, label_shift=0.2, label_color='black', scale=1, size=1, edges=True, draw_H=None, draw_V=None, extra_before='', extra_after='')¶ Return a tikzpicture showing one solution.
INPUT:
color
– None or dict from tile values -> tikz colorsfont
– string (default:r'\normalsize'
rotate
– list orNone
(default:None
) list of four angles in degrees like(0,0,0,0)
, the rotation angle to apply to each label of Wang tiles. IfNone
, it performs a 90 degres rotation for left and right labels taking more than one character.id
– boolean (default:True
), presence of the tile idid_color
– string (default:''
)id_format
– string (default:r'{}'
) to be called withid_format.format(key)
edges
– bool (default:True
)label
– boolean (default:True
), presence of the color labelslabel_shift
– number (default:.2
) translation distance of the label from the edgelabel_color
– string (default:'black'
)scale
– number (default:1
), tikzpicture scalesize
– number (default:1
) size of tilesdraw_H
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {} -- ++ (1,0);'
. Dict values must be stringss
such thats.format((x,y))
works.draw_V
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {} -- ++ (0,1);'
. Dict values must be stringss
such thats.format((x,y))
works.extra_before
– string (default:''
) extra lines of tikz code to add at the startextra_after
– string (default:''
) extra lines of tikz code to add at the end
EXAMPLES:
sage: from slabbe import WangTileSolver sage: tiles = [(0,0,0,0), (1,1,1,1), (2,2,2,2)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve() sage: t = tiling.tikz() sage: t \documentclass[tikz]{standalone} \usepackage{amsmath} \begin{document} \begin{tikzpicture}[scale=1] \tikzstyle{every node}=[font=\normalsize] % tile at position (x,y)=(0, 0) \node[] at (0.5, 0.5) {0}; \draw (0, 0) -- ++ (0,1); ... ... 96 lines not printed (3570 characters in total) ... ... \node[rotate=0,black] at (2.8, 3.5) {0}; \node[rotate=0,black] at (2.5, 3.8) {0}; \node[rotate=0,black] at (2.2, 3.5) {0}; \node[rotate=0,black] at (2.5, 3.2) {0}; \end{tikzpicture} \end{document}
With colors:
sage: tiles = [(0,2,1,3), (1,3,0,2)] sage: color = {0:'white',1:'red',2:'blue',3:'green'} sage: W = WangTileSolver(tiles,3,4,color=color) sage: tiling = W.solve() sage: t = tiling.tikz()
With colors, alternatively:
sage: tiles = [(0,2,1,3), (1,3,0,2)] sage: W = WangTileSolver(tiles,3,4) sage: tiling = W.solve('GLPK') sage: color = {0:'white',1:'red',2:'blue',3:'green'} sage: t = tiling.tikz(color=color)
Using some blank tiles:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,2), (1,2,0,3)] sage: table = [[0, 1, None, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: color = {0:'white',1:'red',2:'blue',3:'green'} sage: tiling = WangTiling(table, tiles, color) sage: t = tiling.tikz()
Testing the options:
sage: tiles = [(0,3,1,2), (1,2,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: color = {0:'white',1:'red',2:'blue',3:'green'} sage: t = WangTiling(table, tiles, color).tikz(font=r'\Huge') sage: t = WangTiling(table, tiles, color).tikz(rotate=(0,90,0,0)) sage: t = WangTiling(table, tiles, color).tikz(label_shift=.05) sage: t = WangTiling(table, tiles, color).tikz(scale=4)
sage: m = matrix(2,[1,1,0,1]) sage: t = WangTiling(table, tiles, color).apply_matrix_transformation(m).tikz()
Using puzzle boundary instead of colors:
sage: tiles = [(0,3,1,2), (1,2,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: t = WangTiling(table, tiles) sage: draw_H = {0:r'\draw {} -- ++ (1/2,.2) -- ++ (1/2,-.2);', ....: 1:r'\draw {} -- ++ (1/2,.2) -- ++ (1/2,-.2);', ....: 2:r'\draw {} -- ++ (1/2,.2) -- ++ (1/2,-.2);', ....: 3:r'\draw {} -- ++ (1/2,.2) -- ++ (1/2,-.2);'} sage: v = r'\draw {} -- ++ (0,.4) -- ++ (.2,0) -- ++ (0,.2) -- ++ (-.2,0) -- ++ (0,.4);' sage: draw_V = {0:v, 1:v, 2:v, 3:v} sage: tikz = t.tikz(label=False, draw_H=draw_H, draw_V=draw_V)
-
tile_frequency
(avoid_border=1)¶ EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.tile_frequency() {(0,): 1/2, (1,): 1/2}
-
tile_positions
(M)¶ Return the list of positions where tile of M appear.
INPUT:
M
– subset of tile indices
EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.tile_positions([0]) [(0, 0), (0, 2), (1, 1), (1, 3), (2, 0), (2, 2)]
TESTS:
sage: tiling.tile_positions([]) []
-
transpose
()¶ EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: M = matrix(2, (1,1,0,1)) sage: tiling_T = tiling.transpose() sage: tiling_T.table() [[0, 1, 0], [1, 0, 1], [0, 1, 0], [1, 0, 1]]
-
vertical_words_dict
(length)¶ Return a dict of vertical words (bottom to top) of given length starting at each position (x,y).
INPUT:
length
– integer
OUTPUT:
dict position -> wordEXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.vertical_words_dict(2) {(0, 0): (1, 0), (0, 1): (0, 1), (0, 2): (1, 0), (1, 0): (0, 1), (1, 1): (1, 0), (1, 2): (0, 1), (2, 0): (1, 0), (2, 1): (0, 1), (2, 2): (1, 0), (3, 0): (0, 1), (3, 1): (1, 0), (3, 2): (0, 1)} sage: tiling.vertical_words_dict(3) {(0, 0): (1, 0, 1), (0, 1): (0, 1, 0), (1, 0): (0, 1, 0), (1, 1): (1, 0, 1), (2, 0): (1, 0, 1), (2, 1): (0, 1, 0), (3, 0): (0, 1, 0), (3, 1): (1, 0, 1)}
-
width
()¶ EXAMPLES:
sage: from slabbe import WangTiling sage: tiles = [(0,3,1,4), (1,4,0,3)] sage: table = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]] sage: tiling = WangTiling(table, tiles) sage: tiling.width() 3
-
slabbe.wang_tiles.
fusion
(tile0, tile1, direction, function=<slot wrapper '__add__' of 'str' objects>, initial='')¶ Return the fusion of wang tile sets in the given direction.
We keep only the strongly connected components.
INPUT:
tile0
– 4-upletile1
– 4-upledirection
– integer (1 or 2)function
– function (default:str.__add__
), monoid- operation
initial
– object (default:''
), monoid neutral
EXAMPLES:
sage: from slabbe.wang_tiles import fusion sage: t0 = 'abcd' sage: t1 = 'xyaz' sage: fusion(t0,t1,1) ('x', 'by', 'c', 'dz')
sage: t0 = 'abcd' sage: t1 = 'xyzb' sage: fusion(t0,t1,2) ('ax', 'y', 'cz', 'd')
TESTS:
sage: t0 = 'abcd' sage: t1 = 'efgh' sage: fusion(t0,t1,1) Traceback (most recent call last): ... AssertionError: A must be equal to Y
-
slabbe.wang_tiles.
tile_to_tikz
(tile, position, color=None, id=None, id_color='', id_format='{}', sizex=1, sizey=1, rotate=None, label=True, label_shift=0.2, label_color='black', right_edges=True, top_edges=True, left_edges=True, bottom_edges=True, draw_H=None, draw_V=None)¶ INPUT:
tile
– tuple of length 4position
– tuple of two numberscolor
– dict (default:None
) from tile values -> tikz colorsid
– id (default:None
) of the tile to be printed in the centerid_color
– string (default:''
)id_format
– string (default:r'{}'
) to be called withid_format.format(key)
sizex
– number (default:1
), horizontal size of the tilesizey
– number (default:1
), vertical size of the tilerotate
– list orNone
(default:None
) list of four angles in degrees like(0,0,0,0)
, the rotation angle to apply to each label of Wang tiles. IfNone
, it performs a 90 degres rotation for left and right labels taking more than one character.label
– boolean (default:True
)label_shift
– number (default:.2
) translation distance of the label from the edgelabel_color
– string (default:'black'
)right_edges
– bool (default:True
)top_edges
– bool (default:True
)left_edges
– bool (default:True
)bottom_edges
– bool (default:True
)draw_H
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {{}} -- ++ (1,0);'
. Dict values must be stringss
such thats.format((x,y))
works.draw_V
– dict (default:None
) from tile values -> tikz draw commands. IfNone
the values of the dict get replaced by straight lines, more precisely byr'\draw {{}} -- ++ (0,1);'
. Dict values must be stringss
such thats.format((x,y))
works.
OUTPUT:
- list of strings
EXAMPLES:
sage: from slabbe.wang_tiles import tile_to_tikz sage: color = {0:'white',1:'red',2:'cyan',3:'green',4:'white'} sage: tile_to_tikz((1,2,3,4), (10,100), color) ['% tile at position (x,y)=(10, 100)', '\\fill[red] (11, 100) -- (10.5, 100.5) -- (11, 101);', '\\fill[cyan] (10, 101) -- (10.5, 100.5) -- (11, 101);', '\\fill[green] (10, 100) -- (10.5, 100.5) -- (10, 101);', '\\fill[white] (10, 100) -- (10.5, 100.5) -- (11, 100);', '\\draw (11, 100) -- ++ (0,1);', '\\draw (10, 101) -- ++ (1,0);', '\\draw (10, 100) -- ++ (0,1);', '\\draw (10, 100) -- ++ (1,0);', '\\node[rotate=0,black] at (10.8, 100.5) {1};', '\\node[rotate=0,black] at (10.5, 100.8) {2};', '\\node[rotate=0,black] at (10.2, 100.5) {3};', '\\node[rotate=0,black] at (10.5, 100.2) {4};'] sage: tile_to_tikz((1,2,3,4), (10,100), color=None) ['% tile at position (x,y)=(10, 100)', '\\draw (11, 100) -- ++ (0,1);', '\\draw (10, 101) -- ++ (1,0);', '\\draw (10, 100) -- ++ (0,1);', '\\draw (10, 100) -- ++ (1,0);', '\\node[rotate=0,black] at (10.8, 100.5) {1};', '\\node[rotate=0,black] at (10.5, 100.8) {2};', '\\node[rotate=0,black] at (10.2, 100.5) {3};', '\\node[rotate=0,black] at (10.5, 100.2) {4};'] sage: tile_to_tikz((1,2,3,4), (10,100), color=None, rotate=(0,90,0,0)) ['% tile at position (x,y)=(10, 100)', '\\draw (11, 100) -- ++ (0,1);', '\\draw (10, 101) -- ++ (1,0);', '\\draw (10, 100) -- ++ (0,1);', '\\draw (10, 100) -- ++ (1,0);', '\\node[rotate=0,black] at (10.8, 100.5) {1};', '\\node[rotate=90,black] at (10.5, 100.8) {2};', '\\node[rotate=0,black] at (10.2, 100.5) {3};', '\\node[rotate=0,black] at (10.5, 100.2) {4};'] sage: tile_to_tikz((1,2,3,4), (10,100), color=None, label_shift=.1) ['% tile at position (x,y)=(10, 100)', '\\draw (11, 100) -- ++ (0,1);', '\\draw (10, 101) -- ++ (1,0);', '\\draw (10, 100) -- ++ (0,1);', '\\draw (10, 100) -- ++ (1,0);', '\\node[rotate=0,black] at (10.9000000000000, 100.5) {1};', '\\node[rotate=0,black] at (10.5, 100.900000000000) {2};', '\\node[rotate=0,black] at (10.1000000000000, 100.5) {3};', '\\node[rotate=0,black] at (10.5, 100.100000000000) {4};']
sage: tile_to_tikz((10,20,30,40), (10,100), color=None) ['% tile at position (x,y)=(10, 100)', '\\draw (11, 100) -- ++ (0,1);', '\\draw (10, 101) -- ++ (1,0);', '\\draw (10, 100) -- ++ (0,1);', '\\draw (10, 100) -- ++ (1,0);', '\\node[rotate=90,black] at (10.8, 100.5) {10};', '\\node[rotate=0,black] at (10.5, 100.8) {20};', '\\node[rotate=90,black] at (10.2, 100.5) {30};', '\\node[rotate=0,black] at (10.5, 100.2) {40};']