Tiling Solver#

Tiling a n-dimensional polyomino with n-dimensional polyominoes.

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 problem of tiling a \(n\)-dimensional polyomino 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.

This uses dancing links code which is in Sage. Dancing links were originally introduced by Donald Knuth in 2000 [Knuth1]. 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.

AUTHOR:

  • Sébastien Labbé, June 2011, initial version

  • Sébastien Labbé, July 2015, count solutions up to rotations

  • Sébastien Labbé, April 2017, tiling a polyomino, not only a rectangular box

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

Scott’s pentamino problem#

As mentioned in the introduction of [Knuth1], Scott’s pentamino problem consists in tiling a chessboard leaving the center four squares vacant with the 12 distinct pentaminoes.

The 12 pentaminoes:

sage: from sage.combinat.tiling import Polyomino
sage: I = Polyomino([(0,0),(1,0),(2,0),(3,0),(4,0)], color='brown')
sage: N = Polyomino([(1,0),(1,1),(1,2),(0,2),(0,3)], color='yellow')
sage: L = Polyomino([(0,0),(1,0),(0,1),(0,2),(0,3)], color='magenta')
sage: U = Polyomino([(0,0),(1,0),(0,1),(0,2),(1,2)], color='violet')
sage: X = Polyomino([(1,0),(0,1),(1,1),(1,2),(2,1)], color='pink')
sage: W = Polyomino([(2,0),(2,1),(1,1),(1,2),(0,2)], color='green')
sage: P = Polyomino([(1,0),(2,0),(0,1),(1,1),(2,1)], color='orange')
sage: F = Polyomino([(1,0),(1,1),(0,1),(2,1),(2,2)], color='gray')
sage: Z = Polyomino([(0,0),(1,0),(1,1),(1,2),(2,2)], color='yellow')
sage: T = Polyomino([(0,0),(0,1),(1,1),(2,1),(0,2)], color='red')
sage: Y = Polyomino([(0,0),(1,0),(2,0),(3,0),(2,1)], color='green')
sage: V = Polyomino([(0,0),(0,1),(0,2),(1,0),(2,0)], color='blue')

A \(8 \times 8\) chessboard leaving the center four squares vacant:

sage: import itertools
sage: s = set(itertools.product(range(8), repeat=2))
sage: s.difference_update([(3,3), (3,4), (4,3), (4,4)])
sage: chessboard = Polyomino(s)
sage: len(chessboard)
60

This problem is represented by a matrix made of 1568 rows and 72 columns. It has 65 different solutions up to isometries:

sage: from sage.combinat.tiling import TilingSolver
sage: T = TilingSolver([I,N,L,U,X,W,P,F,Z,T,Y,V], box=chessboard, reflection=True)
sage: T
Tiling solver of 12 pieces into a box of size 60
Rotation allowed: True
Reflection allowed: True
Reusing pieces allowed: False
sage: len(T.rows())                # long time
1568
sage: T.number_of_solutions()      # long time
520
sage: 520 / 8
65

Showing one solution:

sage: solution = next(T.solve())                                  # long time
sage: G = sum([piece.show2d() for piece in solution], Graphics()) # long time       # optional - sage.plot
sage: G.show(aspect_ratio=1, axes=False)                          # long time       # optional - sage.plot

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 for tiling a \(8 \times 8\) rectangular box:

