Tiling a n-dimensional box into non-intersecting n-dimensional polyominoes.
This uses dancing links code which is in Sage. Dancing links were originally introduced by Donald Knuth in 2000 [Knuth1]. In particular, Knuth used dancing links to solve tilings of a region by 2d pentaminoes. Here we extend the method to any dimension.
In particular, the sage.games.quantumino module is based on the Tiling Solver and allows to solve the 3d Quantumino puzzle.
This module defines two classes:
AUTHOR:
- Sebastien Labbe, June 2011
EXAMPLES:
Here is a 2d example. Let us try to fill the rectangle with a
rectangle and a
square. Obviously, there are two
solutions:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0), (0,1)])
sage: q = Polyomino([(0,0), (0,1), (1,0), (1,1)])
sage: T = TilingSolver([p,q], box=[3,2])
sage: it = T.solve()
sage: it.next()
[Polyomino: [(0, 0), (0, 1), (1, 0), (1, 1)], Color: gray, Polyomino: [(2, 0), (2, 1)], Color: gray]
sage: it.next()
[Polyomino: [(1, 0), (1, 1), (2, 0), (2, 1)], Color: gray, Polyomino: [(0, 0), (0, 1)], Color: gray]
sage: it.next()
Traceback (most recent call last):
...
StopIteration
sage: T.number_of_solutions()
2
Here is an easy one dimensional example where we try to tile a stick of length 6 with three sticks of length 1, 2 and 3. There are six solutions:
sage: p = Polyomino([[0]])
sage: q = Polyomino([[0],[1]])
sage: r = Polyomino([[0],[1],[2]])
sage: T = TilingSolver([p,q,r], box=[6])
sage: len(T.rows())
15
sage: it = T.solve()
sage: it.next()
[Polyomino: [(0,)], Color: gray, Polyomino: [(1,), (2,)], Color: gray, Polyomino: [(3,), (4,), (5,)], Color: gray]
sage: it.next()
[Polyomino: [(0,)], Color: gray, Polyomino: [(1,), (2,), (3,)], Color: gray, Polyomino: [(4,), (5,)], Color: gray]
sage: T.number_of_solutions()
6
The following is a puzzle owned by Florent Hivert:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: L = []
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3)], 'yellow'))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2)], "black"))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,3)], "gray"))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,0),(1,3)],"cyan"))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,0),(1,1)],"red"))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,1),(1,2)],"blue"))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(0,3),(1,1),(1,3)],"green"))
sage: L.append(Polyomino([(0,1),(0,2),(0,3),(1,0),(1,1),(1,3)],"magenta"))
sage: L.append(Polyomino([(0,1),(0,2),(0,3),(1,0),(1,1),(1,2)],"orange"))
sage: L.append(Polyomino([(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)],"pink"))
By default, rotations are allowed and reflections are not. In this case, there are no solution:
sage: T = TilingSolver(L, (8,8))
sage: T.number_of_solutions() # long time (2.5 s)
0
If reflections are allowed, there are solutions. Solve the puzzle and show one solution:
sage: T = TilingSolver(L, (8,8), reflection=True)
sage: solution = T.solve().next()
sage: G = sum([piece.show2d() for piece in solution], Graphics())
sage: G.show(aspect_ratio=1, axes=False)
Compute the number of solutions:
sage: T.number_of_solutions() # long time (2.6s)
328
Create a animation of all the solutions:
sage: a = T.animate() # not tested
sage: a # not tested
Animation with 328 frames
The same thing done in 3d without allowing reflections this time:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: L = []
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,1,0),(1,2,0),(1,3,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,1,0),(1,2,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,1,0),(1,3,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,3,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,1,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,1,0),(1,2,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(0,3,0),(1,1,0),(1,3,0)]))
sage: L.append(Polyomino([(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,1,0),(1,3,0)]))
sage: L.append(Polyomino([(0,1,0),(0,2,0),(0,3,0),(1,0,0),(1,1,0),(1,2,0)]))
sage: L.append(Polyomino([(0,0,0),(0,1,0),(0,2,0),(1,0,0),(1,1,0),(1,2,0)]))
Solve the puzzle and show one solution:
sage: T = TilingSolver(L, (8,8,1))
sage: solution = T.solve().next()
sage: G = sum([piece.show3d(size=0.85) for piece in solution], Graphics())
sage: G.show(aspect_ratio=1, viewer='tachyon')
Let us compute the number of solutions:
sage: T.number_of_solutions() # long time (3s)
328
Donald Knuth [Knuth1] considered the problem of packing 45 Y pentaminoes into a
square:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)])
sage: T = TilingSolver([y], box=(5,10), reusable=True, reflection=True)
sage: T.number_of_solutions()
10
sage: solution = T.solve().next()
sage: G = sum([piece.show2d() for piece in solution], Graphics())
sage: G.show(aspect_ratio=1)
sage: T = TilingSolver([y], box=(15,15), reusable=True, reflection=True)
sage: T.number_of_solutions() #not tested
212
Animation of the solutions:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: Y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='yellow')
sage: T = TilingSolver([Y], box=(15,15), reusable=True, reflection=True)
sage: a = T.animate(stop=40) # long time
sage: a # long time
Animation with 40 frames
sage: a.show() # not tested - requires convert command
Incremental animation of the solutions (one piece is removed/added at a time):
sage: a = T.animate('incremental', stop=40) # long time
sage: a # long time
Animation with 40 frames
sage: a.show(delay=50, iterations=1) # not tested - requires convert command
Here is a 5d example. Let us try to fill the rectangle with reusable
rectangles. Obviously, there is one solution:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: p = Polyomino([(0,0,0,0,0)])
sage: T = TilingSolver([p], box=(2,2,2,2,2), reusable=True)
sage: rows = T.rows() # long time (3s)
sage: rows # long time (fast)
[[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31]]
sage: T.number_of_solutions() # long time (fast)
1
REFERENCES:
[Knuth1] | (1, 2) Knuth, Donald (2000). “Dancing links”. Arxiv cs/0011047. |
Bases: sage.structure.sage_object.SageObject
Return the polyomino defined by a set of coordinates.
The polyomino is the union of the unit square (or cube, or n-cube) centered at those coordinates. Such an object should be connected, but the code do not make this assumption.
INPUT:
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='blue')
Polyomino: [(0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1)], Color: blue
Return the boundary of a 2d polyomino.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0), (1,0), (0,1), (1,1)])
sage: p.boundary()
[((0.5, 1.5), (1.5, 1.5)), ((-0.5, -0.5), (0.5, -0.5)), ((0.5, -0.5), (1.5, -0.5)), ((-0.5, 1.5), (0.5, 1.5)), ((-0.5, 0.5), (-0.5, 1.5)), ((-0.5, -0.5), (-0.5, 0.5)), ((1.5, 0.5), (1.5, 1.5)), ((1.5, -0.5), (1.5, 0.5))]
sage: len(_)
8
sage: p = Polyomino([(5,5)])
sage: p.boundary()
[((4.5, 5.5), (5.5, 5.5)), ((4.5, 4.5), (5.5, 4.5)), ((4.5, 4.5), (4.5, 5.5)), ((5.5, 4.5), (5.5, 5.5))]
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,1,1),(1,2,0)], color='deeppink')
sage: p.bounding_box()
[[0, 0, 0], [1, 2, 1]]
Returns the translated copy of self having minimal and positive coordinates
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,1,1),(1,2,0)], color='deeppink')
sage: p
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
sage: p.canonical()
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
TESTS:
sage: p
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
sage: p + (3,4,5)
Polyomino: [(3, 4, 5), (4, 4, 5), (4, 5, 5), (4, 5, 6), (4, 6, 5)], Color: deeppink
sage: (p + (3,4,5)).canonical()
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
Iterator over the image of self under orthogonal transformations where the coordinates are all positive and minimal.
Note
No guarantee of uniqueness.
INPUT:
OUTPUT:
iterator of Polyomino
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='blue')
sage: L = list(p.canonical_orthogonals())
sage: len(L)
24
They might not be all different:
sage: s = set(p.canonical_orthogonals())
sage: len(s)
12
With the non orientation-preserving:
sage: s = set(p.canonical_orthogonals(False))
sage: len(s)
24
Return the center of the polyomino.
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0),(0,0,1)])
sage: p.center()
(0, 0, 1/2)
In 3d:
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,1,1),(1,2,0)], color='deeppink')
sage: p.center()
(4/5, 4/5, 1/5)
In 2d:
sage: p = Polyomino([(0,0),(1,0),(1,1),(1,2)])
sage: p.center()
(3/4, 3/4)
Return the color of the polyomino.
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='blue')
sage: p.color()
'blue'
Return an iterator over the pairs of neighbor coordinates of the polyomino.
Two points and
are neighbor if
has one coordinate
equal to
or
and zero everywhere else.
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0),(0,0,1)])
sage: list(sorted(edge) for edge in p.neighbor_edges())
[[(0, 0, 0), (0, 0, 1)]]
In 3d:
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,1,1),(1,2,0)], color='deeppink')
sage: L = sorted(sorted(edge) for edge in p.neighbor_edges())
sage: for a in L: a
[(0, 0, 0), (1, 0, 0)]
[(1, 0, 0), (1, 1, 0)]
[(1, 1, 0), (1, 1, 1)]
[(1, 1, 0), (1, 2, 0)]
In 2d:
sage: p = Polyomino([(0,0),(1,0),(1,1),(1,2)])
sage: L = sorted(sorted(edge) for edge in p.neighbor_edges())
sage: for a in L: a
[(0, 0), (1, 0)]
[(1, 0), (1, 1)]
[(1, 1), (1, 2)]
Iterator over the images of self under orthogonal transformations.
Note
No guarantee of uniqueness.
INPUT:
OUTPUT:
iterator of Polyomino
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='blue')
sage: L = list(p.orthogonals())
sage: len(L)
24
sage: L = list(p.orthogonals(False))
sage: len(L)
48
Returns a 2d Graphic object representing the polyomino.
INPUT:
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0),(1,0),(1,1),(1,2)], color='deeppink')
sage: p.show2d() # long time (0.5s)
Returns a 3d Graphic object representing the polyomino.
INPUT:
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='blue')
sage: p.show3d()
Returns an iterator over the translated images of self inside a box.
INPUT:
OUTPUT:
iterator of 3d polyominoes
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,1,1),(1,2,0)], color='deeppink')
sage: for t in p.translated(box=(5,8,2)): t
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
Polyomino: [(0, 1, 0), (1, 1, 0), (1, 2, 0), (1, 2, 1), (1, 3, 0)], Color: deeppink
Polyomino: [(0, 2, 0), (1, 2, 0), (1, 3, 0), (1, 3, 1), (1, 4, 0)], Color: deeppink
Polyomino: [(0, 3, 0), (1, 3, 0), (1, 4, 0), (1, 4, 1), (1, 5, 0)], Color: deeppink
Polyomino: [(0, 4, 0), (1, 4, 0), (1, 5, 0), (1, 5, 1), (1, 6, 0)], Color: deeppink
Polyomino: [(0, 5, 0), (1, 5, 0), (1, 6, 0), (1, 6, 1), (1, 7, 0)], Color: deeppink
Polyomino: [(1, 0, 0), (2, 0, 0), (2, 1, 0), (2, 1, 1), (2, 2, 0)], Color: deeppink
Polyomino: [(1, 1, 0), (2, 1, 0), (2, 2, 0), (2, 2, 1), (2, 3, 0)], Color: deeppink
Polyomino: [(1, 2, 0), (2, 2, 0), (2, 3, 0), (2, 3, 1), (2, 4, 0)], Color: deeppink
Polyomino: [(1, 3, 0), (2, 3, 0), (2, 4, 0), (2, 4, 1), (2, 5, 0)], Color: deeppink
Polyomino: [(1, 4, 0), (2, 4, 0), (2, 5, 0), (2, 5, 1), (2, 6, 0)], Color: deeppink
Polyomino: [(1, 5, 0), (2, 5, 0), (2, 6, 0), (2, 6, 1), (2, 7, 0)], Color: deeppink
Polyomino: [(2, 0, 0), (3, 0, 0), (3, 1, 0), (3, 1, 1), (3, 2, 0)], Color: deeppink
Polyomino: [(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (3, 3, 0)], Color: deeppink
Polyomino: [(2, 2, 0), (3, 2, 0), (3, 3, 0), (3, 3, 1), (3, 4, 0)], Color: deeppink
Polyomino: [(2, 3, 0), (3, 3, 0), (3, 4, 0), (3, 4, 1), (3, 5, 0)], Color: deeppink
Polyomino: [(2, 4, 0), (3, 4, 0), (3, 5, 0), (3, 5, 1), (3, 6, 0)], Color: deeppink
Polyomino: [(2, 5, 0), (3, 5, 0), (3, 6, 0), (3, 6, 1), (3, 7, 0)], Color: deeppink
Polyomino: [(3, 0, 0), (4, 0, 0), (4, 1, 0), (4, 1, 1), (4, 2, 0)], Color: deeppink
Polyomino: [(3, 1, 0), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0)], Color: deeppink
Polyomino: [(3, 2, 0), (4, 2, 0), (4, 3, 0), (4, 3, 1), (4, 4, 0)], Color: deeppink
Polyomino: [(3, 3, 0), (4, 3, 0), (4, 4, 0), (4, 4, 1), (4, 5, 0)], Color: deeppink
Polyomino: [(3, 4, 0), (4, 4, 0), (4, 5, 0), (4, 5, 1), (4, 6, 0)], Color: deeppink
Polyomino: [(3, 5, 0), (4, 5, 0), (4, 6, 0), (4, 6, 1), (4, 7, 0)], Color: deeppink
This method is independant of the translation of the polyomino:
sage: q = Polyomino([(0,0,0), (1,0,0)])
sage: list(q.translated((2,2,1)))
[Polyomino: [(0, 0, 0), (1, 0, 0)], Color: gray, Polyomino: [(0, 1, 0), (1, 1, 0)], Color: gray]
sage: q = Polyomino([(34,7,-9), (35,7,-9)])
sage: list(q.translated((2,2,1)))
[Polyomino: [(0, 0, 0), (1, 0, 0)], Color: gray, Polyomino: [(0, 1, 0), (1, 1, 0)], Color: gray]
Inside smaller boxes:
sage: list(p.translated(box=(2,2,3)))
[]
sage: list(p.translated(box=(2,3,2)))
[Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink]
sage: list(p.translated(box=(3,2,2)))
[]
sage: list(p.translated(box=(1,1,1)))
[]
sage: list(p.translated(box=(1,1,-1)))
[]
Return the translated and rotated of self that lies in the box.
INPUT:
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,1,1),(1,2,0)], color='deeppink')
sage: L = list(p.translated_orthogonals(box=(5,8,2)))
sage: len(L)
360
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,2,0),(1,2,1)], color='orange')
sage: L = list(p.translated_orthogonals(box=(5,8,2)))
sage: len(L)
180
sage: p = Polyomino([(0,0,0),(1,0,0),(1,1,0),(1,2,0),(1,2,1)], color='orange')
sage: L = list(p.translated_orthogonals((5,8,2), False))
sage: len(L)
360
Bases: sage.structure.sage_object.SageObject
Tiling solver
Solve the problem of tiling a rectangular box with a certain number of pieces, called polyominoes, where each polyomino must be used exactly once.
INPUT:
EXAMPLES:
By default, rotations are allowed and reflections are not allowed:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: T
Tiling solver of 3 pieces into the box (1, 1, 6)
Rotation allowed: True
Reflection allowed: False
Reusing pieces allowed: False
Solutions are given by an iterator:
sage: it = T.solve()
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 1), (0, 0, 2)], Color: gray
Polyomino: [(0, 0, 3), (0, 0, 4), (0, 0, 5)], Color: gray
Another solution:
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 1), (0, 0, 2), (0, 0, 3)], Color: gray
Polyomino: [(0, 0, 4), (0, 0, 5)], Color: gray
TESTS:
sage: T = TilingSolver([p,q,r], box=(1,1,6), rotation=False, reflection=True)
Traceback (most recent call last):
...
NotImplementedError: When reflection is allowed and rotation is not allowed
Return an animation of evolving solutions.
INPUT:
EXAMPLES:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='cyan')
sage: T = TilingSolver([y], box=(5,10), reusable=True, reflection=True)
sage: a = T.animate()
sage: a
Animation with 10 frames
Include partial solutions (common prefix between two consecutive solutions):
sage: a = T.animate('common_prefix')
sage: a
Animation with 19 frames
Incremental solutions (one piece removed or added at a time):
sage: a = T.animate('incremental') # long time (2s)
sage: a # long time (2s)
Animation with 123 frames
sage: a.show() # optional -- ImageMagick
The show function takes arguments to specify the delay between frames (measured in hundredths of a second, default value 20) and the number of iterations (default value 0, which means to iterate forever). To iterate 4 times with half a second between each frame:
sage: a.show(delay=50, iterations=4) # optional
Limit the number of frames:
sage: a = T.animate('incremental', stop=13) # not tested
sage: a # not tested
Animation with 13 frames
Returns a dictionary mapping coordinates to integers.
OUTPUT:
dict
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: A = T.coord_to_int_dict()
sage: sorted(A.iteritems())
[((0, 0, 0), 3), ((0, 0, 1), 4), ((0, 0, 2), 5), ((0, 0, 3), 6), ((0, 0, 4), 7), ((0, 0, 5), 8)]
Reusable pieces:
sage: p = Polyomino([(0,0), (0,1)])
sage: q = Polyomino([(0,0), (0,1), (1,0), (1,1)])
sage: T = TilingSolver([p,q], box=[3,2], reusable=True)
sage: B = T.coord_to_int_dict()
sage: sorted(B.iteritems())
[((0, 0), 0), ((0, 1), 1), ((1, 0), 2), ((1, 1), 3), ((2, 0), 4), ((2, 1), 5)]
Return an iterator over the row indices of solutions and of partial solutions, i.e. the common prefix of two consecutive solutions.
The purpose is to illustrate the backtracking and construct an animation of the evolution of solutions.
OUPUT:
iterator
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: list(T.dlx_solutions())
[[0, 7, 14], [0, 12, 10], [6, 13, 5], [6, 14, 2], [11, 9, 5], [11, 10, 3]]
sage: list(T.dlx_common_prefix_solutions())
[[0, 7, 14], [0], [0, 12, 10], [], [6, 13, 5], [6], [6, 14, 2], [], [11, 9, 5], [11], [11, 10, 3]]
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='yellow')
sage: T = TilingSolver([y], box=(5,10), reusable=True, reflection=True)
sage: for a in T.dlx_common_prefix_solutions(): a
[46, 83, 149, 26, 179, 44, 81, 162, 132, 101]
[46, 83, 149, 26, 179]
[46, 83, 149, 26, 179, 154, 81, 162, 132, 175]
[46, 83, 149]
[46, 83, 149, 97, 21, 162, 81, 44, 30, 106]
[46]
[46, 157, 149, 136, 179, 44, 81, 162, 132, 101]
[46, 157, 149, 136, 179]
[46, 157, 149, 136, 179, 154, 81, 162, 132, 175]
[]
[82, 119, 40, 97, 20, 87, 8, 45, 30, 107]
[82, 119, 40, 97, 20]
[82, 119, 40, 97, 20, 161, 8, 45, 140, 107]
[82, 119]
[82, 119, 150, 136, 180, 45, 8, 161, 131, 175]
[82, 119, 150]
[82, 119, 150, 171, 20, 87, 8, 45, 30, 107]
[82, 119, 150, 171, 20]
[82, 119, 150, 171, 20, 161, 8, 45, 140, 107]
Return an iterator over the row indices of the incremental solutions.
Between two incremental solution, either one piece is added or one piece is removed.
The purpose is to illustrate the backtracking and construct an animation of the evolution of solutions.
OUPUT:
iterator
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: list(T.dlx_solutions())
[[0, 7, 14], [0, 12, 10], [6, 13, 5], [6, 14, 2], [11, 9, 5], [11, 10, 3]]
sage: list(T.dlx_incremental_solutions())
[[0, 7, 14], [0, 7], [0], [0, 12], [0, 12, 10], [0, 12], [0], [], [6], [6, 13], [6, 13, 5], [6, 13], [6], [6, 14], [6, 14, 2], [6, 14], [6], [], [11], [11, 9], [11, 9, 5], [11, 9], [11], [11, 10], [11, 10, 3]]
sage: y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='yellow')
sage: T = TilingSolver([y], box=(5,10), reusable=True, reflection=True)
sage: for a in T.dlx_solutions(): a
[46, 83, 149, 26, 179, 44, 81, 162, 132, 101]
[46, 83, 149, 26, 179, 154, 81, 162, 132, 175]
[46, 83, 149, 97, 21, 162, 81, 44, 30, 106]
[46, 157, 149, 136, 179, 44, 81, 162, 132, 101]
[46, 157, 149, 136, 179, 154, 81, 162, 132, 175]
[82, 119, 40, 97, 20, 87, 8, 45, 30, 107]
[82, 119, 40, 97, 20, 161, 8, 45, 140, 107]
[82, 119, 150, 136, 180, 45, 8, 161, 131, 175]
[82, 119, 150, 171, 20, 87, 8, 45, 30, 107]
[82, 119, 150, 171, 20, 161, 8, 45, 140, 107]
sage: len(list(T.dlx_incremental_solutions()))
123
Return an iterator over the row indices of the solutions.
OUPUT:
iterator
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: list(T.dlx_solutions())
[[0, 7, 14], [0, 12, 10], [6, 13, 5], [6, 14, 2], [11, 9, 5], [11, 10, 3]]
Return the sage DLX solver of that 3d tiling problem.
OUTPUT:
DLX Solver
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: x = T.dlx_solver()
sage: x
<sage.combinat.matrices.dancing_links.dancing_linksWrapper object at ...>
Returns a dictionary mapping integers to coordinates.
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: B = T.int_to_coord_dict()
sage: sorted(B.iteritems())
[(3, (0, 0, 0)), (4, (0, 0, 1)), (5, (0, 0, 2)), (6, (0, 0, 3)), (7, (0, 0, 4)), (8, (0, 0, 5))]
Reusable pieces:
sage: from sage.combinat.tiling import Polyomino, TilingSolver
sage: p = Polyomino([(0,0), (0,1)])
sage: q = Polyomino([(0,0), (0,1), (1,0), (1,1)])
sage: T = TilingSolver([p,q], box=[3,2], reusable=True)
sage: B = T.int_to_coord_dict()
sage: sorted(B.iteritems())
[(0, (0, 0)), (1, (0, 1)), (2, (1, 0)), (3, (1, 1)), (4, (2, 0)), (5, (2, 1))]
TESTS:
The methods int_to_coord_dict and coord_to_int_dict returns dictionary that are inverse of each other:
sage: A = T.coord_to_int_dict()
sage: B = T.int_to_coord_dict()
sage: all(A[B[i]] == i for i in B)
True
sage: all(B[A[i]] == i for i in A)
True
Return whether the volume of the box is equal to sum of the volume of the polyominoes and the number of rows sent to the DLX solver is larger than zero.
If these conditions are not verified, then the problem is not suitable in the sense that there are no solution.
Note
The DLX solver throws a Segmentation Fault when the number of rows is zero:
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search() # not tested
BOOM !!!
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: T.is_suitable()
True
sage: T = TilingSolver([p,q,r], box=(1,1,7))
sage: T.is_suitable()
False
Return the number of rows necessary by each piece.
OUPUT:
list
EXAMPLES:
sage: from sage.games.quantumino import QuantuminoSolver
sage: q = QuantuminoSolver(0)
sage: T = q.tiling_solver()
sage: T.nrows_per_piece() # long time (10s)
[360, 360, 360, 360, 360, 180, 180, 672, 672, 360, 360, 180, 180, 360, 360, 180]
Return the number of distinct solutions.
OUPUT:
integer
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0)])
sage: q = Polyomino([(0,0), (0,1)])
sage: r = Polyomino([(0,0), (0,1), (0,2)])
sage: T = TilingSolver([p,q,r], box=(1,6))
sage: T.number_of_solutions()
6
sage: T = TilingSolver([p,q,r], box=(1,7))
sage: T.number_of_solutions()
0
Return the list of pieces.
OUTPUT:
list of 3d polyominoes
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: for p in T._pieces: p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 0), (0, 0, 1)], Color: gray
Polyomino: [(0, 0, 0), (0, 0, 1), (0, 0, 2)], Color: gray
Creation of the rows
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: rows = T.rows()
sage: for row in rows: row
[0, 3]
[0, 4]
[0, 5]
[0, 6]
[0, 7]
[0, 8]
[1, 3, 4]
[1, 4, 5]
[1, 5, 6]
[1, 6, 7]
[1, 8, 7]
[2, 3, 4, 5]
[2, 4, 5, 6]
[2, 5, 6, 7]
[2, 8, 6, 7]
Returns an iterator of list of 3d polyominoes that are an exact cover of the box.
INPUT:
OUTPUT:
iterator of list of 3d polyominoes
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: it = T.solve()
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 1), (0, 0, 2)], Color: gray
Polyomino: [(0, 0, 3), (0, 0, 4), (0, 0, 5)], Color: gray
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 1), (0, 0, 2), (0, 0, 3)], Color: gray
Polyomino: [(0, 0, 4), (0, 0, 5)], Color: gray
sage: for p in it.next(): p
Polyomino: [(0, 0, 0), (0, 0, 1)], Color: gray
Polyomino: [(0, 0, 2), (0, 0, 3), (0, 0, 4)], Color: gray
Polyomino: [(0, 0, 5)], Color: gray
Including the partial solutions:
sage: it = T.solve(partial='common_prefix')
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 1), (0, 0, 2)], Color: gray
Polyomino: [(0, 0, 3), (0, 0, 4), (0, 0, 5)], Color: gray
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: gray
Polyomino: [(0, 0, 1), (0, 0, 2), (0, 0, 3)], Color: gray
Polyomino: [(0, 0, 4), (0, 0, 5)], Color: gray
sage: for p in it.next(): p
sage: for p in it.next(): p
Polyomino: [(0, 0, 0), (0, 0, 1)], Color: gray
Polyomino: [(0, 0, 2), (0, 0, 3), (0, 0, 4)], Color: gray
Polyomino: [(0, 0, 5)], Color: gray
Colors are preserved when the polyomino can be reused:
sage: p = Polyomino([(0,0,0)], color='yellow')
sage: q = Polyomino([(0,0,0), (0,0,1)], color='yellow')
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)], color='yellow')
sage: T = TilingSolver([p,q,r], box=(1,1,6), reusable=True)
sage: it = T.solve()
sage: for p in it.next(): p
Polyomino: [(0, 0, 0)], Color: yellow
Polyomino: [(0, 0, 1)], Color: yellow
Polyomino: [(0, 0, 2)], Color: yellow
Polyomino: [(0, 0, 3)], Color: yellow
Polyomino: [(0, 0, 4)], Color: yellow
Polyomino: [(0, 0, 5)], Color: yellow
TESTS:
sage: T = TilingSolver([p,q,r], box=(1,1,7))
sage: T.solve().next()
Traceback (most recent call last):
...
StopIteration
Returns an iterator over all the non negative integer coordinates contained in the box.
EXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino
sage: p = Polyomino([(0,0,0)])
sage: q = Polyomino([(0,0,0), (0,0,1)])
sage: r = Polyomino([(0,0,0), (0,0,1), (0,0,2)])
sage: T = TilingSolver([p,q,r], box=(1,1,6))
sage: list(T.space())
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 0, 5)]
Return the list of orthogonal transformation matrices in the
-dimensional vector space.
INPUT:
OUTPUT:
list of matrices
EXAMPLES:
sage: from sage.combinat.tiling import orthogonal_transformation
sage: orthogonal_transformation(2)
[
[-1 0] [ 0 -1] [ 0 1] [1 0]
[ 0 -1], [ 1 0], [-1 0], [0 1]
]
sage: orthogonal_transformation(2, orientation_preserving=False)
[
[-1 0] [-1 0] [ 0 -1] [ 0 -1] [ 0 1] [0 1] [ 1 0] [1 0]
[ 0 -1], [ 0 1], [-1 0], [ 1 0], [-1 0], [1 0], [ 0 -1], [0 1]
]
sage: orthogonal_transformation(3)
[
[-1 0 0] [-1 0 0] [-1 0 0] [-1 0 0] [ 0 -1 0] [ 0 -1 0]
[ 0 -1 0] [ 0 0 -1] [ 0 0 1] [ 0 1 0] [-1 0 0] [ 0 0 -1]
[ 0 0 1], [ 0 -1 0], [ 0 1 0], [ 0 0 -1], [ 0 0 -1], [ 1 0 0],
[ 0 -1 0] [ 0 -1 0] [ 0 0 -1] [ 0 0 -1] [ 0 0 -1] [ 0 0 -1]
[ 0 0 1] [ 1 0 0] [-1 0 0] [ 0 -1 0] [ 0 1 0] [ 1 0 0]
[-1 0 0], [ 0 0 1], [ 0 1 0], [-1 0 0], [ 1 0 0], [ 0 -1 0],
[ 0 0 1] [ 0 0 1] [ 0 0 1] [0 0 1] [ 0 1 0] [ 0 1 0]
[-1 0 0] [ 0 -1 0] [ 0 1 0] [1 0 0] [-1 0 0] [ 0 0 -1]
[ 0 -1 0], [ 1 0 0], [-1 0 0], [0 1 0], [ 0 0 1], [-1 0 0],
[0 1 0] [ 0 1 0] [ 1 0 0] [ 1 0 0] [ 1 0 0] [1 0 0]
[0 0 1] [ 1 0 0] [ 0 -1 0] [ 0 0 -1] [ 0 0 1] [0 1 0]
[1 0 0], [ 0 0 -1], [ 0 0 -1], [ 0 1 0], [ 0 -1 0], [0 0 1]
]
TESTS:
sage: orthogonal_transformation(1)
[[1]]
sage: orthogonal_transformation(0)
Traceback (most recent call last):
...
ValueError: ['B', 0] is not a valid cartan type