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='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)


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)
{(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)
{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 2)}
{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}
{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}
{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}


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)
{(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)
{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}
{(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)]

closure_under_rotation()

Return the closure of the set of Wang tiles under rotations.

EXAMPLES:

sage: from slabbe import WangTileSet
sage: tiles = [(0,1,2,3)]
sage: T = WangTileSet(tiles)
sage: T.closure_under_rotation()
Wang tile set of cardinality 4
sage: _.tiles()
[(0, 1, 2, 3), (1, 2, 3, 0), (2, 3, 0, 1), (3, 0, 1, 2)]

closure_under_symmetries()

Return the closure of the set of Wang tiles under symmetries.

EXAMPLES:

sage: from slabbe import WangTileSet
sage: tiles = [(0,1,2,3)]
sage: T = WangTileSet(tiles)
sage: T.closure_under_symmetries()
Wang tile set of cardinality 8
sage: _.tiles()
[(0, 1, 2, 3),
(0, 3, 2, 1),
(1, 0, 3, 2),
(1, 2, 3, 0),
(2, 1, 0, 3),
(2, 3, 0, 1),
(3, 0, 1, 2),
(3, 2, 1, 0)]

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')}


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)]
[(3, 3), (3, 4), (4, 3), (4, 4)]
[(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)]


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 = [[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 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 = [[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 – 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)

Return whether self and other are equivalent.

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_equivalent_up_to_isometry(other, certificate=False)

Return whether self and other are equivalent up to isometry.

INPUT:

• other – wang tile set

• certificate – boolean (default:False)

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: p = DihedralGroup(4)[6]
sage: pL = [p(tuple(d[a] for a in t)) for t in tiles]
sage: U = WangTileSet(pL)
sage: T.is_equivalent(U)
False
sage: T.is_equivalent_up_to_isometry(U)
True
sage: T.is_equivalent_up_to_isometry(U, certificate=True)
(True,
((1,4)(2,3),
{6: 'x', 7: 'y', 8: 'z'},
{1: 'a', 2: 'b', 3: 'c'},
Substitution 2d: {0: [[0]], 1: [[1]], 2: [[2]], 3: [[3]], 4: [[4]], 5: [[5]], 6: [[6]]}))

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


Return whether the rectangular pattern allows a surrounding of given radius.

INPUT:

• pattern – list of lists of tile indices

• 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: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)
True
False
False
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))

rotate(i=1)

Return the rotated copy of the tiles by a clockwise rotation.

INPUT:

• i – integer (default:1), number of quarter turns.

EXAMPLES:

sage: from slabbe import WangTileSet
sage: tiles = [(0,1,2,3)]
sage: T = WangTileSet(tiles)
sage: T.rotate()
Wang tile set of cardinality 1

sage: T.rotate().tiles()
[(1, 2, 3, 0)]
sage: T.rotate(i=2).tiles()
[(2, 3, 0, 1)]
sage: T.rotate(i=3).tiles()
[(3, 0, 1, 2)]


TESTS:

sage: T.rotate(i=4).tiles()
[(0, 1, 2, 3)]
sage: T.rotate(i=7).tiles()
[(3, 0, 1, 2)]
sage: T.rotate(i=-3).tiles()
[(1, 2, 3, 0)]


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()
sage: T.shear()[0].shear()[0].tiles()

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())
sage: s
Substitution 2d: {0: [[0]], 1: [[2]]}
sage: U.tiles()

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
[ 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 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)]


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, ...], [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, ncpus=1, use_previous_smaller_results=True, 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 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'.

• use_previous_smaller_results - bool (default: True)

• verbose - bool (default: False)

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(2,2)
sage: sorted(tiling.table() for tiling in S)
[[[0, 0], [0, 0]], [[1, 1], [1, 1]], [[2, 2], [2, 2]]]

sage: S = T.tilings_with_surrounding(3,3)
sage: sorted(tiling.table() for tiling 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: sorted(tiling.table() for tiling in solutions)   # random
[[[3, 3]], [[4, 4]], [[3, 4]], [[4, 3]]]

sage: tiles = [('02', '4', '02', '4'), ('32', '4', '02', '4')]
sage: T = WangTileSet(tiles)
sage: [tiling.table() for tiling in T.tilings_with_surrounding(1,2)]
[[[0, 0]]]
sage: [tiling.table() for tiling 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=<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 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'))]

union(other)

Return the union of two wang tile sets.

INPUT:

• other – WangTileSet

EXAMPLES:

sage: from slabbe import WangTileSet
sage: tiles_A = ['ABCD', 'EFGH', 'AXCY', 'ABAB']
sage: A = WangTileSet(tiles_A)
sage: tiles_B = ['ABCD', 'XYZW']
sage: B = WangTileSet(tiles_B)
sage: A.union(B)
Wang tile set of cardinality 5
sage: A.union(B).tiles()
[('A', 'B', 'A', 'B'),
('A', 'B', 'C', 'D'),
('A', 'X', 'C', 'Y'),
('E', 'F', 'G', 'H'),
('X', 'Y', 'Z', 'W')]

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()           # known bug (in Python 3)
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]                # known bug (in Python 3)
[[2, 2], [2, 2], [2, 2], [2, 2]]
sage: [node.is_synchronized() for node in G]          # known bug (in Python 3)
[True, True, True, True]
sage: from slabbe import TikzPicture
sage: _ = TikzPicture.from_graph(G).pdf(view=False)   # known bug (in Python 3)

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()       # known bug (in Python 3)
sage: sorted(G.vertices())                     # known bug (in Python 3)
[('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: tiling = W.has_solution(solver='Gurobi', kwds) # optional Gurobi
True


sage: W = WangTileSolver(tiles,3,4)
True


Using cryptominisat:

sage: W = WangTileSolver(tiles,3,4)
sage: W.has_solution(solver='cryptominisat') # optional cryptominisat
True

horizontal_alphabet()

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: W.horizontal_alphabet()
{0, 1, 2}

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 ...


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: 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 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', 'cplex' 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: 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]]


sage: W = WangTileSolver(tiles,3,4)
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._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,{},{},{}])
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()

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: W.vertical_alphabet()
{0, 1, 2}

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 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]]

