检查是否可以从一组块构建二维形状
Check whether a 2D shape can be constructed from a set of blocks
我正在寻找一种算法或程序的通用方法来验证是否可以从一组块中构建特定形状。
对于像下面示例中的一组 one-line 个块，可以将我们需要的形状转换为一条长线，并编写一个递归函数来根据块的长度选择块。
但是，使用包含 multi-line 块的集合（例如下例中的 2x2 正方形）来解决此任务（检查构建形状的可能性）的一般方法是什么？
递归解决这个问题的一种方法是从初始的黑白单元格开始，反复确定一个特定的黑色网格单元，并尝试用一块覆盖（或"nibble off"）那个网格单元以所有可能的方式。例如：始终选择最底部、最右侧的黑色网格单元——即在当前子问题的所有最底部黑色网格中，选择最右侧的。
覆盖所选单元格的棋子的某些（实际上是大多数）放置可以立即被识别为无效，因为它们也覆盖了一些白色单元格 - 我们知道所有白色单元格必须保持白色。如果没有任何可用棋子的 "good" 放置（一个放置是 "good" 如果它覆盖了选定的单元格并且没有白色单元格）那么我们可以 return 否对于这个子问题：这是不可能的解决。 OTOH 如果至少有一个 "good" 可用块的放置，它可能会或可能不会导致解决方案：为了处理这个问题，每个这样的 "good" 放置都会生成一个子问题，其中黑色单元格对应于该放置的棋子已被删除（即变为白色），并且刚刚放置的棋子类型的可用棋子数量已减少一个。当没有黑色单元格时，会出现基本情况：在这种情况下我们可以 return YES，因为我们知道可以放置棋子来实现空网格（具体来说，这涉及根本不放置棋子）。
这种递归方法可能会多次重访某些子问题。例如，如果原始网格的一部分包含一个 4x2 的黑色单元格块，并且您至少有以下 2 单元格块可用：
XX 2 Y 2
Y
那么您可以通过以下方式填充该 4x2 块
XXYY YXXY YYXX
XXYY YXXY YYXX
所以由此产生的子问题（缺少这个 4x2 块并且每种类型的块少 2 个）将被解决 3 次不同的时间。为避免这种情况，在某些（相当严格的）情况下，您可以使用自上而下的动态编程（也称为记忆）。这具有最多解决每个子问题一次的效果，但是（可能）需要存储所有可能子问题的答案（每个一位，表示是或否），其中有 2 ^(m*n)*(k_1+1)*(k_2+1)*...*(k_t+1)，其中 m 和 n 是宽度和高度网格和 k_1, ..., k_t 是 t 种不同类型棋子的可用副本数。在实践中，这意味着大于 5*5 的问题将无法解决（至少如果您使用网格的 "obvious" 编码，其中每个单元格成为整数中的一个位；它可能会出现使用更经济的编码，只需要 2^b 位，其中 b 是 最初黑色 单元格的总数，而不是整体单元格的总数）。 （OTOH，如果你准备假装每种类型的作品有无限数量，你只需要存储 2^(m*n) 个答案，因为我们不需要跟踪每个作品有多少piece remain. This may be useful as a quick first check: If the problem cannot be solved even with unlimited numbers of each type piece, then it certainly can't solved with limited numbers of them.)
我正在寻找一种算法或程序的通用方法来验证是否可以从一组块中构建特定形状。
对于像下面示例中的一组 one-line 个块，可以将我们需要的形状转换为一条长线，并编写一个递归函数来根据块的长度选择块。
但是，使用包含 multi-line 块的集合（例如下例中的 2x2 正方形）来解决此任务（检查构建形状的可能性）的一般方法是什么？
递归解决这个问题的一种方法是从初始的黑白单元格开始，反复确定一个特定的黑色网格单元，并尝试用一块覆盖（或"nibble off"）那个网格单元以所有可能的方式。例如：始终选择最底部、最右侧的黑色网格单元——即在当前子问题的所有最底部黑色网格中，选择最右侧的。
覆盖所选单元格的棋子的某些（实际上是大多数）放置可以立即被识别为无效，因为它们也覆盖了一些白色单元格 - 我们知道所有白色单元格必须保持白色。如果没有任何可用棋子的 "good" 放置（一个放置是 "good" 如果它覆盖了选定的单元格并且没有白色单元格）那么我们可以 return 否对于这个子问题：这是不可能的解决。 OTOH 如果至少有一个 "good" 可用块的放置，它可能会或可能不会导致解决方案：为了处理这个问题，每个这样的 "good" 放置都会生成一个子问题，其中黑色单元格对应于该放置的棋子已被删除（即变为白色），并且刚刚放置的棋子类型的可用棋子数量已减少一个。当没有黑色单元格时，会出现基本情况：在这种情况下我们可以 return YES，因为我们知道可以放置棋子来实现空网格（具体来说，这涉及根本不放置棋子）。
这种递归方法可能会多次重访某些子问题。例如，如果原始网格的一部分包含一个 4x2 的黑色单元格块，并且您至少有以下 2 单元格块可用：
XX 2 Y 2
Y
那么您可以通过以下方式填充该 4x2 块
XXYY YXXY YYXX
XXYY YXXY YYXX
所以由此产生的子问题（缺少这个 4x2 块并且每种类型的块少 2 个）将被解决 3 次不同的时间。为避免这种情况，在某些（相当严格的）情况下，您可以使用自上而下的动态编程（也称为记忆）。这具有最多解决每个子问题一次的效果，但是（可能）需要存储所有可能子问题的答案（每个一位，表示是或否），其中有 2 ^(m*n)*(k_1+1)*(k_2+1)*...*(k_t+1)，其中 m 和 n 是宽度和高度网格和 k_1, ..., k_t 是 t 种不同类型棋子的可用副本数。在实践中，这意味着大于 5*5 的问题将无法解决（至少如果您使用网格的 "obvious" 编码，其中每个单元格成为整数中的一个位；它可能会出现使用更经济的编码，只需要 2^b 位，其中 b 是 最初黑色 单元格的总数，而不是整体单元格的总数）。 （OTOH，如果你准备假装每种类型的作品有无限数量，你只需要存储 2^(m*n) 个答案，因为我们不需要跟踪每个作品有多少piece remain. This may be useful as a quick first check: If the problem cannot be solved even with unlimited numbers of each type piece, then it certainly can't solved with limited numbers of them.)