# Family Games America’s Quantumino solver¶

This module allows to solve the Quantumino puzzle made by Family Games America (see also this video on Youtube). This puzzle was left at the dinner room of the Laboratoire de Combinatoire Informatique Mathematique in Montreal by Franco Saliola during winter 2011.

The solution uses the dancing links code which is in Sage and is based on the more general code available in the module sage.combinat.tiling. Dancing links were originally introduced by Donald Knuth in 2000 (arXiv:cs/0011047). In particular, Knuth used dancing links to solve tilings of a region by 2D pentaminos. Here we extend the method for 3D pentaminos.

This module defines two classes :

AUTHOR:

• Sebastien Labbe, April 28th, 2011

DESCRIPTION (from [1]):

” Pentamino games have been taken to a whole different level; a 3-D level, with this colorful creation! Using the original pentamino arrangements of 5 connected squares which date from 1907, players are encouraged to “think inside the box” as they try to fit 16 of the 17 3-D pentamino pieces inside the playing perimeters. Remove a different piece each time you play for an entirely new challenge! Thousands of solutions to be found! Quantumino hands-on educational tool where players learn how shapes can be transformed or arranged into predefined shapes and spaces. Includes: 1 wooden frame, 17 wooden blocks, instruction booklet. Age: 8+ “

EXAMPLES:

Here are the 17 wooden blocks of the Quantumino puzzle numbered from 0 to 16 in the following 3d picture. They will show up in 3D in your default (=Jmol) viewer:

sage: from sage.games.quantumino import show_pentaminos
sage: show_pentaminos()
Graphics3d Object


To solve the puzzle where the pentamino numbered 12 is put aside:

sage: from sage.games.quantumino import QuantuminoSolver
sage: s = next(QuantuminoSolver(12).solve())          # long time (10 s)
sage: s                                               # long time (<1s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (2, 1, 1)], Color: blue
sage: s.show3d()                                      # long time (<1s)
Graphics3d Object


To remove the frame:

sage: s.show3d().show(frame=False)                    # long time (<1s)


To solve the puzzle where the pentamino numbered 7 is put aside:

sage: s = next(QuantuminoSolver(7).solve())           # long time (10 s)
sage: s                                               # long time (<1s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange
sage: s.show3d()                                      # long time (<1s)
Graphics3d Object


The solution is iterable. This may be used to explicitly list the positions of each pentamino:

sage: for p in s: p                                   # long time (<1s)
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
Polyomino: [(0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 1), (1, 2, 1)], Color: deeppink
Polyomino: [(0, 2, 0), (0, 3, 0), (0, 4, 0), (1, 4, 0), (1, 4, 1)], Color: green
Polyomino: [(0, 3, 1), (1, 3, 1), (2, 2, 0), (2, 2, 1), (2, 3, 1)], Color: green
Polyomino: [(1, 3, 0), (2, 3, 0), (2, 4, 0), (2, 4, 1), (3, 4, 0)], Color: red
Polyomino: [(1, 0, 1), (2, 0, 1), (2, 1, 0), (2, 1, 1), (3, 1, 1)], Color: red
Polyomino: [(2, 0, 0), (3, 0, 0), (3, 0, 1), (3, 1, 0), (4, 0, 0)], Color: gray
Polyomino: [(3, 2, 0), (4, 0, 1), (4, 1, 0), (4, 1, 1), (4, 2, 0)], Color: purple
Polyomino: [(3, 2, 1), (3, 3, 0), (3, 3, 1), (4, 2, 1), (4, 3, 1)], Color: yellow
Polyomino: [(3, 4, 1), (3, 5, 1), (4, 3, 0), (4, 4, 0), (4, 4, 1)], Color: blue
Polyomino: [(0, 4, 1), (0, 5, 0), (0, 5, 1), (0, 6, 1), (1, 5, 0)], Color: midnightblue
Polyomino: [(0, 6, 0), (0, 7, 0), (0, 7, 1), (1, 7, 0), (2, 7, 0)], Color: darkblue
Polyomino: [(1, 7, 1), (2, 6, 0), (2, 6, 1), (2, 7, 1), (3, 6, 0)], Color: blue
Polyomino: [(1, 5, 1), (1, 6, 0), (1, 6, 1), (2, 5, 0), (2, 5, 1)], Color: yellow
Polyomino: [(3, 6, 1), (3, 7, 0), (3, 7, 1), (4, 5, 1), (4, 6, 1)], Color: purple
Polyomino: [(3, 5, 0), (4, 5, 0), (4, 6, 0), (4, 7, 0), (4, 7, 1)], Color: orange


To get all the solutions, use the iterator returned by the solve method. Note that finding the first solution is the most time consuming because it needs to create the complete data to describe the problem:

