这个问题绝对是NP难题，我可以证明这一点。从3-SAT减少到这个问题。具体来说，这是从3-SAT减少到此问题的子问题的问题，在该问题中，多米诺骨牌为1x3。对于其他特定大小，可能还会有其他减少，但是此方法肯定有效。

本质上，在这种减少中，我们将使用多米诺骨牌位置来编码true或false。具体来说，我将采用与其他解决方案相同的表示法，也就是说，我将使用星号表示网格上的开放空间。我还将使用由三个大写字母组成的集合来表示多米诺骨牌，并使用小写字母来表示“信号”，它们是根据系统状态可能填充也可能不填充的空格。

要将3-SAT问题嵌入该空间，我们将需要一组我称之为小工具的小工具，这些小工具仅允许某些状态成为可能。这些小工具中的大多数都将具有固定数量的多米诺骨牌。代表子句的小工具是个例外，如果该子句为真（满足），则为一个多米诺，但如果为假（不满足）则为一个。我们可以使用路径互连这些小工具。这将使我们能够构建一个3-SAT电路。我们将有一个基本的多米诺骨牌，因为每个路径和小工具都将使用标准数量的多米诺骨牌，我们可以将它们加起来得到一个基本数字k，然后每个子句小工具都可以有一个额外的多米诺骨牌（如果为真），所以如果所有可以使子句为真（因此满足表达式），并且有n个子句，则多米诺骨牌的最大数量为n
+ k。如果不是，则最大数量将小于n + k。这是减少的基本形式。接下来，我将描述这些小工具并给出示例。

与其他答案类似，我们将在两个位置上为给定变量编码true和false。因此，我将从一个可以位于两个可能位置的图块开始。

****

这可以用一个多米诺骨牌覆盖

AAA* or *AAA

显然，不能用2个多米诺骨牌覆盖它，而用0个多米诺骨牌覆盖它永远不会是最大的。出于我的目的，我们将考虑使用突出表示“ false”的值和缺少突出表示“
true”的值。因此，我们可以将此部分视为承载了两个信号：

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建模，我们需要的还不止这些。具体来说，我们需要某种方式对子句进行建模。为此，我们有一个小工具，如果该子句为true，则可以在其中填充一个额外的多米诺骨牌。当一个或多个输入为true时，此子句为true。在这种情况下，这意味着当至少一个输入不突出时，我们可以打包一个额外的多米诺骨牌。它看起来像这样：

*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

但是，即使所有输入都正确，我们也不能打包多个Domino。该情况如下所示：

 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突出时，可以用五个多米诺骨牌包装它。但是，这样做将导致可能为真（不突出）的术语变为错误（突出）。只允许某些术语（不是变量，而是子句中的实际术语）仅通过不必要地变为false来实现值的差异，决不会导致能够满足否则无法令人满意的表达式。如果我们的3-SAT表达式是（x
| y | z）＆（！x | y
|！z），那么将x和！x都设为false只会使事情变得更难。如果我们允许某个事物的两端都是真实的，这将导致错误的解决方案，但是在此方案中我们不这样做。要根据我们的特定问题进行构架，

使用路径和这三个小工具，我们现在可以求解平面3-SAT，这将是3-SAT的子问题，如果我们绘制一个图形，其中术语和从句是顶点，并且每个术语与每个子句之间都存在一条边包含该术语的子句，表明图形是平面的。我相信平面3-SAT可能是NP硬的，因为平面1-in-3-SAT是，但是如果不是，我们可以使用小工具进行信号穿越。但这确实很复杂（如果有人看到更简单的方法，请告诉我），因此首先我将举一个使用该系统求解平面3-SAT的示例。

因此，一个简单的平面3-SAT问题将是（x | y | z）＆（！x | y
|！z）。显然，使用y为true的任何赋值或其他几个赋值，这都是可以满足的。我们将这样构建我们的多米诺骨牌问题：

    *******
    *     *
    *     *
 ****   ***
 *       *
***      ****
  *         *
  *         *        
  * ******* *
  * *     * *
  * *     * *
 *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设为true，将z设为false。请注意，这不是唯一的切片（也不是布尔值的唯一令人满意的分配），但是没有其他切片会增加切片的数量，使其超过24，因此这是最大切片。（如果您不想计算所有的多米诺骨牌，可以注意到我用了每个字母，除了Y和Z。）

如果最大平铺包含22个或23个多米诺骨牌，那么我们将知道不满足其中一个子句（将无法放置GGG和/或LLL多米诺骨牌），因此我们将知道原始表达式不可以满足的。

为了确保即使平面3-SAT并非NP-
hard，我们也可以做到这一点，我们可以构建一个允许路径交叉的小工具。不幸的是，这个小工具虽然又大又复杂，但它是我能发现的最小的小工具。我将首先描述各个部分，然后再描述整个小工具。

片段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，然后使用逻辑和小工具分别将a和b的c值连接起来，就可以成功完成交叉。

到目前为止，逻辑和是我们最简单的小工具，它看起来像这样：

  ****
  *
 x*y

您可能实际上注意到，在交叉点小工具的顶部嵌入了一个。这个小工具将始终精确包含2个多米诺骨牌。一个将在顶部充当输出。另一个开关用作开关，仅当x和y均为true（非突出）时才水平放置，否则将竖直放置，如下图所示：

 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两侧的两个空格对其进行了修订。这样就消除了六个多米诺骨牌包装，同时仍然允许在x和x覆盖时不覆盖y和z的5-domino填充。