# Tiling solver: finite limits for reusable pieces

I am hoping someone can explain to me how to get the Tiling Solver to work sensibly with finitely limited piece constraints. I tried adding multiple copies of given polyominos into the pieces list and setting reusable = False, but this was not handled sensibly by the iterator as it seemed to be viewing permutations of identical pieces as distinct solutions, and therefore finding absurdly many solutions.

If there is no way to do this currently, it seems like a worthy feature to implement.

Thank you!

edit retag close merge delete

Sort by ยป oldest newest most voted

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_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]

# 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)

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

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

# 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 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 in solutions], 2, 3)


more

Thank you, this is very helpful. I am very much a novice when it comes to writing code in general, but this is a very clear example. It would take me some time to implement everything I need (for example, different sets of pieces or tiling boards), but it is none-the-less a very good example. Not to mention, your ouput is very appealing visually.

However, given that Sage already has a very robust tiling solver, this seems like a no-brainer update for someone who knows what they are doing a bit better than I do.

Thank you!

( 2024-08-03 06:47:26 +0200 )edit