Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Tiling Solver
Tiling a n-dimensional polyomino with n-dimensional polyominoes.
This module defines two classes:
- :class:`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.
- :class:`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 :mod:`sage.games.quantumino` module is based on the Tiling Solver and allows to solve the 3d Quantumino puzzle.
AUTHOR:
- Sebastien Labbe, June 2011, initial version - Sebastien Labbe, July 2015, count solutions up to rotations - Sebastien Labbe, 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 pentomino problem -------------------------
As mentionned in the introduction of [Knuth1]_, Scott's pentomino problem consists in tiling a chessboard leaving the center four squares vacant with the 12 distinct pentominoes.
The 12 pentominoes::
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 sage: G.show(aspect_ratio=1, axes=False) # long time
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) 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, 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()) 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] Knuth, Donald (2000). "Dancing links". :arxiv:`cs/0011047`.
""" #***************************************************************************** # Copyright (C) 2011-2015 Sebastien Labbe <slabqc@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** # python3
####################################### # n-cube isometry group transformations ####################################### r""" 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] [-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. """ else:
r""" 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] ]]
TESTS::
sage: cosets = ncube_isometry_group_cosets(3, False) sage: len(cosets) 6 sage: [len(c) for c in cosets] [8, 8, 8, 8, 8, 8] sage: type(cosets[0][0]) <... 'sage.matrix.matrix_rational_dense.Matrix_rational_dense'>
"""
# Construct the subgroup H of G of diagonal matrices else:
# Make sure that H is a subset of G
# Construct the cosets
############################## # Class Polyomino ############################## r""" 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
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 """ r""" Constructor.
See :mod:`Polyomino` for full documentation.
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
::
sage: from sage.combinat.tiling import Polyomino sage: Polyomino([(0,0), (1,0), (2,0)]) Polyomino: [(0, 0), (1, 0), (2, 0)], Color: gray """
raise TypeError("color = ({!r}) must be a string".format(color))
raise ValueError("Polyomino must be non empty")
r""" String representation.
EXAMPLES::
sage: from sage.combinat.tiling import Polyomino sage: Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='red') Polyomino: [(0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1)], Color: red """
r""" 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' """
r""" 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)}) """
def sorted_list(self): r""" 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)] """
r""" Return the size of the polyomino, i.e. the number of n-dimensional unit cubes.
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: len(p) 4 """
r""" 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: it = iter(p) sage: next(it) (0, 0, 0) """
def bounding_box(self): r""" 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]] """ [max(_) for _ in zipped_coords]]
r""" 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: hash(p) # random 2059134902 """
r""" Return whether self is equal to other.
INPUT:
- ``other`` - a polyomino
OUTPUT:
boolean
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: q = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='red') sage: p == q True sage: r = Polyomino([(0,0,0), (0,1,0), (1,1,0)], color='blue') sage: p == r False """
r""" Return whether self is not equal to other.
INPUT:
- ``other`` - a polyomino
OUTPUT:
boolean
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: q = Polyomino([(0,0,0), (0,1,0), (1,1,0), (1,1,1)], color='red') sage: p != q False sage: r = Polyomino([(0,0,0), (0,1,0), (1,1,0)], color='blue') sage: p != r True """
r""" Return whether self is inside of other.
INPUT:
- ``other`` - a polyomino
OUTPUT:
boolean
EXAMPLES::
sage: from sage.combinat.tiling import Polyomino sage: p = Polyomino([(0,0)]) sage: b = Polyomino([(0,0), (0,1), (1,1), (2,1)]) sage: p <= b True sage: b <= p False """
r""" Return whether self contains other.
INPUT:
- ``other`` - a polyomino
OUTPUT:
boolean
EXAMPLES::
sage: from sage.combinat.tiling import Polyomino sage: p = Polyomino([(0,0)]) sage: b = Polyomino([(0,0), (0,1), (1,1), (2,1)]) sage: p >= b False sage: b >= p True """
r""" Return a translated copy of self by the opposite of the vector v.
INPUT:
- ``v`` - tuple
OUTPUT:
polyomino
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 - (2,2,2) Polyomino: [(-2, -2, -2), (-1, -2, -2), (-1, -1, -2), (-1, -1, -1), (-1, 0, -2)], Color: deeppink """
r""" Return a translated copy of self by the vector v.
INPUT:
- ``v`` - tuple
OUTPUT:
polyomino
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 + (2,2,2) Polyomino: [(2, 2, 2), (3, 2, 2), (3, 3, 2), (3, 3, 3), (3, 4, 2)], Color: deeppink """
r""" Return the image of the polyomino under the application of the matrix m.
INPUT:
- ``m`` - square matrix, matching the dimension of self.
OUTPUT:
Polyomino
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: m = matrix(3, [1,0,0,0,1,0,0,0,1]) sage: m * p Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink sage: m = matrix(3, [1,0,0,0,0,-1,0,1,0]) sage: m * p Polyomino: [(0, 0, 0), (1, -1, 1), (1, 0, 0), (1, 0, 1), (1, 0, 2)], Color: deeppink
TESTS::
sage: m = matrix(2, [1,0,0,1]) sage: m * p Traceback (most recent call last): ... ValueError: Dimension of input matrix must match the dimension of the polyomino """ "dimension of the polyomino")
r""" 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 """
mod_box_isometries=False): r""" 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 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
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] """ else:
r""" Returns 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 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))) []
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] """ raise ValueError("Dimension of input box must match the " "dimension of the polyomino") boxmaxxyz, size)]
mod_box_isometries=False): r""" 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: list(p.isometric_copies(b)) [Polyomino: [(0, 0), (1, 0), (1, 1)], Color: gray, 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, Polyomino: [(0, 0), (0, 1), (1, 1)], Color: gray, Polyomino: [(0, 1), (1, 0), (1, 1)], Color: gray] """ raise ValueError("Dimension of input box must match the " "dimension of the polyomino") box_max_coords))) < box._dimension: raise NotImplementedError("The code below assumes that the" " sizes of the box (={}) are all distinct when" " argument `mod_box_isometries` is True.".format(box)) mod_box_isometries)
r""" 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: 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)] """
r""" 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) """
r""" 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))] """ raise NotImplementedError("The method boundary is currently " "implemented " "only for dimension 2")
r""" Returns 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) Graphics3d Object """
r""" Returns 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) Graphics object consisting of 17 graphics primitives """ (a-k, b-k)], color=self._color)
####################### # General tiling solver ####################### r""" 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 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
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
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 """ reflection=False, reusable=False): r""" Constructor.
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 Tiling solver of 3 pieces into a box of size 6 Rotation allowed: True Reflection allowed: False Reusing pieces allowed: False """ else: "rotation is not allowed")
r""" String representation
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: TilingSolver([p,q,r], box=(1,1,6)) Tiling solver of 3 pieces into a box of size 6 Rotation allowed: True Reflection allowed: False Reusing pieces allowed: False
"""
r""" 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 """ else: and len(self.rows()) != 0)
r""" 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 """
r""" Returns 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)] """
def coord_to_int_dict(self): r""" 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.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)] """ else: for i, c in enumerate(self.space()))
def int_to_coord_dict(self): r""" 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.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))]
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
""" else: for i, c in enumerate(self.space()))
r""" 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, 3, 5, 6], [0, 4, 6, 7], [0, 2, 3, 6], [0, 3, 4, 7], [0, 2, 3, 5], [0, 3, 4, 6], [0, 2, 5, 6], [0, 3, 6, 7]] sage: T.rows_for_piece(0, mod_box_isometries=True) [[0, 2, 3, 6], [0, 3, 4, 7]] sage: T.rows_for_piece(1, mod_box_isometries=True) [[1, 2, 3, 6], [1, 3, 4, 7]] """ else: orientation_preserving=orientation_preserving, mod_box_isometries=mod_box_isometries) else: if self._reflection: raise NotImplementedError("Reflection allowed, Rotation not " "allowed is not implemented") else: it = p.translated_copies(self._box)
def rows(self): r""" 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] """
r""" Return a list of rows representing the solutions up to isometries of the box.
The positions of the ``i``-th pieces are chosen up to isometries of the box. In dimension 3, there are four times less rows for that piece.
It is currently implemented only when the pieces are not reusable.
INPUT:
- ``i`` - integer, the i-th piece to consider, that piece must not be isometric to itself by a isometry that preserve the box.
EXAMPLES::
sage: from sage.combinat.tiling import TilingSolver, Polyomino sage: p = Polyomino([(0,0,0), (1,0,0), (1,1,0), (1,0,1), (2,0,1)], color='red') sage: T = TilingSolver([p], box=(3,4,2)) sage: T._rows_mod_box_isometries(0) [[0, 2, 3, 4, 5, 11], [0, 4, 5, 6, 7, 13], [0, 10, 11, 12, 13, 19], [0, 12, 13, 14, 15, 21], [0, 1, 9, 10, 12, 18], [0, 3, 11, 12, 14, 20], [0, 5, 13, 14, 16, 22], [0, 2, 9, 10, 12, 20], [0, 4, 11, 12, 14, 22], [0, 6, 13, 14, 16, 24], [0, 1, 3, 4, 11, 13], [0, 3, 5, 6, 13, 15], [0, 9, 11, 12, 19, 21], [0, 11, 13, 14, 21, 23]]
We test that there are four times less rows for that polyomino::
sage: len(T.rows()) == 4 * len(T._rows_mod_box_isometries(0)) True
Now, a real use case. A solution of the game Quantumino is a tiling of a `5 \times 8 \times 2` box. Since a `5 \times 8 \times 2` box has four orientation preserving isometries, each solution up to rotation is counted four times by this dancing links solver::
sage: from sage.games.quantumino import QuantuminoSolver sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: q = QuantuminoSolver(0) sage: T = q.tiling_solver() sage: dlx_solver(T.rows()) # long time (10s) Dancing links solver for 96 columns and 5484 rows
It is possible to avoid to compute 4 times each solution up to rotations. This is done by choosing a piece (here the 0-th) and considering 4 times less positions for that piece. To be precise, 90 positions instead of 360, therefore the dancing links solver below has 270 less rows::
sage: dlx_solver(T._rows_mod_box_isometries(0)) # long time (10s) Dancing links solver for 96 columns and 5214 rows """ raise ValueError("i(={}) must be 0 <= i < {}".format(i,len_pieces)) else: rows.extend(self.rows_for_piece(j))
r""" 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] """
r""" 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] """
r""" 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, 1), (1, 0, 1), (1, 0, 2)], Color: blue
::
sage: T.row_to_polyomino(13) Polyomino: [(0, 0, 1), (0, 0, 2), (1, 0, 1)], Color: red """ no += 1 else:
r""" 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 """
r""" Return an iterator over the row indices of the solutions.
OUTPUT:
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_iterator()) [[0, 7, 14], [0, 12, 10], [6, 13, 5], [6, 14, 2], [11, 9, 5], [11, 10, 3]] """ return
r""" 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.
OUTPUT:
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_iterator()) [[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_iterator()) [[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_iterator(): a [64, 83, 149, 44, 179, 62, 35, 162, 132, 101] [64, 83, 149, 44, 179] [64, 83, 149, 44, 179, 154, 35, 162, 132, 175] [64, 83, 149] [64, 83, 149, 97, 39, 162, 35, 62, 48, 106] [64] [64, 157, 149, 136, 179, 62, 35, 162, 132, 101] [64, 157, 149, 136, 179] [64, 157, 149, 136, 179, 154, 35, 162, 132, 175] [] [82, 119, 58, 97, 38, 87, 8, 63, 48, 107] [82, 119, 58, 97, 38] [82, 119, 58, 97, 38, 161, 8, 63, 140, 107] [82, 119] [82, 119, 150, 136, 180, 63, 8, 161, 131, 175] [82, 119, 150] [82, 119, 150, 171, 38, 87, 8, 63, 48, 107] [82, 119, 150, 171, 38] [82, 119, 150, 171, 38, 161, 8, 63, 140, 107] """ else:
r""" 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.
OUTPUT:
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_iterator()) [[0, 7, 14], [0, 12, 10], [6, 13, 5], [6, 14, 2], [11, 9, 5], [11, 10, 3]] sage: list(T._dlx_incremental_solutions_iterator()) [[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_iterator(): a [64, 83, 149, 44, 179, 62, 35, 162, 132, 101] [64, 83, 149, 44, 179, 154, 35, 162, 132, 175] [64, 83, 149, 97, 39, 162, 35, 62, 48, 106] [64, 157, 149, 136, 179, 62, 35, 162, 132, 101] [64, 157, 149, 136, 179, 154, 35, 162, 132, 175] [82, 119, 58, 97, 38, 87, 8, 63, 48, 107] [82, 119, 58, 97, 38, 161, 8, 63, 140, 107] [82, 119, 150, 136, 180, 63, 8, 161, 131, 175] [82, 119, 150, 171, 38, 87, 8, 63, 48, 107] [82, 119, 150, 171, 38, 161, 8, 63, 140, 107] sage: len(list(T._dlx_incremental_solutions_iterator())) 123 """ else:
r""" Returns 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
TESTS::
sage: T = TilingSolver([p,q,r], box=(1,1,7)) sage: next(T.solve()) Traceback (most recent call last): ... StopIteration
""" elif partial == 'incremental': it = self._dlx_incremental_solutions_iterator() else: raise ValueError("Unknown value for partial (=%s)" % partial)
r""" 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 """
r""" 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() 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 """ for piece in solution], Graphics()) for solution in it] xmax=xmax, ymax=ymax, aspect_ratio=1, axes=axes) elif dimension == 3: raise NotImplementedError("3d Animation must be implemented " "in Jmol first") else: raise NotImplementedError("Dimension must be 2 or 3 in order " "to make an animation") |