sage: it = QuantuminoSolver(7).solve()
sage: next(it)                                     # not tested (10s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange
sage: next(it)                                     # not tested (0.001s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange
sage: next(it)                                     # not tested (0.001s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange


To get the solution inside other boxes:

sage: s = next(QuantuminoSolver(7, box=(4,4,5)).solve())        # not tested (2s)
sage: s.show3d()                                                # not tested (<1s)

sage: s = next(QuantuminoSolver(7, box=(2,2,20)).solve())       # not tested (1s)
sage: s.show3d()                                                # not tested (<1s)


If there are no solution, a StopIteration error is raised:

sage: next(QuantuminoSolver(7, box=(3,3,3)).solve())
Traceback (most recent call last):
...
StopIteration


The implementation allows a lot of introspection. From the TilingSolver object, it is possible to retrieve the rows that are passed to the DLX solver and count them. It is also possible to get an instance of the DLX solver to play with it:

sage: q = QuantuminoSolver(0)
sage: T = q.tiling_solver()
sage: T
Tiling solver of 16 pieces into the box (5, 8, 2)
Rotation allowed: True
Reflection allowed: False
Reusing pieces allowed: False
sage: rows = T.rows()                            # not tested (10 s)
sage: len(rows)                                  # not tested (but fast)
5484
sage: x = T.dlx_solver()                         # long time (10 s)
sage: x                                          # long time (fast)


REFERENCES:

class sage.games.quantumino.QuantuminoSolver(aside, box=(5, 8, 2))

Return the Quantumino solver for the given box where one of the pentamino is put aside.

INPUT:

• aside - integer, from 0 to 16, the aside pentamino
• box - tuple of size three (optional, default: (5,8,2)), size of the box

EXAMPLES:

sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(9)
Quantumino solver for the box (5, 8, 2)
Aside pentamino number: 9
sage: QuantuminoSolver(12, box=(5,4,4))
Quantumino solver for the box (5, 4, 4)
Aside pentamino number: 12

number_of_solutions()

Return the number of solutions.

OUTPUT:

integer

EXAMPLES:

sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(4, box=(3,2,2)).number_of_solutions()
0


This computation takes several days:

sage: QuantuminoSolver(0).number_of_solutions()                # not tested
??? hundreds of millions ???

solve(partial=None)

Return an iterator over the solutions where one of the pentamino is put aside.

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' - common part between two consecutive solutions
• 'incremental' - one piece change at a time

OUTPUT:

iterator of QuantuminoState

EXAMPLES:

Get one solution:

sage: from sage.games.quantumino import QuantuminoSolver
sage: s = next(QuantuminoSolver(8).solve())          # long time (9s)
sage: s                                              # long time (fast)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 1, 0)], Color: yellow
sage: s.show3d()                                     # long time (< 1s)
Graphics3d Object


The explicit solution:

sage: for p in s: p                                  # long time (fast)
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
Polyomino: [(0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 1), (1, 2, 1)], Color: deeppink
Polyomino: [(0, 2, 0), (0, 3, 0), (0, 4, 0), (1, 4, 0), (1, 4, 1)], Color: green
Polyomino: [(0, 3, 1), (1, 3, 1), (2, 2, 0), (2, 2, 1), (2, 3, 1)], Color: green
Polyomino: [(1, 3, 0), (2, 3, 0), (2, 4, 0), (2, 4, 1), (3, 4, 0)], Color: red
Polyomino: [(1, 0, 1), (2, 0, 0), (2, 0, 1), (2, 1, 0), (3, 0, 1)], Color: midnightblue
Polyomino: [(0, 4, 1), (0, 5, 0), (0, 5, 1), (0, 6, 0), (1, 5, 0)], Color: red
Polyomino: [(2, 1, 1), (3, 0, 0), (3, 1, 0), (3, 1, 1), (4, 0, 0)], Color: blue
Polyomino: [(3, 2, 0), (4, 0, 1), (4, 1, 0), (4, 1, 1), (4, 2, 0)], Color: purple
Polyomino: [(3, 2, 1), (3, 3, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1)], Color: yellow
Polyomino: [(3, 3, 1), (3, 4, 1), (4, 4, 0), (4, 4, 1), (4, 5, 0)], Color: blue
Polyomino: [(0, 6, 1), (0, 7, 0), (0, 7, 1), (1, 5, 1), (1, 6, 1)], Color: purple
Polyomino: [(1, 6, 0), (1, 7, 0), (1, 7, 1), (2, 7, 0), (3, 7, 0)], Color: darkblue
Polyomino: [(2, 5, 0), (2, 6, 0), (3, 6, 0), (4, 6, 0), (4, 6, 1)], Color: orange
Polyomino: [(2, 5, 1), (3, 5, 0), (3, 5, 1), (3, 6, 1), (4, 5, 1)], Color: gray
Polyomino: [(2, 6, 1), (2, 7, 1), (3, 7, 1), (4, 7, 0), (4, 7, 1)], Color: orange