sage: T = TilingSolver(L, box=(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, box=(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) # optional - sage.plot
sage: G.show(aspect_ratio=1, axes=False)                          # long time (2s)  # optional - sage.plot

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, box=(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())                           # optional - sage.plot
sage: G.show(aspect_ratio=1)                       # long time (2s)                 # optional - sage.plot

sage: T = TilingSolver([y], box=(15,15), reusable=True, reflection=True)
sage: T.number_of_solutions()                      # not tested
1696

Up to the symmetries of the square, there are 212 distinct solutions:

sage: 1696 // 8
212

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,3)

Knuth, Donald (2000). “Dancing links”. arXiv cs/0011047.

class sage.combinat.tiling.Polyomino(coords, color='gray', dimension=None)#

Bases: SageObject

A polyomino in \(\ZZ^d\).

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 does not make this assumption.

INPUT:

  • coords – iterable of integer coordinates in \(\ZZ^d\)

  • color – string (default: 'gray'), color for display

  • dimension – integer (default: None), dimension of the space, if None, it is guessed from the coords if coords is non empty

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: sorted(p.boundary())
[((-0.5, -0.5), (-0.5, 0.5)), ((-0.5, -0.5), (0.5, -0.5)), ((-0.5, 0.5), (-0.5, 1.5)), ((-0.5, 1.5), (0.5, 1.5)), ((0.5, -0.5), (1.5, -0.5)), ((0.5, 1.5), (1.5, 1.5)), ((1.5, -0.5), (1.5, 0.5)), ((1.5, 0.5), (1.5, 1.5))]
sage: len(_)
8
sage: p = Polyomino([(5,5)])
sage: sorted(p.boundary())
[((4.5, 4.5), (4.5, 5.5)), ((4.5, 4.5), (5.5, 4.5)), ((4.5, 5.5), (5.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()#

Return 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
canonical_isometric_copies(orientation_preserving=True, mod_box_isometries=False)#

Return the list 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 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: 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
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(color=None)#

Return or change the color of the polyomino.

INPUT:

  • color – string, RBG tuple or None (default: None), if None, it returns the current color

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'
frozenset()#

Return the elements of \(\ZZ^d\) in the polyomino as a frozenset.

EXAMPLES:

sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='red')
sage: p.frozenset()
frozenset({(0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1)})
intersection(other)#

Return the intersection of self and other.

INPUT:

  • other - a polyomino

OUTPUT:

polyomino

EXAMPLES:

sage: from sage.combinat.tiling import Polyomino
sage: a = Polyomino([(0,0)])
sage: b = Polyomino([(0,0), (0,1), (1,1), (2,1)])
sage: a.intersection(b)
Polyomino: [(0, 0)], Color: gray
sage: a.intersection(b+(1,1))
Polyomino: [], Color: gray
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 – Polyomino or tuple of integers (size of a box)

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

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

sage: p = Polyomino([(0,0), (1,0), (0,1)])
sage: b = Polyomino([(0,0), (1,0), (2,0), (0,1), (1,1), (0,2)])
sage: sorted(p.isometric_copies(b), key=lambda p: p.sorted_list())
[Polyomino: [(0, 0), (0, 1), (1, 0)], Color: gray,
 Polyomino: [(0, 0), (0, 1), (1, 1)], Color: gray,
 Polyomino: [(0, 0), (1, 0), (1, 1)], Color: gray,
 Polyomino: [(0, 1), (0, 2), (1, 1)], Color: gray,
 Polyomino: [(0, 1), (1, 0), (1, 1)], Color: gray,
 Polyomino: [(1, 0), (1, 1), (2, 0)], Color: gray]
isometric_copies_intersection(box, orientation_preserving=True)#

Return the set of non empty intersections of isometric images of self with a polyomino.

INPUT:

  • box – Polyomino or tuple of integers (size of a box)

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

EXAMPLES:

sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0),(1,0)], color='deeppink')
sage: sorted(sorted(a.frozenset()) for a in p.isometric_copies_intersection(box=(2,3)))
[[(0, 0)],
 [(0, 0), (0, 1)],
 [(0, 0), (1, 0)],
 [(0, 1)],
 [(0, 1), (0, 2)],
 [(0, 1), (1, 1)],
 [(0, 2)],
 [(0, 2), (1, 2)],
 [(1, 0)],
 [(1, 0), (1, 1)],
 [(1, 1)],
 [(1, 1), (1, 2)],
 [(1, 2)]]
neighbor_edges()#

Return an iterator over the pairs of neighbor coordinates inside of the polyomino.

Two points \(P\) and \(Q\) in the polyomino 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: [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)]
self_surrounding(radius, remove_incomplete_copies=True, ncpus=None)#

Return a list of isometric copies of self surrounding it with an annulus of given radius.

INPUT:

  • self - a polyomino of dimension 2

  • radius - integer

  • remove_incomplete_copies – bool (default: True), whether to keep only complete copies of self in the output

  • ncpus – integer (default: None), maximal number of subprocesses to use at the same time. If None, it detects the number of effective CPUs in the system using sage.parallel.ncpus.ncpus(). If ncpus=1, the first solution is searched serially.

OUTPUT:

list of polyominoes

EXAMPLES:

