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
– integersolver
– 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 SageMathcertificate
– 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
– integerstart
– 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 SageMathcertificate
– 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
– integerstart
– integer (default:3
), sum of the sizes of the rectangular boxsolver
– 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 SageMathcertificate
– 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
– integersolver
– 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 SageMathcertificate
– 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 integerssolution
– 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 integerscyclic
– boolean (default:False
), whether the constraints on opposite boundary must matchpreassigned_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 positionssolver
– 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 integerscyclic
– boolean (default:False
), whether the constraints on opposite boundary must matchsolver
– 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 SageMathsolver_parameters
– dict (default:{}
), parameters given to the MILP solver using methodsolver_parameter
. For a list of available parameters for example for the Gurobi backend, see dictionaryparameters_type
in the filesage/numerical/backends/gurobi_backend.pyx
ncpus
– integer (default:1
), maximal number of subprocesses to use at the same time, used only ifsolver
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}