# Revision history [back]

I would suggest that you try implementing the feature yourself. There are basically three options available to express your tiling problem.

Which one to use depend on the tiling problem you want to solve (you might want to try all of them and convert your tiling problem with various encoding and use various solvers).

For example, here is an implementation of domino tiling of a rectangle with horizontal and vertical resources constraints using a mixed integer linear program

def rectangle_domino_tiling(width, height, num_horiz, num_vert):
from sage.numerical.mip import MIPSolverException

M = MixedIntegerLinearProgram()

# h[i,j]: whether there is a horizontal domino at position i,j
# v[i,j]: whether there is a vertical domino at position i,j
h = M.new_variable(binary=True)
v = M.new_variable(binary=True)

# tiling constraints
for i in range(width):
for j in range(height):
s = 0
if i > 0:
s += h[i-1, j]
if j > 0:
s += v[i, j-1]
if i < width - 1:
s += h[i, j]
if j < height - 1:
s += v[i,j]

# resource constraints
M.add_constraint(M.sum(h[i,j] for i in range(width - 1) for j in range(height)) == num_horiz)
M.add_constraint(M.sum(v[i,j] for i in range(width) for j in range(height - 1)) == num_vert)

try:
M.solve()
except MIPSolverException:
# no solution
return None

hval = M.get_values(h)
vval = M.get_values(v)

return ([(i, j) for i in range(width - 1) for j in range(height) if hval[i, j]],
[(i, j) for i in range(width) for j in range(height - 1) if vval[i, j]])

def plot_tiling(width, height, horizontal_dominos, vertical_dominos):
G = Graphics()
for i, j in horizontal_dominos:
G += polygon2d([(i, j), (i + 2, j), (i + 2, j + 1), (i, j + 1)], color='blue', edgecolor='black', alpha=0.5)
for i, j in vertical_dominos:
G += polygon2d([(i, j), (i + 1, j), (i + 1, j + 2), (i, j + 2)], color='red', edgecolor='black', alpha=0.5)
G.axes(False)
G.set_aspect_ratio(1)
return G


Here is an example of how to use these functions

sage: hsol, vsol = rectangle_domino_tiling(4, 4, 2, 6)
sage: plot_tiling(4, 4, hsol, vsol)


sage: hsol, vsol = rectangle_domino_tiling(2, 6, 2, 4)
sage: plot_tiling(2, 6, hsol, vsol)


I would suggest that you try implementing the feature yourself. There are basically three options available to express your tiling problem.

Which one to use depend on the tiling problem you want to solve (you might want to try all of them and convert your tiling problem with various encoding and use various solvers).

For example, here is an implementation of domino tiling of a rectangle with horizontal and vertical resources constraints using a mixed integer linear program

def rectangle_domino_tiling(width, rectangle_domino_tilings(width, height, num_horiz, num_vert):
from sage.numerical.mip import MIPSolverException

M = MixedIntegerLinearProgram()

# h[i,j]: whether there is a horizontal domino at position i,j
# v[i,j]: whether there is a vertical domino at position i,j
h = M.new_variable(binary=True)
v = M.new_variable(binary=True)

num_pieces = (width * height) // 2

# tiling constraints
for i in range(width):
for j in range(height):
s = 0
if i > 0:
s += h[i-1, j]
if j > 0:
s += v[i, j-1]
if i < width - 1:
s += h[i, j]
if j < height - 1:
s += v[i,j]
v[i, j]

# resource constraints
M.add_constraint(M.sum(h[i,j] M.add_constraint(M.sum(h[i, j] for i in range(width - 1) for j in range(height)) == num_horiz)
M.add_constraint(M.sum(v[i,j] M.add_constraint(M.sum(v[i, j] for i in range(width) for j in range(height - 1)) == num_vert)

while True:
try:
M.solve()
except MIPSolverException:
# no solution
return None

break

hval = M.get_values(h)
vval = M.get_values(v)

return     # yield the solution
yield ([(i, j) for i in range(width - 1) for j in range(height) if hval[i, j]],
[(i, j) for i in range(width) for j in range(height - 1) if vval[i, j]])

# exclude the solution for next iteration
M.add_constraint(M.sum(h[i, j] for i in range(width - 1) for j in range(height) if hval[i,j])
+ M.sum(v[i, j] for i in range(width) for j in range(height - 1) if vval[i, j])
<= num_pieces - 1)

def plot_tiling(width, height, horizontal_dominos, vertical_dominos):
G = Graphics()
for i, j in horizontal_dominos:
G += polygon2d([(i, j), (i + 2, j), (i + 2, j + 1), (i, j + 1)], color='blue', edgecolor='black', alpha=0.5)
for i, j in vertical_dominos:
G += polygon2d([(i, j), (i + 1, j), (i + 1, j + 2), (i, j + 2)], color='red', edgecolor='black', alpha=0.5)
G.axes(False)
G.set_aspect_ratio(1)
return G


Here is an example of how to use these functions

sage: solutions = list(rectangle_domino_tilings(4, 4, 2, 6))
sage: len(solutions)
sage: graphics_array([plot_tiling(4, 4, hsol, vsol) for hsol, vsol = rectangle_domino_tiling(4, 4, 2, 6)
sage: plot_tiling(4, 4, hsol, vsol)
in solutions], 3, 3)


sage: solutions = list(rectangle_domino_tilings(2, 6, 2, 4))
sage: len(solutions)
6
sage:  graphics_array([plot_tiling(2, 6, hsol, vsol) for hsol, vsol = rectangle_domino_tiling(2, 6, in solutions], 2, 4)
sage: plot_tiling(2, 6, hsol, vsol)
3)