三角形ガジェット

https://gyazo.com/6f844198960a087fcdd4114174401c13

https://scrapbox.io/files/649f82443ebca7001b9044c1.png

https://gyazo.com/c729f4d074acf120ca34fc78681aa2a7

三角形を見つけさえすれば着色候補を 2 通りまで絞れると考えればかなり使い勝手が良い

しかも、片方は true, false が確定するのでダメかどうかすぐに分かる

controled equality

https://scrapbox.io/files/66531e721cbb35001c42d8cf.png

上を equality の選択とみなす

true の時は下 2 つが等しいときに SAT

false の時は下 2 つが異なるときに SAT

つまり、定数割当を一旦無視するやり方

https://scrapbox.io/files/66502acb98da3d001da9c5d5.png

定数割当も考慮すると他に 3 パターンあるが、簡単化のために無視している

わかりやすいように「？」を書くか

とりあえずの 3 色割当のほうが多くなるはずなので、シンプルな記法の方が良い

3 色割当が確定したときに二重線で書くか

not が波線なので、書きづらそう

内部のゴチャゴチャした部分を打ち消して外側に 3 つ生えた辺変数がトライフォースの振る舞いをする

https://scrapbox.io/files/66510fc1223bcd001c1289db.png

定数割当

https://scrapbox.io/files/6651108302fe02001cb89d59.png

外側の辺変数に着目すると 3 色割当と同じ

https://scrapbox.io/files/6651117a6aa5a8001d66950c.png

外側の辺変数に着目すると定数割当と同じ

他の多角形になるとどうなるか？

一般形

囲んでいないが、両端を接続することで同様に考えられる