Python（AI 约束满足问题）将正方形 and/or 矩形 (2d) 瓷砖安装到矩形地面上

Question

我必须使用 python 程序通过 AI 算法将 and/or 二维瓷砖放入二维正方形或矩形平面中。每个图块都有长度和宽度。例如，如果一个平面是 4x3 并且一组图块是

S={(2,3),(1,2),(2,2)}

这些图块可以旋转 90 度以适应矩阵。

输入第一行包含平面的长度和宽度第二行瓷砖数量然后是后续瓷砖的长度，宽度

但输入应该用制表符分隔

例如

输出例如

1    1    2   2
1    1    3   3
1    1    3   3

我无法解决这个问题，因为我只能在 python 中使用标准库，没有 NumPy 也没有 CSP 库

~编辑 2` 到目前为止我的代码我不知道如何在没有 csp 库的情况下添加算法或生成网格


from sys import stdin
a = stdin.readline()

x = a.split()

rectangular_plane = [[0] * int(x[0]) for i in range(int(x[1]))]
num_of_rectangles = stdin.readline()

r_widths = []
r_lengths= []

for l in range(int(num_of_rectangles)):
    b = stdin.readline()
    y = b.split()

r_lengths.insert(l,y[0])
r_widths.insert(l,y[1])

Answer 1

我已经使用 backtracking 方法解决了任务，没有任何 non-standard 模块。

Try it online!

import sys

nums = list(map(int, sys.stdin.read().split()))
pw, ph = nums[0:2]
ts = list(zip(nums[3::2], nums[4::2]))
assert len(ts) == nums[2]

if sum([e[0] * e[1] for e in ts]) != pw * ph:
    print('Not possible!')
else:
    def Solve(*, it = 0, p = None):
        if p is None:
            p = [[0] * pw for i in range(ph)]
        if it >= len(ts):
            for e0 in p:
                for e1 in e0:
                    print(e1, end = ' ')
                print()
            return True
        for tw, th in [(ts[it][0], ts[it][1]), (ts[it][1], ts[it][0])]:
            zw = [0] * tw
            ow = [it + 1] * tw
            for i in range(ph - th + 1):
                for j in range(pw - tw + 1):
                    if all(p[k][j : j + tw] == zw for k in range(i, i + th)):
                        for k in range(i, i + th):
                            p[k][j : j + tw] = ow
                        if Solve(it = it + 1, p = p):
                            return True
                        for k in range(i, i + th):
                            p[k][j : j + tw] = zw
        return False

    if not Solve():
        print('Not possible!')

示例输入：

输出：

1 1 2 2
1 1 3 3
1 1 3 3

Python（AI 约束满足问题）将正方形 and/or 矩形 (2d) 瓷砖安装到矩形地面上

Python(AI Constraint satisfaction problem) Fitting square and/or rectangular (2d) tiles onto a rectangular ground

artificial-intelligence

constraints

python-3.x