Tiling solver: finite limits for reusable pieces

edit

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

• dancing links
• mixed integer linear programming
• SAT

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]
            M.add_constraint(s == 1)

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