No.483

2-SAT 問題に帰着させる.

あるマッチ棒が, 右側/下側に頭薬が付いている向きを true とする.

ある頂点の上下左右にマッチ棒がある場合, それらの向きを $a_u, a_r, a_d, a_l$ とすると, これらは以下を満たす必要がある.

$$(\overline{a_u} \lor a_r) \land (\overline{a_u} \lor a_d) \land (\overline{a_u} \lor \overline{a_l}) \land (a_r \lor a_d) \land (a_r \lor \overline{a_l}) \land (a_d \lor \overline{a_l})$$

これをすべての頂点について調べて, 2-SAT を解く.