チェインとリンクの話

Tips

混乱してきたので

パズルを解いててたまに出てくるチェインの考え方。自分もたまに使うのですが、ここで用語について改めてまとめておきます。

 

コンセプト

チェインとは、命題の真偽を連鎖させることでいくつかのマスの真偽を確定させる手法のことです。ここで使う「命題」は、たとえば

・ある特定のマスにある特定の数字が入る (e.g. 数独など数字埋め)

・ある特定のマスを塗る (e.g. Tapaなど塗るパズル)

といったものです。

用語の定義

2つの命題の真偽の関係を表したものがリンク (link) です。リンクにはいくつか種類があります。説明のため、2つの命題をA, Bとおきます。

弱リンク (weak link) とは「A, Bが共に真にならない」=「not A or not B」= "NAND" のことです。Aが真とわかったとき、Bが偽になることが演繹できます。

強リンク (strong link) とは「A, Bが共に偽にならない」=「A or B」= "OR" のことです。Aが偽とわかったとき、Bが真になることが演繹できます。

場合によっては強かつ弱 (strong and weak) とわかることもあります。この場合は「AとBのちょうど一方が真」= "XOR" です。

(なお、文脈によっては別の定義をすることもありますが、この記事では今の定義で統一しておきます。)

これらのリンクをつなげたものがチェイン (chain) です。チェインで大事なのは弱リンクと強リンクが交互にくるもので、それが見つかると議論が進みます。

例として、命題A, B, CについてAとBが弱リンク、BとCが強リンク、CとAが弱リンクでつながっているとします。このとき、Aは偽とわかります。なぜなら、もしAを真とすると、さっきの演繹により真偽が交互に伝わり、一周回ってAが偽となって矛盾するからです。この議論は、チェインがもっと長くなっても同様のことが言えます。一般に、長さ奇数で強弱が交互にくるチェインでループができると、開始地点の命題 (強弱が一致する場所) の真偽が確定します。長さが偶数でも、全てのリンクが強かつ弱に昇格します。

具体例

 数独についての過去の記事：

sp1-puzzle.hatenadiary.jp

Tapaでの具体例：