确定奶酪片是否可以重新组装成完整块的算法

Question

我正在尝试编写一个程序来确定是否可以将一组长方形且全为一毫米厚的奶酪片重新组装成一个完整的块，以及以什么顺序组装。本质上，问题是检查一组给定的矩形块是否可以以形成固体奶酪块的方式排列。谁能建议一种算法或方法来解决这个问题？我正在用 Python 编程，但我也愿意接受其他语言的建议。到目前为止，这是我的代码：

import os

# Function to import the file
def importFile(file):
    slices = []
    with open(file, "r") as f:
        lines = f.readlines()
        number_of_slices = float(lines[0])
        for line in range(1, len(lines)):
            slices.append(lines[line].strip().split(" "))
        for i in range(0, len(slices)):
            for j in range(0,2):
                slices[i][j] = float(slices[i][j])
    return number_of_slices, slices

# Main function to determine the solution
def backtracking(file):
    # Import the file and declare variables
    imported = importFile(file)
    number_of_slices = imported[0]
    slices = imported[1]
    
    # Create a new cheese block
    cheese = cheeseBlock()
    # Add the first slice to the cheese block and remove it from the list of slices
    cheese.addSlice(slices[0], "FRONT")
    slices.pop(0)
    # List to keep track of which slices have been checked
    checkedSlices = [[], []]
    # Repeat until all slices are added to the cheese block
    while len(cheese.addedSlices) < number_of_slices:
        # Select the next slice to add (must fit on the cheese block and not be in the checked list of the last level)
        nextSlice = None
        for slice in slices:
            if cheese.checkSlice(slice) != None and slice not in checkedSlices[-1]:
                nextSlice = slice
                break
        # If no slice is found
        if nextSlice == None:
            # Add the last slice back to the list of slices
            slices.append(cheese.addedSlices[-1])
            # Remove the last entry from the checked list
            checkedSlices.pop()
            # Add the slice to the checked list of the last level
            checkedSlices[-1].append(cheese.addedSlices[-1])
            # Remove the slice from the cheese block
            cheese.removeSlice()
            # If the cheese block is empty, choose a new start slice that is not in the checked list
            if cheese.addedSlices == []:
                for slice in slices:
                    if slice not in checkedSlices[-1]:
                        cheese.addSlice(slice, "TOP")
                        checkedSlices += [[]]
                        break
                # If no start slice is found, there is no solution
                if cheese.addedSlices == []:
                    return None
        # If a slice is found
        else:
            # Add a new level to the checked list
            checkedSlices += [[]]
            # Add the slice to the cheese block
            position = cheese.checkSlice(nextSlice)
            cheese.addSlice(nextSlice, position)
            # Remove the slice from the list of remaining slices
            slices.remove(nextSlice)

    # Output the order of slices added to the cheese block (reverse order corresponds to order of cutting) 
    return cheese.addedSlices

# Class for the cheese block
class cheeseBlock():
    def __init__(self):
        # List of slices added to the cheese block (initially empty)
        self.addedSlices = []
        # Dimensions of the cheese block in millimeters
        self.height = 0 # Height
        self.width = 0  # Width
        self.length = 0 # Depth

    # Method to add a slice to the cheese block and adjust the dimensions accordingly
    def addSlice(self, slice, position):
        if self.addedSlices == []:
            self.addedSlices
        self.addedSlices += [slice]
        self.height = slice[1]
        self.width = slice[0]
        self.length += 1
    else:
        self.addedSlices += [slice]
        if position == "TOP":
            self.height += 1
        elif position == "SIDE":
            self.width += 1
        elif position == "FRONT":
            self.length += 1

# Method to remove the last slice added to the cheese block and adjust the dimensions accordingly
def removeSlice(self):
    position = self.checkSlice(self.addedSlices[-1])
    self.addedSlices.pop()
    if position == "TOP":
        self.height -= 1
    elif position == "SIDE":
        self.width -= 1
    elif position == "FRONT":
        self.length -= 1

# Method to check if a given slice can be added to the cheese block and if so, at which position
def checkSlice(self, slice):
    if (self.width == slice[0] and self.length == slice[1]) or (self.width == slice[1] and self.length == slice[0]):
        position = "TOP"
    elif (self.length == slice[0] and self.height == slice[1]) or (self.length == slice[1] and self.height == slice[0]):
        position = "SIDE"
    elif (self.width == slice[0] and self.height == slice[1]) or (self.width == slice[1] and self.height == slice[0]):
        position = "FRONT"
    else:
        return None
    return position

filename = "kaese5.txt"
current_directory = os.path.dirname(os.path.abspath(file))
file_path = os.path.join(current_directory, filename)
solution = backtracking(file_path)

if solution == None:
   print("The given slices cannot be used to form a block of cheese that contains all slices")
else:
   solution.reverse()
   print("The slices were cut in the following order to form the cheese block:")
   for slice in solution:
      print(slice[0], slice[1])

可以在以下链接中找到示例：https://bwinf.de/fileadmin/bundeswettbewerb/41/kaese5.txt。在这里，第一行表示切片的总数，而在接下来的几行中，可以读取每个切片的大小。 上面的代码使用回溯算法解决了将奶酪片切割成矩形块的问题。 该代码定义了两个函数，importFile(file)、backtracking(file) 和类 cheeseBlock()，分别从文件导入数据、使用回溯解决问题和表示奶酪块。 backtracking(file) 函数是应用回溯算法确定要切割的切片顺序以形成包含所有切片的矩形奶酪块的主要函数。 cheeseBlock() 类用于跟踪奶酪尺寸和添加到块中的切片顺序。 最终的解决方案按照切片切割的顺序打印到控制台。

提前感谢您提供的任何帮助。