sage: from sage.combinat.tiling import Polyomino
sage: H = Polyomino([(-1, 1), (-1, 4), (-1, 7), (0, 0), (0, 1), (0, 2),
....: (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 1), (1, 2),
....: (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 2),
....: (2, 3), (2, 5), (2, 6), (2, 8)])
sage: solution = H.self_surrounding(8)
sage: G = sum([p.show2d() for p in solution], Graphics())                   # optional - sage.plot

sage: solution = H.self_surrounding(8, remove_incomplete_copies=False)
sage: G = sum([p.show2d() for p in solution], Graphics())                   # optional - sage.plot
show2d(size=0.7, color='black', thickness=1)#

Return a 2d Graphic object representing the polyomino.

INPUT:

  • self - a polyomino of dimension 2

  • size - 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)                            # optional -- sage.plot
Graphics object consisting of 17 graphics primitives
show3d(size=1)#

Return a 3d Graphic object representing the polyomino.

INPUT:

  • self - a polyomino of dimension 3

  • size - number (optional, default: 1), the size of each 1 \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)                            # optional -- sage.plot
Graphics3d Object
sorted_list()#

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.sorted_list()
[(0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1)]
translated_copies(box)#

Return an iterator over the translated images of self inside a polyomino.

INPUT:

  • box – Polyomino or tuple of integers (size of a box)

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

Using a Polyomino as input:

sage: b = Polyomino([(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)])
sage: p = Polyomino([(0,0)])
sage: list(p.translated_copies(b))
[Polyomino: [(0, 0)], Color: gray,
 Polyomino: [(0, 1)], Color: gray,
 Polyomino: [(0, 2)], Color: gray,
 Polyomino: [(1, 0)], Color: gray,
 Polyomino: [(1, 1)], Color: gray,
 Polyomino: [(1, 2)], Color: gray]

sage: p = Polyomino([(0,0), (1,0), (0,1)])
sage: b = Polyomino([(0,0), (1,0), (2,0), (0,1), (1,1), (0,2)])
sage: list(p.translated_copies(b))
[Polyomino: [(0, 0), (0, 1), (1, 0)], Color: gray,
 Polyomino: [(0, 1), (0, 2), (1, 1)], Color: gray,
 Polyomino: [(1, 0), (1, 1), (2, 0)], Color: gray]
translated_copies_intersection(box)#

Return the set of non empty intersections of translated images of self with a polyomino.

INPUT:

  • box – Polyomino or tuple of integers (size of a box)

OUTPUT:

set of 3d polyominoes

EXAMPLES:

sage: from sage.combinat.tiling import Polyomino
sage: p = Polyomino([(0,0),(1,0)], color='deeppink')
sage: sorted(sorted(a.frozenset()) for a in p.translated_copies_intersection(box=(2,3)))
[[(0, 0)],
 [(0, 0), (1, 0)],
 [(0, 1)],
 [(0, 1), (1, 1)],
 [(0, 2)],
 [(0, 2), (1, 2)],
 [(1, 0)],
 [(1, 1)],
 [(1, 2)]]

Using a Polyomino as input:

sage: b = Polyomino([(0,0), (0,1), (0,2), (1,0), (2,0)])
sage: p = Polyomino([(0,0), (1,0)])
sage: sorted(sorted(a.frozenset()) for a in p.translated_copies_intersection(b))
[[(0, 0)], [(0, 0), (1, 0)], [(0, 1)], [(0, 2)], [(1, 0), (2, 0)], [(2, 0)]]
class sage.combinat.tiling.TilingSolver(pieces, box, rotation=True, reflection=False, reusable=False, outside=False)#

Bases: SageObject

Tiling solver

Solve the problem of tiling a polyomino with a certain number of polyominoes.

INPUT:

  • pieces – iterable of Polyominoes

  • box – Polyomino or tuple of integers (size of a box)

  • rotation – bool (optional, default: True), whether to allow rotations

  • reflection – bool (optional, default: False), whether to allow reflections

  • reusable – bool (optional, default: False), whether to allow the pieces to be reused

  • outside – bool (optional, default: False), whether to allow pieces to partially go outside of the box (all non-empty intersection of the pieces with the box are considered)

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 a box of size 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

Tiling of a polyomino by polyominoes:

sage: b = Polyomino([(0,0), (1,0), (1,1), (2,1), (1,2), (2,2), (0,3), (1,3)])
sage: p = Polyomino([(0,0), (1,0)])
sage: T = TilingSolver([p], box=b, reusable=True)
sage: T.number_of_solutions()
2
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 frames

  • size - number (optional, default: 0.75), the size of each 1 \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()                                                       # optional - sage.plot
