Tiling Solver¶
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:
sage.combinat.tiling.Polyomino
class, to represent polyominoes in arbitrary dimension. The goal of this class is to return all the rotated, reflected and/or translated copies of a polyomino that are contained in a certain box.sage.combinat.tiling.TilingSolver
class, to solve the general problem of tiling a rectangular \(n\)-dimensional box with a set of \(n\)-dimensional polyominoes. One can specify if rotations and reflections are allowed or not and if pieces can be reused or not. This class convert the tiling data into rows of a matrix that are passed to the DLX solver. It also allows to compute the number of solutions.
AUTHOR:
- Sebastien Labbe, June 2011, initial version
- Sebastien Labbe, July 2015, count solutions up to rotations
EXAMPLES:
2d Easy Example¶
Here is a 2d example. Let us try to fill the \(3 \times 2\) rectangle with a \(1 \times 2\) rectangle and a \(2 \times 2\) 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: next(it)
[Polyomino: [(0, 0), (0, 1), (1, 0), (1, 1)], Color: gray, Polyomino: [(2, 0), (2, 1)], Color: gray]
sage: next(it)
[Polyomino: [(1, 0), (1, 1), (2, 0), (2, 1)], Color: gray, Polyomino: [(0, 0), (0, 1)], Color: gray]
sage: next(it)
Traceback (most recent call last):
...
StopIteration
sage: T.number_of_solutions()
2
1d Easy Example¶
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: next(it)
[Polyomino: [(0)], Color: gray, Polyomino: [(1), (2)], Color: gray, Polyomino: [(3), (4), (5)], Color: gray]
sage: next(it)
[Polyomino: [(0)], Color: gray, Polyomino: [(1), (2), (3)], Color: gray, Polyomino: [(4), (5)], Color: gray]
sage: T.number_of_solutions()
6
2d Puzzle allowing reflections¶
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 = next(T.solve()) # long time (7s)
sage: G = sum([piece.show2d() for piece in solution], Graphics()) # long time (<1s)
sage: G.show(aspect_ratio=1, axes=False) # long time (2s)
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
3d Puzzle¶
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 = next(T.solve()) # long time (8s)
sage: G = sum([p.show3d(size=0.85) for p in solution], Graphics()) # long time (<1s)
sage: G.show(aspect_ratio=1, viewer='tachyon') # long time (2s)
Let us compute the number of solutions:
sage: T.number_of_solutions() # long time (3s)
328
Donald Knuth example : the Y pentamino¶
Donald Knuth [Knuth1] considered the problem of packing 45 Y pentaminoes into a \(15 \times 15\) 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 = next(T.solve())
sage: G = sum([p.show2d() for p in solution], Graphics())
sage: G.show(aspect_ratio=1) # long time (2s)
sage: T = TilingSolver([y], box=(15,15), reusable=True, reflection=True)
sage: T.number_of_solutions() # not tested
212
Animation of Donald Knuth’s dancing links¶
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 # optional -- ImageMagick
sage: a # long time # optional -- ImageMagick
Animation with 40 frames
Incremental animation of the solutions (one piece is removed/added at a time):
sage: a = T.animate('incremental', stop=40) # long time # optional -- ImageMagick
sage: a # long time # optional -- ImageMagick
Animation with 40 frames
sage: a.show(delay=50, iterations=1) # long time # optional -- ImageMagick
5d Easy Example¶
Here is a 5d example. Let us try to fill the \(2 \times 2 \times 2 \times 2 \times 2\) rectangle with reusable \(1 \times 1 \times 1 \times 1 \times 1\) 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. |
-
class
sage.combinat.tiling.
Polyomino
(coords, color='gray')¶ 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:
coords
- iterable of tuplecolor
- string (optional, default:'gray'
), the color
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
-
boundary
()¶ Return the boundary of a 2d polyomino.
INPUT:
self
- a 2d polyomino
OUTPUT:
- list of edges (an edge is a pair of adjacent 2d coordinates)
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))]
-
bounding_box
()¶ 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]]
-
canonical
()¶ Returns the translated copy of self having minimal and nonnegative 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
-
canonical_isometric_copies
(orientation_preserving=True, mod_box_isometries=False)¶ Return the set of image of self under isometries of the \(n\)-cube where the coordinates are all nonnegative and minimal.
INPUT:
orientation_preserving
– bool (optional, default:True
), If True, the group of isometries of the \(n\)-cube is restricted to those that preserve the orientation, i.e. of determinant 1.mod_box_isometries
– bool (default:False
), whether to quotient the group of isometries of the \(n\)-cube by the subgroup of isometries of the \(a_1\times a_2\cdots \times a_n\) rectangular box where are the \(a_i\) are assumed to be distinct.
OUTPUT:
set of PolyominoEXAMPLES:
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: s = p.canonical_isometric_copies() sage: len(s) 12
With the non orientation-preserving:
sage: s = p.canonical_isometric_copies(orientation_preserving=False) sage: len(s) 24
Modulo rotation by angle 180 degrees:
sage: s = p.canonical_isometric_copies(mod_box_isometries=True) sage: len(s) 3
TESTS:
sage: from sage.games.quantumino import pentaminos sage: [len(p.canonical_isometric_copies((5,8,2), mod_box_isometries=False)) for p in pentaminos] [24, 24, 24, 24, 24, 24, 12, 12, 24, 24, 24, 24, 12, 12, 24, 24, 12] sage: [len(p.canonical_isometric_copies((5,8,2), mod_box_isometries=True)) for p in pentaminos] [6, 6, 6, 6, 6, 6, 3, 3, 6, 6, 6, 6, 3, 3, 6, 6, 3]
-
canonical_orthogonals
(*args, **kwds)¶ Deprecated: Use
canonical_isometric_copies()
instead. See trac ticket #19107 for details.
-
center
()¶ 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)
-
color
()¶ 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'
-
isometric_copies
(box, orientation_preserving=True, mod_box_isometries=False)¶ Return the translated and isometric images of self that lies in the box.
INPUT:
box
– tuple of integers, size of the boxorientation_preserving
– bool (optional, default:True
), If True, the group of isometries of the \(n\)-cube is restricted to those that preserve the orientation, i.e. of determinant 1.mod_box_isometries
– bool (default:False
), whether to quotient the group of isometries of the \(n\)-cube by the subgroup of isometries of the \(a_1\times a_2\cdots \times a_n\) rectangular box where are the \(a_i\) are assumed to be distinct.
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.isometric_copies(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.isometric_copies(box=(5,8,2))) sage: len(L) 180 sage: L = list(p.isometric_copies((5,8,2), False)) sage: len(L) 360 sage: L = list(p.isometric_copies((5,8,2), mod_box_isometries=True)) sage: len(L) 45
-
neighbor_edges
()¶ Return an iterator over the pairs of neighbor coordinates of the polyomino.
Two points \(P\) and \(Q\) are neighbor if \(P - Q\) has one coordinate equal to \(+1\) or \(-1\) 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)]
-
show2d
(size=0.7, color='black', thickness=1)¶ Returns a 2d Graphic object representing the polyomino.
INPUT:
self
- a polyomino of dimension 2size
- number (optional, default:0.7
), the size of each square.color
- color (optional, default:'black'
), color of the boundary line.thickness
- number (optional, default:1
), how thick the boundary line is.
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) Graphics object consisting of 17 graphics primitives
-
show3d
(size=1)¶ Returns a 3d Graphic object representing the polyomino.
INPUT:
self
- a polyomino of dimension 3size
- number (optional, default:1
), the size of each1 \times 1 \times 1
cube. This does a homothety with respect to the center 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.show3d() # long time (2s) Graphics3d Object
-
translated
(*args, **kwds)¶ Deprecated: Use
translated_copies()
instead. See trac ticket #19107 for details.
-
translated_copies
(box)¶ Returns an iterator over the translated images of self inside a box.
INPUT:
box
– tuple of integers, size of the box
OUTPUT:
iterator of 3d polyominoesEXAMPLES:
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_copies(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_copies((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_copies((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_copies(box=(2,2,3))) [] sage: list(p.translated_copies(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_copies(box=(3,2,2))) [] sage: list(p.translated_copies(box=(1,1,1))) [] sage: list(p.translated_copies(box=(1,1,-1))) []
-
translated_orthogonals
(*args, **kwds)¶ Deprecated: Use
isometric_copies()
instead. See trac ticket #19107 for details.
-
class
sage.combinat.tiling.
TilingSolver
(pieces, box, rotation=True, reflection=False, reusable=False)¶ 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:
pieces
- iterable of Polyominoesbox
- tuple, size of the boxrotation
- bool (optional, default:True
), whether to allow rotationsreflection
- bool (optional, default:False
), whether to allow reflectionsreusable
- bool (optional, default:False
), whether to allow the pieces to be reused
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 next(it): 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 next(it): 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
-
animate
(partial=None, stop=None, size=0.75, axes=False)¶ Return an animation of evolving solutions.
INPUT:
partial
- string (optional, default:None
), whether to include partial (incomplete) solutions. It can be one of the following:None
- include only complete solutions'common_prefix'
- common prefix between two consecutive solutions'incremental'
- one piece change at a time
stop
- integer (optional, default:None
), number of framessize
- number (optional, default:0.75
), the size of each1 \times 1
square. This does a homothety with respect to the center of each polyomino.axes
- bool (optional, default:False
), whether the x and y axes are shown.
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 # optional -- ImageMagick Animation with 10 frames
Include partial solutions (common prefix between two consecutive solutions):
sage: a = T.animate('common_prefix') sage: a # optional -- ImageMagick 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) # optional -- ImageMagick 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 -- ImageMagick
Limit the number of frames:
sage: a = T.animate('incremental', stop=13) # not tested sage: a # not tested Animation with 13 frames
-
coord_to_int_dict
()¶ Returns a dictionary mapping coordinates to integers.
OUTPUT:
dictEXAMPLES:
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)]
-
dlx_solver
()¶ Return the sage DLX solver of that 3d tiling problem.
OUTPUT:
DLX SolverEXAMPLES:
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.dlx_solver() Dancing links solver for 9 columns and 15 rows
-
int_to_coord_dict
()¶ 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
andcoord_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
-
is_suitable
()¶ 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.
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
-
nrows_per_piece
()¶ Return the number of rows necessary by each piece.
OUTPUT:
listEXAMPLES:
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]
-
number_of_solutions
()¶ Return the number of distinct solutions.
OUTPUT:
integerEXAMPLES:
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
-
pieces
()¶ Return the list of pieces.
OUTPUT:
list of 3d polyominoesEXAMPLES:
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
-
row_to_polyomino
(row_number)¶ Return a polyomino associated to a row.
INPUT:
row_number
– integer, the i-th row
OUTPUT:
polyominoEXAMPLES:
sage: from sage.combinat.tiling import TilingSolver, Polyomino sage: a = Polyomino([(0,0,0), (0,0,1), (1,0,0)], color='blue') sage: b = Polyomino([(0,0,0), (1,0,0), (0,1,0)], color='red') sage: T = TilingSolver([a,b], box=(2,1,3)) sage: len(T.rows()) 16
sage: T.row_to_polyomino(7) Polyomino: [(0, 0, 1), (0, 0, 2), (1, 0, 1)], Color: blue
sage: T.row_to_polyomino(13) Polyomino: [(0, 0, 1), (0, 0, 2), (1, 0, 1)], Color: red
-
rows
()¶ 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, 7, 8] [2, 3, 4, 5] [2, 4, 5, 6] [2, 5, 6, 7] [2, 6, 7, 8]
-
rows_for_piece
(i, mod_box_isometries=False)¶ Return the rows for the i-th piece.
INPUT:
i
– integer, the i-th piecemod_box_isometries
– bool (default:False
), whether to consider only rows for positions up to the action of the quotient the group of isometries of the \(n\)-cube by the subgroup of isometries of the \(a_1\times a_2\cdots \times a_n\) rectangular box where are the \(a_i\) are assumed to be distinct.
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.rows_for_piece(0) [[0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8]] sage: T.rows_for_piece(1) [[1, 3, 4], [1, 4, 5], [1, 5, 6], [1, 6, 7], [1, 7, 8]] sage: T.rows_for_piece(2) [[2, 3, 4, 5], [2, 4, 5, 6], [2, 5, 6, 7], [2, 6, 7, 8]]
Less rows when using
mod_box_isometries=True
:sage: a = Polyomino([(0,0,0), (0,0,1), (1,0,0)]) sage: b = Polyomino([(0,0,0), (1,0,0), (0,1,0)]) sage: T = TilingSolver([a,b], box=(2,1,3)) sage: T.rows_for_piece(0) [[0, 3, 5, 6], [0, 4, 6, 7], [0, 2, 5, 6], [0, 3, 6, 7], [0, 2, 3, 6], [0, 3, 4, 7], [0, 2, 3, 5], [0, 3, 4, 6]] sage: T.rows_for_piece(0, mod_box_isometries=True) [[0, 2, 5, 6], [0, 3, 6, 7]] sage: T.rows_for_piece(1, mod_box_isometries=True) [[1, 2, 5, 6], [1, 3, 6, 7]]
-
solve
(partial=None)¶ Returns an iterator of list of 3d polyominoes that are an exact cover of the box.
INPUT:
partial
- string (optional, default:None
), whether to include partial (incomplete) solutions. It can be one of the following:None
- include only complete solution'common_prefix'
- common prefix between two consecutive solutions'incremental'
- one piece change at a time
OUTPUT:
iterator of list of 3d polyominoesEXAMPLES:
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 next(it): 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 next(it): 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 next(it): 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 next(it): 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 next(it): p Polyomino: [(0, 0, 0)], Color: gray sage: for p in next(it): 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 next(it): p sage: for p in next(it): 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 next(it): 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: next(T.solve()) Traceback (most recent call last): ... StopIteration
-
space
()¶ 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)]
-
starting_rows
()¶ Return the starting rows for each piece.
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.starting_rows() [0, 6, 11, 15]
-
sage.combinat.tiling.
ncube_isometry_group
(n, orientation_preserving=True)¶ Return the isometry group of the \(n\)-cube as a list of matrices.
INPUT:
n
– positive integer, dimension of the spaceorientation_preserving
– bool (optional, default:True
), whether the orientation is preserved
OUTPUT:
list of matricesEXAMPLES:
sage: from sage.combinat.tiling import ncube_isometry_group sage: ncube_isometry_group(2) [ [1 0] [ 0 1] [-1 0] [ 0 -1] [0 1], [-1 0], [ 0 -1], [ 1 0] ] sage: ncube_isometry_group(2, orientation_preserving=False) [ [1 0] [ 0 -1] [ 1 0] [ 0 1] [0 1] [-1 0] [ 0 -1] [-1 0] [0 1], [-1 0], [ 0 -1], [-1 0], [1 0], [ 0 -1], [ 1 0], [ 0 1] ]
There are 24 orientation preserving isometries of the 3-cube:
sage: ncube_isometry_group(3) [ [1 0 0] [ 1 0 0] [-1 0 0] [-1 0 0] [0 0 1] [ 0 0 -1] [0 1 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0] [1 0 0] [ 1 0 0] [0 0 1], [ 0 0 -1], [ 0 0 -1], [ 0 0 1], [0 1 0], [ 0 -1 0], <BLANKLINE> [ 0 0 -1] [ 0 0 1] [0 1 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0] [-1 0 0] [-1 0 0] [0 0 1] [ 0 0 -1] [ 0 0 -1] [ 0 0 1] [ 0 1 0], [ 0 -1 0], [1 0 0], [ 1 0 0], [-1 0 0], [-1 0 0], <BLANKLINE> [ 0 1 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0] [ 1 0 0] [ 1 0 0] [ 1 0 0] [ 1 0 0] [-1 0 0] [-1 0 0] [ 0 0 -1] [ 0 0 1] [ 0 0 -1], [ 0 0 1], [ 0 0 1], [ 0 0 -1], [ 0 1 0], [ 0 -1 0], <BLANKLINE> [-1 0 0] [-1 0 0] [ 0 0 -1] [ 0 0 1] [ 0 0 1] [ 0 0 -1] [ 0 0 1] [ 0 0 -1] [ 0 1 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0] [ 0 1 0], [ 0 -1 0], [ 1 0 0], [ 1 0 0], [-1 0 0], [-1 0 0] ]
TESTS:
sage: ncube_isometry_group(1) [[1]] sage: ncube_isometry_group(0) Traceback (most recent call last): ... ValueError: ['B', 0] is not a valid Cartan type
Is deprecated:
sage: from sage.combinat.tiling import orthogonal_transformation sage: L = orthogonal_transformation(2) doctest:...: DeprecationWarning: orthogonal_transformation is deprecated. Please use sage.combinat.tiling.ncube_isometry_group instead. See http://trac.sagemath.org/19107 for details.
-
sage.combinat.tiling.
ncube_isometry_group_cosets
(n, orientation_preserving=True)¶ Return the quotient of the isometry group of the \(n\)-cube by the the isometry group of the rectangular parallelepiped.
INPUT:
n
– positive integer, dimension of the spaceorientation_preserving
– bool (optional, default:True
), whether the orientation is preserved
OUTPUT:
list of cosets, each coset being a sorted list of matricesEXAMPLES:
sage: from sage.combinat.tiling import ncube_isometry_group_cosets sage: sorted(ncube_isometry_group_cosets(2)) [[ [-1 0] [1 0] [ 0 -1], [0 1] ], [ [ 0 -1] [ 0 1] [ 1 0], [-1 0] ]] sage: sorted(ncube_isometry_group_cosets(2, False)) [[ [-1 0] [-1 0] [ 1 0] [1 0] [ 0 -1], [ 0 1], [ 0 -1], [0 1] ], [ [ 0 -1] [ 0 -1] [ 0 1] [0 1] [-1 0], [ 1 0], [-1 0], [1 0] ]]
sage: sorted(ncube_isometry_group_cosets(3)) [[ [-1 0 0] [-1 0 0] [ 1 0 0] [1 0 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0] [0 1 0] [ 0 0 1], [ 0 0 -1], [ 0 0 -1], [0 0 1] ], [ [-1 0 0] [-1 0 0] [ 1 0 0] [ 1 0 0] [ 0 0 -1] [ 0 0 1] [ 0 0 -1] [ 0 0 1] [ 0 -1 0], [ 0 1 0], [ 0 1 0], [ 0 -1 0] ], [ [ 0 -1 0] [ 0 -1 0] [ 0 1 0] [ 0 1 0] [-1 0 0] [ 1 0 0] [-1 0 0] [ 1 0 0] [ 0 0 -1], [ 0 0 1], [ 0 0 1], [ 0 0 -1] ], [ [ 0 -1 0] [ 0 -1 0] [ 0 1 0] [0 1 0] [ 0 0 -1] [ 0 0 1] [ 0 0 -1] [0 0 1] [ 1 0 0], [-1 0 0], [-1 0 0], [1 0 0] ], [ [ 0 0 -1] [ 0 0 -1] [ 0 0 1] [0 0 1] [-1 0 0] [ 1 0 0] [-1 0 0] [1 0 0] [ 0 1 0], [ 0 -1 0], [ 0 -1 0], [0 1 0] ], [ [ 0 0 -1] [ 0 0 -1] [ 0 0 1] [ 0 0 1] [ 0 -1 0] [ 0 1 0] [ 0 -1 0] [ 0 1 0] [-1 0 0], [ 1 0 0], [ 1 0 0], [-1 0 0] ]]
TESTS:
sage: cosets = ncube_isometry_group_cosets(3, False) sage: len(cosets) 6 sage: map(len, cosets) [8, 8, 8, 8, 8, 8] sage: type(cosets[0][0]) <type 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'>