algorithm - 使用递归编程用 L 形三 block 瓷砖填充 n*m block 矩阵的方法数

Question

我正在寻找解决此问题的方法，您必须使用 L 形三 block 拼贴 block 填充 n*m (n, m <=8) block 矩阵。瓷砖不能以任何方式相互重叠。

我不一定要寻找完整的答案，只是关于如何处理它的提示。

来源:https://cses.fi/dt/task/336

Answer 1

我解决了这个 graph problem使用 recursive backtracking算法加 memoization .我的解决方案不是特别快，需要一分钟左右的时间来解决 9x12 网格，但对于您问题中的 8x8 网格应该足够了(在 9x9 上大约需要一秒钟)。 7x7 和 8x8 网格没有解决方案，因为它们不能被 triomino 大小 3 整除。

策略是从网格的一个角落开始，逐个单元格地移动，尝试在合法的情况下放置每个 block ，从而有条不紊地探索解决方案空间。

如果方 block 的放置是合法的，但在网格中产生了无法填充的气穴，则移除方 block ；我们提前知道这种状态没有解决方案，可以放弃探索它的 child 。例如，在 3x6 网格上，

abb.c.
aabcc.
......

无可救药。

一旦达到所有单元格都已填充的状态，我们就可以向其父状态报告 1 个解决方案的计数。下面是已求解的 3x6 网格的示例:

aaccee
abcdef
bbddff

如果每个可能的 block 都已放置在某个位置，则回溯，沿途向父状态报告解决方案计数并探索尚未探索的任何状态。

就内存而言，如果存在某种排列的图 block 使得它们覆盖完全相同的坐标，则将任意两个网格状态称为等效的。例如:

aacc..
abdc..
bbdd..

和

aacc..
bacd..
bbdd..

被认为是等效的，即使这两个状态是通过不同的图 block 放置达到的。两种状态具有相同的子结构，因此计算一种状态的解的数量就足够了；将其添加到备忘录中，如果我们再次达到该状态，我们可以简单地报告备忘录中的解决方案数量，而不是重新计算所有内容。

我的程序在 3x6 网格上报告 8 个解决方案:

正如我提到的，我的 Python 解决方案既不快速也不优化。可以在不到一秒的时间内解决 9x12 网格。除了大的优化，我在实现中忽略了一些基本的东西。例如，我为每个瓷砖放置复制了整个网格；在单个网格上添加/删除图 block 本来是一个简单的改进。我也没有检查网格中无法解决的间隙，这可以在动画中看到。

解决问题后，一定要四处寻找人们提出的一些令人兴奋的解决方案。我不想放弃更多!