这个问题绝对是 NP 难的，我可以证明这一点。从 3-SAT 减少到这个问题。具体来说，它是从 3-SAT 减少到这个问题的子问题，其中多米诺骨牌是 1x3。其他特定尺寸也可能有其他减少，但这绝对有效。
本质上，在这种简化中，我们将使用多米诺骨牌位置来编码真假。具体来说，我将采用与其他解决方案相同的符号，也就是说，我将使用星号来表示网格上的开放空间。我还将使用三个大写字母的集合来表示多米诺骨牌，并使用小写字母来表示“信号”，这些“信号”是可能会或可能不会根据系统状态填充的空格。
要将 3-SAT 问题嵌入到这个空间中，我们将需要一组我称之为小工具的东西，它们只允许某些状态成为可能。这些小工具中的大多数都会有固定数量的多米诺骨牌。例外情况是表示子句的小工具，如果子句为真（满足），则将有一个额外的多米诺骨牌，但当它为假（不满足）时则不会。我们可以使用路径互连这些小工具。这将使我们能够构建一个 3-SAT 电路。我们将有一个基数的多米诺骨牌，因为每个路径和小工具都将采用标准数量的多米诺骨牌，我们可以将它们相加得到一个基数 k，然后如果它是真的，每个子句小工具可以有一个额外的多米诺骨牌，所以如果所有子句可以为真（因此满足表达式）并且有 n 个子句，那么多米诺骨牌的最大数量将是 n+k。如果不是，那么最大数量将小于 n+k。这是还原的基本形式。接下来我将描述小工具并举例说明。
与另一个答案类似，我们将有两个位置对给定变量编码真假。所以，我将从一个可以在两个可能位置的单个图块开始。
****
这可以用一张多米诺骨牌来覆盖
AAA* or *AAA
显然，这不能用 2 多米诺骨牌覆盖，用 0 多米诺骨牌覆盖它永远不会是最大的。出于我的目的，我们将考虑用突起来表示值“假”，而没有突起来表示“真”。所以我们可以将这部分视为携带两个信号：
x**y
在这种情况下，只会覆盖 x 或 y 中的一个，因此我们可以认为信号是 x 和 x 的逻辑非。就我们的目的而言，凡是涵盖的都是假的，凡是不涵盖的都是真的。接下来，我们可以简单地通过直线可以弯曲的路径传输信号。如果我们有
x*****y
我们将再次恰好有两个多米诺骨牌，并导致 x 或 y 被覆盖，但不能同时覆盖。
***y
*
*
x
将具有完全相同的行为。所以我们可以使用它来创建长度为 3 的长而弯曲的路径。但是，并非我们可能想要使用的所有长度都是 3 的增量，所以我们需要一个额外的小工具来移动不同的距离。我称之为提琴手小工具，它的唯一目的是将信号移动到稍微不均匀的距离以使事物成功连接。它的输入来自 x，输出到 y，它只传输相同的信号。它看起来像这样：
***y
*
**x
它总是恰好包含两个多米诺骨牌，并以以下两种方式之一填充：
BBB* ABBB
* A
AAA *AX
但是，如果我们要对 3-SAT 进行建模，我们需要的还不止这些。具体来说，我们需要一些方法来对子句进行建模。为此，我们有一个小工具，如果该子句为真，则可以在其中打包一个额外的多米诺骨牌。当一个或多个输入为真时，该子句为真。在这种情况下，这意味着当至少有一个输入没有突出时，我们可以添加一个额外的多米诺骨牌。它看起来像这样：
*x*y*
*
z
如果为了清楚起见我们为每个路径添加一个额外的路径，那么它看起来像这样：
* *
* *
* *
*****
*
****
如果 x、y 和 z 都是假的，那么它们都会有突起，并且会像这样填充：
A B
C D
C D
*C*D*
*
EEEF
其余的多米诺骨牌 A、B 和 F 在某处继续前进。如果至少有一个输入为真，那么我们可以像这样打包一个额外的多米诺骨牌 (G)：
C B A D A B
C D C D C D
C D or C D or C D
GGGD* *CGGG *CGD*
* * G
EEEF EEEF GEEE
但是，即使所有输入都为真，我们也不能打包多个多米诺骨牌。这种情况看起来像这样：
C D
C D
C D
*****
*
*EEE
正如你所看到的，我们只能在空白处插入一个额外的多米诺骨牌，而不是两个。
现在，如果条款从不重复，那么我们就完成了（或几乎完成了）。但是，它们可以重复，所以接下来，我们需要一个信号分离器，以便一个变量可以出现在多个术语中。为此，我们使用以下小工具：
y*** ***z
* *
***
***
x
在这个小工具中，x 是输入，y 和 z 是输出。在这个小工具中，我们总是可以打包 5 张多米诺骨牌。如果 x 比包装 5 块多米诺骨牌突出，则始终需要覆盖 y 和 z。如果 x 不突出，则不需要覆盖 y 和 z。x 不突出的包装如下所示：
yAAA BBBz
C D
CED
CED
E
当 x 确实突出时（我们使用 X 表示多米诺骨牌的末端突出到空间 x 中），最大包装必然覆盖 y 和 z：
AAAC DBBB
C D
C*D
EEE
X
我会花一点时间注意，当 x 没有以 y 或 z 突出的方式突出时，可以用五个多米诺骨牌打包它。但是，这样做会导致可能为真（不突出）的术语变为假（突出）。仅通过不必要地变为假来允许某些术语（不是变量，而是子句中的实际术语）在值上有所不同，永远不会导致能够满足否则无法满足的表达式。如果我们的 3-SAT 表达式是 (x | y | z) & (!x | y | !z) 那么让 x 和 !x 都为假只会让事情变得更难。如果我们让某事物的两端都为真，这将导致不正确的解决方案，但我们在此方案中不这样做。根据我们的具体问题来构建它，
有了路径和这三个小工具，我们现在可以解决平面 3-SAT，这将是 3-SAT 的子问题，如果我们绘制一个图，其中术语和子句是顶点，并且每个术语和每个包含该术语的子句，即图形是平面的。我相信平面 3-SAT 可能是 NP 难的，因为平面 1-in-3-SAT 是，但如果不是，我们可以使用小工具进行信号交叉。但它真的很复杂（如果有人看到更简单的方法，请告诉我）所以首先我将做一个用这个系统解决平面 3-SAT 的例子。
因此，一个简单的平面 3-SAT 问题将是 (x | y | z) & (!x | y | !z)。显然，这是可以满足的，使用 y 为真的任何赋值或其他几个赋值。我们将这样构建我们的多米诺骨牌问题：
*******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
*
*
*
y
请注意，我们必须在顶部使用提琴手来正确分配空间，否则这将大大降低复杂性。
将来自小工具和路径的多米诺骨牌总数相加，我们有 1 个拆分器（5 个多米诺骨牌）、两个提琴手（每个 2 个多米诺骨牌）和总共 13 个常规路径，总共保证 5 + 2*2 + 13 = 22 个多米诺骨牌，即使不能满足条款。如果可以的话，那么我们将有 2 个多米诺骨牌，总共可以填充 24 个。24 个多米诺骨牌的最佳包装如下：
QRRRSSS
Q T
Q T
OPPP *UT
O U
*ON UVVV
N W
N W
M IIIJJJK W
M H K X
M H K X
*zGH* LLLX*
G *
GEEE FFF*
B D
BCD
BCD
C
A
A
A
这个平铺包含24个多米诺骨牌，因此我们可以知道原始表达式是可满足的。在这种情况下，平铺对应于使 y 和 x 为真而 z 为假。请注意，这不是唯一的平铺（也不是唯一令人满意的布尔值分配），但没有其他平铺可以增加超过 24 个的平铺，因此它是最大平铺。（如果你不想计算所有的多米诺骨牌，你可以注意到我使用了除 Y 和 Z 之外的所有字母。）
如果最大平铺包含 22 或 23 个多米诺骨牌，那么我们将知道其中一个子句不满足（无法放置 GGG 和/或 LLL 多米诺骨牌），因此我们将知道原始表达式不满足可满足。
为了确定即使平面 3-SAT 不是 NP 难的，我们也可以做到这一点，我们可以构建一个允许路径交叉的小工具。不幸的是，这个小工具有点大而且复杂，但它是我能弄明白的最小的。我将首先描述这些部件，然后再描述整个小工具。
第 1 部分：交叉点。x 和 y 是输入。a、b 和 c 是输出。它们将需要使用其他小工具进行组合，以将 x 和 y 实际传递到彼此的另一侧。
***c
*
***
* *
* *
* *
***
***
ax*yb
这个小工具总是正好适合 7 块多米诺骨牌。有四种可能的输入组合。如果两个输入都没有突出（两者都为真），则没有输出将突出，并将填充如下（tt1）或（tt2）。如果只有输入 x 突出，那么只有 c 会突出，如下面的 (ft) 所示。如果只有输入 y 突出，则输出 a 或 c 将突出，如下面的 (tf) 所示。如果输入 x 和 y 都突出，则输出 c 突出，如下面的 (ff) 所示。
(tt) AAAc (ft) AAAc (tf) AAAc (ff) BAAA
* * * B
BBB BBB BBB CBD
C D C D C D C D
C D C D C D C D
C D C D C D E G
EEE EEE EEE EFG
FFF FFF FFF EFG
aGGGb aXGGG GGGYb aXFYb
我没有包括在 (ft) 或 (tf) 场景中可以覆盖 c 而不是 a 或 b 的可能性。这在这个小工具的范围内是可能的，但是一旦与其他小工具组合形成完整的交叉，如果这样做，它将永远不会导致大量的子句被满足，因此我们可以排除它。考虑到这一点，我们可以观察到，在这种情况下，输入 x 的值等于 b & c 的值，输入 y 等于 a & c 的值（请注意，这将是合乎逻辑的，或者更确切地说而不是逻辑，如果突出被认为是真实的而不是虚假的）。所以我们只需要将 c 拆分，然后使用逻辑和小工具将 c 的值分别与 a 和 b 连接起来，我们就可以成功完成交叉。
逻辑 and 是迄今为止我们最简单的小工具，它看起来像这样：
****
*
x*y
您实际上可能会注意到，交叉点小工具的顶部嵌入了一个。此小工具将始终包含恰好 2 个多米诺骨牌。一个将在顶部作为输出。另一个用作开关，只有当 x 和 y 都为真（不突出）时才会水平定向，否则垂直定向，如下图所示：
BBB* ABBB ABBB ABBB
* A A A
AAA XAy xAY XAY
因此，我们可以通过拆分 c 然后添加其中两个门来完成交叉，一个用于 a 和 c，一个用于 b 和 c。将它们放在一起还需要添加一些提琴手小工具，如下所示：
******* ****
* * * *
* *** *
*** *** ***
* * *
**** * ****
* * *
* **** *
*** * ***
* *** *
**** * * ****
y * * * * x
* * * * * *
* **** *** **** *
*** *** ***
**********x*y*************
我不会为此填写示例平铺。如果你想看到它的实际效果，你必须自己做。所以，万岁！我们现在可以做任意的 3-SAT。我应该花点时间注意，这样做将是一个多项式时间变换，因为即使在最坏的情况下，我们也可以制作一个大网格，上面有所有变量及其对立面，所有项都在旁边，然后做O(n^2) 次交叉。因此，有一个简单的多项式时间算法可以解决所有问题，并且转换后的问题的最大大小是输入问题大小的多项式。QED。
编辑说明：在汤姆·西尔格达斯 (Tom Sirgedas) 出色地发现拆分器小工具中的错误之后，我对答案进行了一些更改。本质上，我的旧分离器看起来像这样，并且当 x 不突出时（而不是我想要的 5）可以装满 6，如下所示：
y*** ***z AAAC DBBB
* * C D
*** C*D
*** EEE
*x* FFF
所以我通过删除 x 两边的两个空格来修改它。这消除了 6 个 domino 包装，同时仍然允许 5-domino 包装，其中当 x 未被覆盖时，y 和 z 未被覆盖。