concatenate_right(other)

Return a concatenation of self with other on its right.

INPUT:

• other – a Wang tiling

EXAMPLES:

sage: from slabbe import WangTiling
sage: tiles = [(0,3,1,2), (1,2,0,3)]
sage: tableA = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
sage: tableB = [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
sage: tilingA = WangTiling(tableA, tiles)
sage: tilingB = WangTiling(tableB, tiles)
sage: t = tilingA.concatenate_right(tilingB)
sage: t
A wang tiling of a 6 x 4 rectangle
sage: t.table()
[[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]]

concatenate_top(other)

Return a concatenation of self with other on its top.

INPUT:

• other – a Wang tiling

EXAMPLES:

sage: from slabbe import WangTiling
sage: tiles = [(0,3,1,2), (1,2,0,3)]
sage: tableA = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
sage: tableB = [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
sage: tilingA = WangTiling(tableA, tiles)
sage: tilingB = WangTiling(tableB, tiles)
sage: t = tilingA.concatenate_top(tilingB)
sage: t
A wang tiling of a 3 x 8 rectangle
sage: t.table()
[[0, 0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 1]]

diff(other)

Return a tuple of three Wang tilings A,B,C such that self is the union of A and B, other is the union of A and C, and A is the maximum common part of both self and other.

INPUT:

• other – a Wang tiling

OUTPUT:

• A tiling of the common part of self and other.

• A tiling of the different part of self and other (the self part)

• A tiling of the different part of self and other (the other part)

EXAMPLES:

sage: from slabbe import WangTiling
sage: tiles = [(0,3,1,2), (1,2,0,3)]
sage: tableA = [[0, 1, 1, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
sage: tilingA = WangTiling(tableA, tiles)
sage: tableB = [[0, 1, 0, 0], [1, 0, 0, 0], [0, 1, 0, 1]]
sage: tilingB = WangTiling(tableB, tiles)
sage: d,ds,do = tilingA.diff(tilingB)
sage: d
A wang tiling of a 3 x 4 rectangle
sage: d.table()
[[0, 1, None, None], [1, 0, None, 0], [0, 1, 0, 1]]
sage: ds.table()
[[None, None, 1, 1], [None, None, 1, None], [None, None, None, None]]
sage: do.table()
[[None, None, 0, 0], [None, None, 0, None], [None, None, None, None]]

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_occurrences(pattern, avoid_border=0)

Return the number of occurrences 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_occurrences({(0,0):0})
6
sage: tiling.number_of_occurrences({(0,0):1})
6
sage: tiling.number_of_occurrences({(0,0):1, (1,0):1})
0
sage: tiling.number_of_occurrences({(0,0):1, (1,0):1, (0,1):1})
0
sage: tiling.number_of_occurrences({(0,0):1, (1,0):0, (0,1):0})
3


The pattern is translation invariant:

sage: tiling.number_of_occurrences({(0,-1):1})
6
sage: tiling.number_of_occurrences({(-1,-1):1})
6
sage: tiling.number_of_occurrences({(-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_occurrences({(0,0):1})
6
sage: tiling.number_of_occurrences({(0,0):1, (1,0):1})
4
sage: tiling.number_of_occurrences({(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_occurrences({(0,0):0}, avoid_border=1)
1

number_of_occurrences_with_shape(shape, avoid_border=0)

Return the number of occurrences 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.number_of_occurrences_with_shape([(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.number_of_occurrences_with_shape([(0,0)])
Counter({(0,): 6, (1,): 6})
sage: c = tiling.number_of_occurrences_with_shape([(0,0), (1,0), (0,1)])
sage: sorted(c.items())
[((0, 1, 1), 3), ((1, 0, 0), 3)]


When avoiding the border:

sage: tiling.number_of_occurrences_with_shape([(0,0)], avoid_border=1)
Counter({(0,): 1, (1,): 1})
sage: tiling.number_of_occurrences_with_shape([(0,0)], avoid_border=2)
Counter()

pattern_occurrences(pattern, avoid_border=0)

Return the set of occurrences 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.pattern_occurrences({(0,0):0})
{(0, 0), (0, 2), (1, 1), (1, 3), (2, 0), (2, 2)}
sage: tiling.pattern_occurrences({(0,0):1})
{(0, 1), (0, 3), (1, 0), (1, 2), (2, 1), (2, 3)}
sage: tiling.pattern_occurrences({(0,0):1, (1,0):1})
set()
sage: tiling.pattern_occurrences({(0,0):1, (1,0):1, (0,1):1})
set()
sage: tiling.pattern_occurrences({(0,0):1, (1,0):0, (0,1):0})
{(0, 1), (1, 0), (1, 2)}


The positions depends on the relative position of the pattern:

sage: tiling.pattern_occurrences({(0,-1):1})
{(0, 2), (0, 4), (1, 1), (1, 3), (2, 2), (2, 4)}
sage: tiling.pattern_occurrences({(-1,-1):1})
{(1, 2), (1, 4), (2, 1), (2, 3), (3, 2), (3, 4)}
sage: tiling.pattern_occurrences({(-100,-100):1})
{(100, 101), (100, 103), (101, 100), (101, 102), (102, 101), (102, 103)}


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.pattern_occurrences({(0,0):1})
{(0, 1), (0, 3), (1, 1), (1, 3), (2, 1), (2, 3)}
sage: tiling.pattern_occurrences({(0,0):1, (1,0):1})
{(0, 1), (0, 3), (1, 1), (1, 3)}
sage: tiling.pattern_occurrences({(0,0):1, (0,1):1})
set()
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.pattern_occurrences({(0,0):0}, avoid_border=1)
{(1, 1)}

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)

rows()

Return the rows from the top to the bottom.

EXAMPLES:

sage: from slabbe import WangTiling
sage: tiles = [(0,3,1,4)] * 10
sage: table = [[1,2,3,4], [5,6,7,8]]
sage: tiling = WangTiling(table, tiles)
sage: tiling.rows()
[(4, 8), (3, 7), (2, 6), (1, 5)]

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, color_by_tile_id=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 edge values -> tikz color

• color_by_tile_id – None or dict from tile id -> color, if not None, the result will ignore the color argument

• 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: ''), color of the id

• id_format – string (default: r'{}') to be called with id_format.format(key)

• edges – bool (default: True)

• label – boolean (default: True) or a tuple of four boolean, presence of the color labels

• label_shift – number (default: .2) translation distance of the label from the edge

• label_color – string (default: 'black'), color of the label

• scale – number or 2-tuple (default: 1), tikzpicture scale. If given a 2-tuple, it is interpreted as (xscale, yscale)

• 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};
...
... 97 lines not printed (3571 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()


Coloring the tiles by their id:

sage: d = {0:'green', 1:'yellow'}
sage: t = tiling.tikz(color_by_tile_id=d)


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([])
[]

to_image(color_dict=None)

INPUT:

• color_dict – dict (default:None) letters to RGB colors (tuple of 3 int), if None, random colors are chosen

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: img = tiling.to_image()
sage: img
<PIL.Image.Image image mode=RGB size=3x4 at ...>


Resize the result when too small:

sage: import PIL
sage: img.resize((100,100), resample=PIL.Image.NEAREST).show()     # not tested


Specify the colors:

sage: color_dict = {0:[255,255,255], 1:[0,0,0]}
sage: img = tiling.to_image(color_dict)
sage: img
<PIL.Image.Image image mode=RGB size=3x4 at ...>

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 or tuple or string (default: None), color of the whole tile, or color of each 4 edges (east, north, west, south), or dict of edge id to 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) or a tuple of four boolean

• 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};']