python - 平铺，在这种情况下如何使用递归？

Question

我正在尝试制作一种能够解决拼贴问题中的大图 block 集的算法。现在它能够根据宽度和高度找到正确的 Tiles 来放置，但是在使其正确递归方面存在一些问题。

如您所见，这个想法是，在放置的每个图 block 之后，该字段将被分隔为右字段和下字段。该算法将首先尝试填充右侧的字段，一旦完成，它就必须开始尝试填充下方的字段。

我遇到的问题是，一旦 Field Right 被解决，它必须以某种方式“发回”(我认为使用递归，虽然这很复杂)让它返回一个 Tile 并转到 Field下面属于那个 Tile。我把这个想法放在一些伪代码中，让它更容易理解。

如您所见，当 FieldRightWidth 已解决且 FieldBelowHeight 也已解决时，我想让它返回到前一个图 block 以检查 FieldBelow 是否已解决。我认为那是我需要放置一些代码来完成这项工作的地方，但经过数小时的谷歌搜索后，我仍然一无所知。

伪代码:

def Methods:
   create global tileset
   create local tileset (without duplicates)

   If globaltiles is empty: 
      solved    
      end
   else:
           if fieldRightWidth == solved:                  
               if fieldBelowHeight == solved:
                   return True???
               #FIELD BELOW
               else:
                    Search for Tile
                    Place Tile
                    Return Methods

           #FIELD RIGHT       
           else:
                Search for Tile
                Place Tile
                Return Methods

还有一张我希望算法执行的操作的图片:

所有代码: http://pastebin.com/8t4PeiZP

http://www.filedropper.com/tilingnew

我在编码方面还是个新手，所以非常感谢任何建议或帮助!

Answer 1

好吧，假设您要计算的区域是正方形或矩形(未旋转)，它从最小值 [x,y] 开始到最大值 [x,y] 结束，就像这样:

SMaxX = 5
SMinX = 0
SMaxY = 5
SMinY = 0

或者如果您熟悉 2D 矢量，您可以像这样优化它:

S = [5,5]

你可能知道 2D 向量，以防万一我解释什么是二维笛卡尔坐标中的向量:
S = [5,5] 表示，如果S从[0,0]开始，它将在[5, 5]，(更简单吧？)
所以盒子也会像这样:

#space each box taking
box1 = [3,3]
box2 = [2,2]
box3 = [1,1]

并且由于每个框都有优先级，所以我们说:

#priority of each box
box1 = 6
box2 = 4
box3 = 2

我们可以像这样将空间和优先级合并到字典中:

#Items
dic = {'box1':{'space':[3,3] , 'priority ':6},
       'box2':{'space':[2,2] , 'priority ':4},
       'box3':{'space':[1,1] , 'priority ':2}}

有每个盒子的优先级和空间，看起来像背包问题算法。
如果您熟悉背包问题算法，我们会在表格中尝试找到能够完美填充空间的最高优先级，或者换句话说，就是最佳可能的装箱方式。检查这个link1和 link2 .

但是背包问题算法的图表是一维解，如果你这样做，你会得到 10，所以 Box1 和 Box2。但由于它是 2D 并且你有不同的高度和宽度，所以标准的 1D 公式不起作用，也许你需要研究它看看你是否可以想出 2D 公式或询问周围是否有人这样做过。

除了背包问题算法，你可以尝试洪水填充算法，如果你有很大的面积，它会有点慢，但它的工作原理就像俄罗斯方 block 游戏一样。

您需要设置标准大小，如 1x1，然后用 1x1 数据定义整个区域，并将其存储在变量中并设置每个 True( bool 值)，然后用更高优先级的框填充该区域并设置这些 1x1 日期到 False，然后您可以很容易地检查它们中有多少是 True 以及它们占用的区域。

无论如何，我正在尝试找出不规则形状的相同事物，所以这就是我发现的全部内容，希望对您有所帮助。
(也检查这个 link，我得到了一些有用的答案。)

编辑: 好吧，如果你使用俄罗斯方 block 的想法在一个轴上定义区域和背包问题算法然后基于标准俄罗斯方 block 区域，在其他轴上再次使用背包问题算法应该可以完美地工作。