Enumerate the solutions:

sage: it = QuantuminoSolver(0).solve()
sage: next(it)                                          # not tested
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
sage: next(it)                                          # not tested
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink


With the partial solutions included, one can see the evolution between consecutive solutions (an animation would be better):

sage: it = QuantuminoSolver(0).solve(partial='common')
sage: next(it).show3d()               # not tested (2s)
sage: next(it).show3d()               # not tested (< 1s)
sage: next(it).show3d()               # not tested (< 1s)


Generalizations of the game inside different boxes:

sage: next(QuantuminoSolver(7, (4,4,5)).solve())       # long time (2s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange
sage: next(QuantuminoSolver(7, (2,2,20)).solve())      # long time (1s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color: orange
sage: next(QuantuminoSolver(3, (2,2,20)).solve())      # long time (1s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (1, 0, 0), (1, 0, 1)], Color: green


If the volume of the box is not 80, there is no solution:

sage: next(QuantuminoSolver(7, box=(3,3,9)).solve())
Traceback (most recent call last):
...
StopIteration


If the box is too small, there is no solution:

sage: next(QuantuminoSolver(4, box=(40,2,1)).solve())
Traceback (most recent call last):
...
StopIteration

tiling_solver()

Return the Tiling solver of the Quantumino Game where one of the pentamino is put aside.

EXAMPLES:

sage: from sage.games.quantumino import QuantuminoSolver
sage: QuantuminoSolver(0).tiling_solver()
Tiling solver of 16 pieces into the box (5, 8, 2)
Rotation allowed: True
Reflection allowed: False
Reusing pieces allowed: False
sage: QuantuminoSolver(14).tiling_solver()
Tiling solver of 16 pieces into the box (5, 8, 2)
Rotation allowed: True
Reflection allowed: False
Reusing pieces allowed: False
sage: QuantuminoSolver(14, box=(5,4,4)).tiling_solver()
Tiling solver of 16 pieces into the box (5, 4, 4)
Rotation allowed: True
Reflection allowed: False
Reusing pieces allowed: False

class sage.games.quantumino.QuantuminoState(pentos, aside)

A state of the Quantumino puzzle.

Used to represent an solution or a partial solution of the Quantumino puzzle.

INPUT:

• pentos - list of 16 3d pentamino representing the (partial) solution
• aside - 3d polyomino, the unused 3D pentamino

EXAMPLES:

sage: from sage.games.quantumino import pentaminos, QuantuminoState
sage: p = pentaminos[0]
sage: q = pentaminos[5]
sage: r = pentaminos[11]
sage: S = QuantuminoState([p,q], r)
sage: S
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 2, 0)], Color: darkblue

sage: from sage.games.quantumino import QuantuminoSolver
sage: next(QuantuminoSolver(3).solve())      # not tested (1.5s)
Quantumino state where the following pentamino is put aside :
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (1, 0, 0), (1, 0, 1)], Color: green

list()

Return the list of 3d polyomino making the solution.

EXAMPLES:

sage: from sage.games.quantumino import pentaminos, QuantuminoState
sage: p = pentaminos[0]
sage: q = pentaminos[5]
sage: r = pentaminos[11]
sage: S = QuantuminoState([p,q], r)
sage: L = S.list()
sage: L[0]
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 2, 0)], Color: deeppink
sage: L[1]
Polyomino: [(0, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (2, 0, 1)], Color: red

show3d(size=0.85)

Return the solution as a 3D Graphic object.

OUTPUT:

3D Graphic Object

EXAMPLES:

sage: from sage.games.quantumino import QuantuminoSolver
sage: s = next(QuantuminoSolver(0).solve())    # not tested (1.5s)
sage: G = s.show3d()                            # not tested (<1s)
sage: type(G)                                   # not tested
<class 'sage.plot.plot3d.base.Graphics3dGroup'>


To remove the frame:

sage: G.show(frame=False) # not tested


To see the solution with Tachyon viewer:

sage: G.show(viewer='tachyon', frame=False) # not tested

sage.games.quantumino.show_pentaminos(box=(5, 8, 2))

Show the 17 3-D pentaminos included in the game and the $$5 \times 8 \times 2$$ box where 16 of them must fit.

INPUT:

• box - tuple of size three (optional, default: (5,8,2)), size of the box

OUTPUT:

3D Graphic object

EXAMPLES:

sage: from sage.games.quantumino import show_pentaminos
sage: show_pentaminos()    # not tested (1s)


To remove the frame do:

sage: show_pentaminos().show(frame=False)  # not tested (1s)


Sudoku Puzzles