sage: a          # optional -- ImageMagick    # long time                   # optional - sage.plot
Animation with 10 frames

Include partial solutions (common prefix between two consecutive solutions):

sage: a = T.animate('common_prefix')                                        # optional - sage.plot
sage: a          # optional -- ImageMagick    # long time                   # optional - sage.plot
Animation with 19 frames

Incremental solutions (one piece removed or added at a time):

sage: a = T.animate('incremental')      # long time (2s)                    # optional - sage.plot
sage: a                                 # long time (2s)  # optional -- ImageMagick sage.plot
Animation with 123 frames

sage: a.show()           # optional -- ImageMagick   # long time            # optional - sage.plot

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 # long time # optional - sage.plot

Limit the number of frames:

sage: a = T.animate('incremental', stop=13)     # not tested                # optional - sage.plot
sage: a                                         # not tested                # optional - sage.plot
Animation with 13 frames
coord_to_int_dict()#

Return 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.items())
[((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.items())
[((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 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: T.dlx_solver()
Dancing links solver for 9 columns and 15 rows
int_to_coord_dict()#

Return 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.items())
[(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.items())
[(0, (0, 0)), (1, (0, 1)), (2, (1, 0)), (3, (1, 1)), (4, (2, 0)), (5, (2, 1))]
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:

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]
number_of_solutions()#

Return the number of distinct solutions.

OUTPUT:

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
pieces()#

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
row_to_polyomino(row_number)#

Return a polyomino associated to a row.

INPUT:

  • row_number – integer, the i-th row

OUTPUT:

polyomino

EXAMPLES:

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, 2), (1, 0, 1), (1, 0, 2)], Color: blue

sage: T.row_to_polyomino(13)
Polyomino: [(0, 0, 1), (1, 0, 1), (1, 0, 2)], 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 piece

  • mod_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, 2, 3, 5],
 [0, 3, 4, 6],
 [0, 2, 3, 6],
 [0, 3, 4, 7],
 [0, 2, 5, 6],
 [0, 3, 6, 7],
 [0, 3, 5, 6],
 [0, 4, 6, 7]]
sage: T.rows_for_piece(0, mod_box_isometries=True)
[[0, 2, 3, 5], [0, 3, 4, 6]]
sage: T.rows_for_piece(1, mod_box_isometries=True)
[[1, 2, 3, 5], [1, 3, 4, 6]]
solve(partial=None)#

Return an iterator of list of 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 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 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
space()#

Return an iterator over all the non negative integer coordinates contained in the space to tile.

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 space

  • orientation_preserving – bool (optional, default: True), whether the orientation is preserved

OUTPUT:

list of matrices

EXAMPLES:

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

[-1  0  0]  [ 0 -1  0]  [-1  0  0]  [-1  0  0]  [ 0 -1  0]  [ 0  0 -1]
[ 0 -1  0]  [ 0  0 -1]  [ 0  0 -1]  [ 0  1  0]  [ 0  0  1]  [ 1  0  0]
[ 0  0  1], [ 1  0  0], [ 0 -1  0], [ 0  0 -1], [-1  0  0], [ 0 -1  0],

[ 0  1  0]  [ 0  0  1]  [0 0 1]  [ 0 -1  0]  [ 0  0 -1]  [-1  0  0]
[ 1  0  0]  [ 0  1  0]  [1 0 0]  [ 1  0  0]  [ 0  1  0]  [ 0  0  1]
[ 0  0 -1], [-1  0  0], [0 1 0], [ 0  0  1], [ 1  0  0], [ 0  1  0],

[ 0 -1  0]  [ 0  0 -1]  [ 0  0  1]  [ 1  0  0]  [ 0  0 -1]  [ 0  1  0]
[-1  0  0]  [-1  0  0]  [-1  0  0]  [ 0 -1  0]  [ 0 -1  0]  [ 0  0 -1]
[ 0  0 -1], [ 0  1  0], [ 0 -1  0], [ 0  0 -1], [-1  0  0], [-1  0  0]
]
sage.combinat.tiling.ncube_isometry_group_cosets(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 space

  • orientation_preserving – bool (optional, default: True), whether the orientation is preserved

OUTPUT:

list of cosets, each coset being a sorted list of matrices

EXAMPLES:

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