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 – integer
  • width – integer
  • height – integer

OUTPUT:

set of tuples

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.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 – integer
  • width – integer
  • height – integer

OUTPUT:

set of tuples

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.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 or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, it performs a 90 degres rotation for left and right labels taking more than one character.
  • label – boolean (default: True), presence of the colors
  • label_shift – number (default: .2) translation distance of the label from the edge
  • label_color – string (default: 'black')
  • id – boolean (default: True), presence of the tile id
  • id_color – string (default: '')
  • id_format – string (default: r'{}') to be called with id_format.format(key)
  • draw_H – dict (default: None) from tile values -> tikz draw commands. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {{}} -- ++ (1,0);'. Dict values must be strings s such that s.format((x,y)) works.
  • draw_V – dict (default: None) from tile values -> tikz draw commands. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {{}} -- ++ (0,1);'. Dict values must be strings s such that s.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 2d
  • fn – a function (default: None) to apply to the new colors which are tuple of previous colors

OUTPUT:

dict, key -> tile

EXAMPLES:

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 2
  • radius - 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 if solver 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 lists

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 = [map(str,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 lists

EXAMPLES:

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 indices
  • i – integer 1 or 2
  • side'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 neutral
  • verbose – 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 = [map(str,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 – WangTileSet
  • direction – integer (1 or 2)
  • function – function (default:str.__add__), monoid operation
  • initial – object (default:''), monoid neutral
  • clean_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 set
  • certificate – 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 indices
  • B – list of tile indices
  • i – integer, 1 or 2
  • radius – 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
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 operation
  • verbose – 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: U.tiles()
[('aadd', 'dd', 'ccbb', 'bb'),
 ('aadd', 'dd', 'ccdd', 'bb'),
 ('ccdd', 'dd', 'aadd', 'dd'),
 ('ccbb', 'bb', '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 – integer
  • height – integer
  • preassigned_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 positions
  • color – 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 2d
  • fn – a function (default: None) to apply to the new colors which are tuple of previous colors
  • color – dict (default: None) from tile values -> tikz colors
  • size – number (default: 1), size of the tile
  • scale – number (default: 1), scale of tikzpicture
  • font – string (default: r'\normalsize'
  • rotate – list or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, 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 edge
  • ncolumns – 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
[ 0  1  1 -1  0  0  0  0]
[ 0 -1  0  1  0 -1  0  0]
[ 0  0 -1  0  0  1  0  0]
[ 1  1 -1  0  0 -1  1  0]
[ 0 -1  1  0 -1  1 -1  0]
[-1  0  0  0  1  0  0  0]
[ 1  1  1  1  1  1  1  1]
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 or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, it performs a 90 degres rotation for left and right labels taking more than one character.
  • label – boolean (default: True), presence of the colors
  • id – boolean (default: True), presence of the tile id
  • id_color – string (default: '')
  • id_format – string (default: r'{}') to be called with id_format.format(key)
  • label_shift – number (default: .2) translation distance of the label from the edge
  • label_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. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {{}} -- ++ (1,0);'. Dict values must be strings s such that s.format((x,y)) works.
  • draw_V – dict (default: None) from tile values -> tikz draw commands. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {{}} -- ++ (0,1);'. Dict values must be strings s such that s.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 - integer
  • solver - string or None
  • ncpus - integer
  • verbose - 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 - integer
  • height - integer
  • radius - integer
  • solver - string or None
  • verbose - 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 = [map(str, 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]]]
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=<type '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 one
  • merge_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 2
  • size – integer, 2 or more
  • verbose – 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 – integer
  • height – integer
  • preassigned_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 positions
  • color – 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 tilings

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: 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 Solver

EXAMPLES:

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 method solver_parameter. For a list of available parameters for example for the Gurobi backend, see dictionary parameters_type in the file sage/numerical/backends/gurobi_backend.pyx
  • ncpus – integer (default: 1), maximal number of subprocesses to use at the same time, used only if solver is 'dancing_links'.

OUTPUT:

a wang tiling object

EXAMPLES:

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 (with None 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: support
[(0, 1, 1), (0, 1, 3), (0, 2, 1), (0, 2, 0), (0, 2, 3), (0, 2, 2), 
 (0, 1, 2), (0, 0, 3), (0, 0, 2), (0, 0, 1), (0, 0, 0), (0, 1, 0)]

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, False, True, False, True, True, False, True, False,
 False, True, False, True, True, False, True, False, False,
 True, False, True, True, False, True, False]
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 tilings

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: 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' or 'Gurobi'.
  • solver_parameters – dict (default: {}), parameters given to the MILP solver using method solver_parameter. For a list of available parameters for example for the Gurobi backend, see dictionary parameters_type in the file sage/numerical/backends/gurobi_backend.pyx
  • ncpus – integer (default: 1), maximal number of subprocesses to use at the same time, used only if solver is 'dancing_links'.

OUTPUT:

a wang tiling object

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: 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._table
[[1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]

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 lists
  • tiles – 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 SL(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 -> word

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.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 – dict
  • avoid_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 coordinates
  • avoid_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: tiling.pattern_occurrences([(0,0), (1,0), (0,1)])
Counter({(1, 0, 0): 3, (0, 1, 1): 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)

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)

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 – integer
  • x0 – 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 colors
  • font – string (default: r'\normalsize'
  • rotate – list or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, it performs a 90 degres rotation for left and right labels taking more than one character.
  • id – boolean (default: True), presence of the tile id
  • id_color – string (default: '')
  • id_format – string (default: r'{}') to be called with id_format.format(key)
  • edges – bool (default: True)
  • label – boolean (default: True), presence of the color labels
  • label_shift – number (default: .2) translation distance of the label from the edge
  • label_color – string (default: 'black')
  • scale – number (default: 1), tikzpicture scale
  • size – number (default: 1) size of tiles
  • draw_H – dict (default: None) from tile values -> tikz draw commands. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {} -- ++ (1,0);'. Dict values must be strings s such that s.format((x,y)) works.
  • draw_V – dict (default: None) from tile values -> tikz draw commands. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {} -- ++ (0,1);'. Dict values must be strings s such that s.format((x,y)) works.
  • extra_before – string (default: '') extra lines of tikz code to add at the start
  • extra_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 -> word

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.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-uple
  • tile1 – 4-uple
  • direction – 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 4
  • position – tuple of two numbers
  • color – dict (default: None) from tile values -> tikz colors
  • id – id (default: None) of the tile to be printed in the center
  • id_color – string (default: '')
  • id_format – string (default: r'{}') to be called with id_format.format(key)
  • sizex – number (default: 1), horizontal size of the tile
  • sizey – number (default: 1), vertical size of the tile
  • rotate – list or None (default:None) list of four angles in degrees like (0,0,0,0), the rotation angle to apply to each label of Wang tiles. If None, 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 edge
  • label_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. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {{}} -- ++ (1,0);'. Dict values must be strings s such that s.format((x,y)) works.
  • draw_V – dict (default: None) from tile values -> tikz draw commands. If None the values of the dict get replaced by straight lines, more precisely by r'\draw {{}} -- ++ (0,1);'. Dict values must be strings s such that s.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};']