puzzle - 如何开始“无裂墙”问题

Question

这是问题陈述：

考虑一下用2x1和3x1砖（水平x垂直尺寸）建造墙的问题，这样一来，为了获得额外的强度，水平砖之间的缝隙不会在连续的层中对齐，即永远不会形成“运行裂缝”。
形成无裂缝9x3墙的方法有八种，记为W（9,3）= 8。
计算W（32,10）。 <将其概括为W（x，y）>
http://www.careercup.com/question?id=67814&form=comments

上面的链接提供了一些解决方案，但是我无法理解它们背后的逻辑。我正在尝试在Perl中编写代码，到目前为止已经完成：

input : W(x,y)
find all possible i's and j's such that x == 3(i) + 2(j);
for each pair (i,j) ,
find n = (i+j)C(j)            # C:combinations

将所有这些n相加应得出所有可能组合的计数。但是我不知道如何找到一行的真正组合以及如何继续进行。

Answer 1

基于W（9,3）= 8的说法，我推断“运行裂纹”是指高度为2或更大的任何连续垂直裂纹。在解决所提出的二维问题之前，我想讨论一个类似的一维问题及其解决方案。我希望这将使人们更清楚地将二维问题视为一维问题并最终得到解决。

假设您要计算长度为40的列表的数量，这些列表的符号来自一个相当小的集合，例如五个符号{a，b，c，d，e}。当然有5 ^ 40个这样的列表。如果我们添加一个额外的约束，使得字母不能连续出现两次，那么数学解决方案仍然很简单：存在5 * 4 ^ 39个没有重复字符的列表。但是，如果我们反而希望取缔诸如bc，cb，bd等辅音组合，那么事情就更加困难了。当然，我们想计算选择第一个字符，第二个字符等并相乘的方式，但是选择第二个字符的方式数目取决于第一个字符的选择，依此类推。这个新问题很难说明正确的技术。 （尽管不够困难，以使其完全抵制数学方法！）

为了解决没有辅音组合的长度为40的列表的问题（我们将其称为f（40）），我们可以想象使用递归。您可以根据f（39）计算f（40）吗？不，因为某些长度为39的列表以辅音结尾，而某些以元音结尾，而且我们不知道每种类型中有多少。因此，我们无需为每个长度n <= 40 f（n）计算，而是为每个n和每个字符k计算f（n，k），长度n的列表以k结尾。尽管f（40）不能是
仅从f（39）计算得出，就可以用f（30，a），f（39，b）等计算出f（40，a）。

上述策略可用于解决您的二维问题。您将拥有长度为32（或x）的整个水平砖行，而不是字符。而不是40，而是10（或y）。您可以使用no-adjacent-cracks约束来代替no-consonant-combinations约束。

您特别询问如何枚举给定长度的所有砖行，您是正确的，至少对于此方法而言，这是正确的。首先，决定如何表示行。显然，指定3个砖的位置就足够了，并且由于每个砖都有一个定义明确的中心，因此给出3个砖的中心位置的列表似乎很自然。例如，如果壁长为15，则序列（1,8,11）将这样描述一行：（ooo | oo | oo | ooo | ooo | oo）。此列表必须满足一些自然约束：


初始位置和最终位置不能为3砖的中心。上面的0和14是无效的条目。
序列中数字之间的连续差异必须为奇数，且至少为三个。
第一个条目的位置必须是奇数。
最后一个条目和列表长度之间的差异也必须是奇数。


有多种计算和存储所有此类列表的方法，但是从概念上讲，最简单的方法是沿墙的长度递归，直到完成后才忽略条件4。手动生成一个长度为2、3和4的墙的所有列表的表，然后针对每个n，从以前的值推导一个描述长度为n的墙的所有列表的表。完成时强加条件4，因为它在递归中不能很好地发挥作用。

给定任何砖行S，您还需要一种方法来快速描述合法存在于其下的所有砖行S'。为了简单起见，让我们假设墙的长度为32。


S'必须满足与上述S相同的约束。
当且仅当1不位于S中时，1才在S'中。
当且仅当30不位于S中时，30位于S'中。
对于S中的每个条目q，S'必须具有对应的条目q + 1或q-1，相反，对于S中的某个元素q，S'的每个元素都必须是q-1或q + 1。


例如，列表（1,8,11）可以合法地放在（7,10,30），（7,12,30）或（9,12,30）的顶部，但不能放在（9,10 ，30），因为它不满足“至少三个”条件。基于此描述，编写一个计算给定行的可能后继程序的循环并不难。

现在，我们将所有内容放在一起：

首先，对于固定x，创建一个长度为x的所有合法行的表。接下来，编写一个函数W（y，S），该函数（递归地）计算宽度x，高度y和顶行S的壁数。对于y = 1，W（y，S）= 1。否则，W（y，S）是值W（y-1，S'）的所有S'的总和，可以与上述S相关。

该解决方案足以解决问题W（32,10），但对于大x而言将失败。例如，正如我所描述的，W（100,10）几乎肯定是不可行的。如果x大但y小，我们将打破所有明智的砌砖惯例，并认为该墙是从左到右而不是从下到上建造的。这将需要描述墙的有效列。例如，列说明可以是一个列表，其长度为墙的高度，并且其条目在五个符号之间，分别表示“ 2x1砖的第一个正方形”，“ 2x1砖的第二个正方形”，“ a的第一个正方形” 3x1砖”等。当然，每个列的描述都有约束，而描述连续列之间的关系也有约束，但是与上述相同的方法也可以以这种方式工作，并且更适合长而短的墙。