Wang cubes, tiling and solver

Wang cubes tiling solver

We solve the problem of tiling a rectangular box by Wang cubes by reducing it to other well-known problems like linear problem, exact cover problem and SAT.

class slabbe.wang_cubes.WangCubeSet(cubes)

Bases: object

Construct a set of Wang cubes.

INPUT:

  • cubes – list or dict of cubes, a Wang cube is a 6-tuple identifying a label to each square face orthogonal to the vectors in the following order: \((e_1,e_2,e_3,-e_1,-e_2,-e_3)\)

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)

Input can be a dictionnary:

sage: cubes = {'a':(0,0,0,0,0,0), 'b':(1,1,1,1,1,1), 'c':(2,2,2,2,2,2)}
sage: T = WangCubeSet(cubes)
cubes()

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.cubes()
{0: (0, 0, 0, 0, 0, 0),
 1: (1, 1, 1, 1, 1, 1),
 2: (2, 2, 2, 2, 2, 2)}
indices()

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: list(T.indices())
[0, 1, 2]
is_aperiodic_candidate(stop=None, verbose=False, solver=None, certificate=True)

Return False if a periodic configuration is found or if some finite 3d rectangular box admit no tiling.

INPUT:

  • stop – integer

  • solver – string or None (default: None), 'dancing_links' or the name of a MILP solver in Sage like 'GLPK', 'Coin', 'cplex' or 'Gurobi' or the name of a SAT solver in SageMath

  • certificate – bool (default:False)

  • verbose – bool (default:False)

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,1,0,1,0), (1,1,3,1,2,1), (2,0,2,0,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_aperiodic_candidate(5, certificate=True)
(False, 'is_finite', (True, (2, 2, 2)))
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_aperiodic_candidate(5, certificate=True)
(False, 'is_periodic', (True, (1, 1, 1)))
is_finite(stop=None, start=1, solver=None, certificate=False, verbose=False)

INPUT:

  • stop – integer

  • start – integer (default: 1)

  • solver – string or None (default: None), 'dancing_links' or the name of a MILP solver in Sage like 'GLPK', 'Coin', 'cplex' or 'Gurobi' or the name of a SAT solver in SageMath

  • certificate – bool (default:False)

  • verbose – bool (default:False)

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,1,0,1,0), (1,1,3,1,2,1), (2,0,2,0,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_finite(5, certificate=True)
(True, (2, 2, 2))
is_periodic(stop=None, start=3, solver=None, certificate=False, verbose=False)

INPUT:

  • stop – integer

  • start – integer (default:3), sum of the sizes of the rectangular box

  • solver – string or None (default: None), 'dancing_links' or the name of a MILP solver in Sage like 'GLPK', 'Coin', 'cplex' or 'Gurobi' or the name of a SAT solver in SageMath

  • certificate – bool (default:False)

  • verbose – bool (default:False)

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_periodic(5, certificate=True)
(True, (1, 1, 1))
sage: cubes = [(0, 0, 1, 0, 0, 0), (0, 1, 0, 0, 0, 0), (0, 0, 0, 0, 1, 1)]
sage: T = WangCubeSet(cubes)
sage: T.is_periodic(5, certificate=True)
is_periodic_111()

Return True is some Wang cube tiles the space trivially.

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,0,1), (2,2,2,0,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_periodic_111()
True
sage: cubes = [(1,0,0,0,0,0), (1,1,1,1,0,1), (2,2,2,0,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_periodic_111()
False
is_periodic_parallel(stop=None, solver=None, certificate=False, verbose=False, ncpus=8)

INPUT:

  • stop – integer

  • solver – string or None (default: None), 'dancing_links' or the name of a MILP solver in Sage like 'GLPK', 'Coin', 'cplex' or 'Gurobi' or the name of a SAT solver in SageMath

  • certificate – bool (default:False)

  • verbose – bool (default:False)

  • ncpus – integer (default:8)

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: T.is_periodic_parallel(5, certificate=True)
(True, (1, 1, 1))
sat_solution_to_tiling(box, solution)

Return a configuration of cubes from a SAT solution

INPUT:

  • box – tuple of 3 integers

  • solution – tuple of bools

OUTPUT:

dict

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: box = (2,2,2)
sage: solution = (None, False, False, False, False, False,
....:   False, False, False, True, True, True, True, True, True, True,
....:   True, False, False, False, False, False, False, False, False)
sage: T.sat_solution_to_tiling(box, solution)
array([[[1, 1],
        [1, 1]],
<BLANKLINE>
       [[1, 1],
        [1, 1]]], dtype=int8)
sat_solver(box, cyclic=False, preassigned_color=None, preassigned_cubes=None, solver=None)

Return the SAT solver.

INPUT:

  • box – tuple of 3 integers

  • cyclic – boolean (default: False), whether the constraints on opposite boundary must match

  • preassigned_color – None or list of 6 dict or the form [{}, {}, {}, {}, {}, {}] right, top, left, bottom colors preassigned to some positions (on the border or inside)

  • preassigned_cubes – None or dict of cubes preassigned to some positions

  • solver – string or None (default: None), 'dancing_links' or the name of a MILP solver in Sage like 'GLPK', 'Coin', 'cplex' or 'Gurobi' or the name of a SAT solver in SageMath

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: box = (2,2,2)
sage: s = T.sat_solver(box)
sage: s             # random
PicoSAT solver: 24 variables, 104 clauses.
sage: list(s())
[None, ...]
sage: s = T.sat_solver(box, cyclic=True)
sage: s             # random
PicoSAT solver: 24 variables, 176 clauses.
sage: list(s())
[None, ...]
sat_variable_to_cube_position_bijection(box)

Return the dictionary giving the correspondence between variables and cube indices i at position (j,k)

INPUT:

  • box – tuple of 3 integers

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: box = (2,2,2)
sage: d1,d2 = T.sat_variable_to_cube_position_bijection(box)
sage: d1
{1: (0, 0, 0, 0),
 2: (0, 0, 0, 1),
 3: (0, 0, 1, 0),
 4: (0, 0, 1, 1),
 5: (0, 1, 0, 0),
 6: (0, 1, 0, 1),
 7: (0, 1, 1, 0),
 8: (0, 1, 1, 1),
 9: (1, 0, 0, 0),
 10: (1, 0, 0, 1),
 11: (1, 0, 1, 0),
 12: (1, 0, 1, 1),
 13: (1, 1, 0, 0),
 14: (1, 1, 0, 1),
 15: (1, 1, 1, 0),
 16: (1, 1, 1, 1),
 17: (2, 0, 0, 0),
 18: (2, 0, 0, 1),
 19: (2, 0, 1, 0),
 20: (2, 0, 1, 1),
 21: (2, 1, 0, 0),
 22: (2, 1, 0, 1),
 23: (2, 1, 1, 0),
 24: (2, 1, 1, 1)}
solve_tiling_a_box(box, cyclic=False, solver=None, solver_parameters=None, ncpus=1)

Return a configuration of cubes in a box matching the constraints

INPUT:

  • box – tuple of 3 integers

  • cyclic – boolean (default: False), whether the constraints on opposite boundary must match

  • solver – string or None (default: None), 'dancing_links' or the name of a MILP solver in Sage like 'GLPK', 'Coin', 'cplex' or 'Gurobi' or the name of a SAT solver in SageMath

  • solver_parameters – dict (default: {}), parameters given to the MILP solver using method solver_parameter. For a list of available parameters for example for the Gurobi backend, see dictionary parameters_type in the file sage/numerical/backends/gurobi_backend.pyx

  • ncpus – integer (default: 1), maximal number of subprocesses to use at the same time, used only if solver is 'dancing_links'.

OUTPUT:

dict

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(0,0,0,0,0,0), (1,1,1,1,1,1), (2,2,2,2,2,2)]
sage: T = WangCubeSet(cubes)
sage: box = (2,2,2)
sage: T.solve_tiling_a_box(box, solver='glucose')
array([[[1, 1],
        [1, 1]],
<BLANKLINE>
       [[1, 1],
        [1, 1]]], dtype=int8)
sage: T.solve_tiling_a_box(box, cyclic=True, solver='glucose')
array([[[1, 1],
        [1, 1]],
<BLANKLINE>
       [[1, 1],
        [1, 1]]], dtype=int8)
tikz(ncols=3, scale=1, node_scale=1)

EXAMPLES:

sage: from slabbe import WangCubeSet
sage: cubes = [(i,i,i,i,i,i) for i in range(7)]
sage: cubes.append((0,1,2,3,4,5))
sage: T = WangCubeSet(cubes)
sage: t = T.tikz()
class slabbe.wang_cubes.WangCubeSets(n)

Bases: object

Construct a set of Wang cubes.

INPUT:

  • n – integer, number of cubes

EXAMPLES:

sage: from slabbe.wang_cubes import WangCubeSets
sage: S = WangCubeSets(3)
aperiodic_candidates(stop, verbose=False, solver='kissat', certificate=False, initial_candidates=None, ncpus=4)

EXAMPLES:

sage: from slabbe.wang_cubes import WangCubeSets
sage: S = WangCubeSets(2)
sage: L = list(S.aperiodic_candidates(stop=4))   # long time (5s)    # known bug
sage: len(L)                                     # long time (fast)  # known bug
22

This proves that there are no aperiodic set of 2 Wang cubes:

sage: L = list(S.aperiodic_candidates(stop=7)) # not tested (3s)
sage: len(L)                                   # not tested
0

Of the 3142 candidates of sets of 3 Wang cubes, their remains 1556 to check:

sage: S = WangCubeSets(3)
sage: L = list(S.aperiodic_candidates(stop=6, verbose=True)) # not tested 4 min
sage: len(L)                                                 # not tested
1556
sage: %time L = list(S.aperiodic_candidates(stop=7, verbose=True)) # not tested 4 min
sage: len(L)                                                       # not tested
1509
sage: %time L = list(S.aperiodic_candidates(stop=13, verbose=True)) # not tested (6min)
{(False, 'is_finite', 'NO DATA'): 11,
 (False, 'is_finite', (True, (2, 2, 2))): 792,
 (False, 'is_finite', (True, (3, 3, 3))): 289,
 (False, 'is_periodic', 'NO DATA'): 33,
 (False, 'is_periodic', (True, [1, 1, 2])): 155,
 (False, 'is_periodic', (True, [1, 1, 3])): 145,
 (False, 'is_periodic', (True, [1, 2, 1])): 23,
 (False, 'is_periodic', (True, [1, 2, 2])): 127,
 (False, 'is_periodic', (True, [1, 3, 3])): 220,
 (False, 'is_periodic', (True, [2, 1, 1])): 16,
 (False, 'is_periodic', (True, [2, 1, 2])): 26,
 (False, 'is_periodic', (True, [2, 2, 1])): 4,
 (False, 'is_periodic', (True, [2, 2, 2])): 34,
 (False, 'is_periodic', (True, [3, 1, 3])): 34
 (False, 'is_periodic', (True, [3, 3, 1])): 23, 
 (False, 'is_periodic', (True, [3, 3, 3])): 136, 
 (False, 'is_periodic', (True, [1, 1, 1])): 1074}