この問題は間違いなくNP困難であり、私はそれを証明することができます。3-SATからこの問題への削減があります。具体的には、3-SATから、ドミノが1x3であるこの問題のサブ問題への削減です。他の特定のサイズに対して他の削減もあるかもしれませんが、これは間違いなく機能します。
基本的に、この削減では、ドミノ位置を使用してtrueまたはfalseのいずれかをエンコードします。具体的には、他のソリューションと同じ表記法を採用します。つまり、グリッド上のオープンスペースを示すためにアスタリスクを使用します。また、ドミノを表すために3つの大文字のセットを使用し、システムの状態に応じて埋められる場合と埋められない場合があるスペースである「信号」を表すために小文字を使用します。
このスペースに3-SAT問題を埋め込むには、特定の状態のみを可能にするガジェットと呼ばれるもののセットが必要になります。これらのガジェットのほとんどには、固定数のドミノが含まれています。例外は、句がtrue（満たされている）の場合は1つ余分なドミノを持つが、false（満たされていない）の場合はそうではない句を表すガジェットです。パスを使用してこれらのガジェットを相互接続できます。これにより、3SAT回路を構築できます。各パスとガジェットは標準量のドミノを使用するため、基本数のドミノがあります。これらを合計して基本数kを取得します。次に、各句ガジェットは、それがtrueの場合、1つの追加のドミノを持つことができます。節を真にすることができ（したがって、式が満たされる）、n個の節がある場合、ドミノの最大数はn+kになります。そうでない場合、最大数はn+k未満になります。これが削減の基本的な形です。次に、ガジェットについて説明し、例を示します。
他の答えと同様に、特定の変数に対してtrueとfalseをエンコードする2つの位置があります。それで、私は2つの可能な場所にあることができる単一のタイルから始めます。
****
これは、次のような1つのドミノでカバーできます。
AAA* or *AAA
明らかに、これは2つのドミノでカバーすることはできず、0のドミノでカバーすることは決して最大ではありません。私の目的では、値「false」を表す突起と「true」を表す突起の欠如を検討します。したがって、この部分は2つの信号を伝送していると見なすことができます。
x**y
この場合、xまたはyのいずれか1つだけがカバーされるため、信号はxであり、論理はxではないと見なすことができます。私たちの目的では、カバーされているものはどれも偽であり、カバーされていないものは真です。次に、まっすぐな缶の曲がった経路を介して信号を簡単に送信できます。私たちが持っている場合
x*****y
ここでも正確に2つのドミノがあり、xまたはyのいずれかがカバーされますが、両方はカバーされません。
***y
*
*
x
まったく同じ動作になります。したがって、これを使用して、3の増分である長さの長く曲がったパスを作成できます。ただし、使用する可能性のあるすべての長さが3の増分であるとは限らないため、別の距離を移動するには追加のガジェットが必要です。私はこれをフィドラーガジェットと呼んでいます。唯一の目的は、信号をわずかに不均一な距離に移動して、接続を成功させることです。その入力はxから来て、出力はyに行き、それは単に同じ信号を送信します。次のようになります。
***y
*
**x
常に正確に2つのドミノが含まれ、次の2つの方法のいずれかで入力されます。
BBB* ABBB
* A
AAA *AX
ただし、3-SATをモデル化する場合は、これ以上のものが必要です。具体的には、句をモデル化する方法が必要です。これを行うために、句がtrueの場合に1つの追加のドミノをパックできるガジェットがあります。この句は、その入力の1つ以上がtrueの場合にtrueになります。この場合、入力の少なくとも1つが突き出ていないときに、追加のドミノを1つ詰めることができることを意味します。次のようになります。
*x*y*
*
z
わかりやすくするためにそれぞれにパスを追加すると、次のようになります。
* *
* *
* *
*****
*
****
x、y、zがすべてfalseの場合、それらはすべて突起があり、次のように塗りつぶされます。
A B
C D
C D
*C*D*
*
EEEF
残りのドミノA、B、およびFは、どこかのパスを進みます。入力の少なくとも1つが真の場合、次のように1つの追加のドミノ（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
ご覧のとおり、空のスペースに挿入できる追加のドミノは2つではなく、1つだけです。
さて、用語が繰り返されなかった場合、私たちは完了します（またはほぼ完了します）。ただし、それらは繰り返すことができるため、次に、1つの変数が複数の用語で表示されるように信号スプリッターが必要です。これを行うために、次のガジェットを利用します。
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のいずれかが突出するように突出していない場合、これを5つのドミノでパックすることが可能であることに注意してください。ただし、そうすると、真（突出していない）である可能性のある用語が偽（突出）になる可能性があります。一部の用語（変数ではなく、句内の実際の用語）が不必要に偽になることによってのみ値が異なることを許可しても、他の方法では満たされない式を満たすことができるようになることはありません。3-SAT式が（x | y | z）＆（！x | y |！z）の場合、xと！xの両方をfalseにすると、事態はさらに難しくなります。何かの両端が真になることを許可した場合、これは誤った解決策になりますが、このスキームではこれを行いません。私たちの特定の問題の観点からそれを組み立てるために、
パスとこれらの3つのガジェットを使用して、平面3-SATを解決できます。これは、3-SATのサブ問題であり、用語と句が頂点であり、すべての用語とすべての間にエッジがあるグラフを描画すると、その用語を含む節、グラフは平面である。平面1-in-3-SATはそうであるため、平面3-SATはおそらくNP困難であると思いますが、そうでない場合は、ガジェットを使用して信号交差を行うことができます。しかし、それは本当に非常に複雑なので（誰かがもっと簡単な方法を見つけたら、私に知らせてください）、最初にこのシステムで平面3-SATを解く例を行います。
したがって、単純な平面3-SAT問題は（x | y | z）＆（！x | y |！z）になります。明らかに、これは、yが真である任意の割り当て、または他のいくつかの割り当てを使用して、充足可能です。したがって、ドミノの問題を構築します。
*******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
*
*
*
y
物事を正しくスペースに配置するために上部でフィドラーを使用する必要があったことに注意してください。そうしないと、これは実質的にそれほど複雑ではなかったでしょう。
ガジェットとパスからの合計ドミノを合計すると、1つのスプリッター（5つのドミノ）、2つのフィドラー（それぞれ2つのドミノ）、および合計13の通常のパスがあり、合計で5 + 2 * 2 + 13=22のドミノが保証されます、条項が満たされない場合でも。可能であれば、さらに2つのドミノを入力して合計24個にすることができます。24個のドミノを使用した最適なパッキングの1つは、次のとおりです。
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個のドミノが含まれている場合、句の1つが満たされていない（GGGおよび/またはLLLドミノを配置できない）ことがわかります。したがって、元の式が満たされていないことがわかります。満足できる。
平面3-SATがNP困難でなくてもこれを確実に実行できるようにするために、パスが交差できるガジェットを作成できます。このガジェットは残念ながら大きくて複雑ですが、私が理解できた最小のガジェットです。最初にピースについて説明し、次にガジェット全体について説明します。
ピース1：クロスオーバーポイント。xとyは入力です。a、b、およびcは出力です。xとyを実際に互いに反対側に中継するには、他のガジェットを使用してこれらを組み合わせる必要があります。
***c
*
***
* *
* *
* *
***
***
ax*yb
このガジェットは常に正確に7つのドミノに適合します。4つの可能な入力の組み合わせがあります。どちらの入力も突出しない場合（両方とも真）、出力は突出せず、以下の（tt1）または（tt2）のように入力されます。入力xのみが突出している場合、以下の（ft）のようにcのみが突出します。入力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）シナリオで、aまたはbの代わりにcがカバーされる可能性は含めていません。これはこのガジェットの範囲内で可能ですが、他のガジェットと組み合わせて完全なクロスオーバーを形成すると、そうすると、より多くの句が満たされることはないため、除外できます。そのことを念頭に置いて、この場合、入力xの値はb＆cの値に等しく、入力yはa＆cの値に等しいことに注意してください（これは論理的であることに注意してください）。論理的ではなく、突出が偽ではなく真であると見なされた場合）。したがって、cを分割し、論理積とガジェットを使用してcの値をそれぞれaとbに接続するだけで、クロスオーバーが正常に完了します。
論理的で、これまでで最も単純なガジェットであり、次のようになります。
****
*
x*y
クロスオーバーポイントガジェットの上部に埋め込まれているものがあることに実際に気付くかもしれません。このガジェットには、常に正確に2つのドミノが含まれます。1つは、出力として機能する上部になります。もう1つは、次の図に示すように、xとyの両方が真（突出していない）の場合にのみ水平方向に配置され、そうでない場合は垂直方向に配置されるスイッチとして機能します。
BBB* ABBB ABBB ABBB
* A A A
AAA XAy xAY XAY
したがって、cを分割し、これらのゲートを2つ追加することでクロスオーバーを完了することができます。1つはa＆c用、もう1つは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の両側の2つのスペースを削除して修正しました。これにより、6つのドミノパッキングが排除され、xがカバーされていないときにyとzがカバーされていない5つのドミノパッキングが可能になります。