数独日誌140323

【背理法と私の解き方について】
   今私が使える手筋の中で、Simple ChainとXY-Chainについては背理法を使って探しています。（今回は長文でスミマセン）

【Simple Chain】
   私の場合、序盤、各ブロックについて、数字Aが入るマスが２つまで絞れた場合、Aをそのマスに小さく書き込むというやり方をしていますが、例えば数字１について調べた時、図１のようになったとします。図では左上、中上、左中、中中ブロックのみ書いてあります。１と書いてあるマスが、数字１が入る可能性のあるマスです。

図１
001 010
010 001
000 000

010 001
000 000
001 011

   図１で中中ブロックだけ、１が３か所書いてありますが、実はSimple Chainによりr6c6には１が入りません。つまり、ここからが背理法になりますが、r6c6に１が入るとすると、中上ブロックではr1c5が１、左上ブロックではr2c2が１、左中ブロックではr6c3が１となり、第６行（r6）に１が２つ入ってしまい、矛盾します。よってr6c6から１を除外できます。

次のようなタイプもあります。
図２
001 010
010 001
000 000

010 011
000 000
001 001

   図１と同じように考えるとr6c6から１が除外できて、中中ブロックで１の入る可能性のあるマスはr4c56のみとなります。この結果、１が入るのは左中ブロックではr6c3のみ、左上ブロックではr2c2のみ、中上ブロックではr1c5のみ、結局中中ブロックでもr4c6に１が入ることが確定します。この場合はSimple Chainで４つのブロックの１の場所がすべて確定します。

   最近やった世界文化社「超上級編31」の87番は、５つの数字についてSimple Chainを探しただけで解けてしまいました。（図１のタイプも図２のタイプもあったと思います）

【XY-Chain】
   私が背理法を使って探しているもうひとつの手筋がXY-Chainです。これは昔の記事にあるやりとりを、少し長いですが、再録したいと思います。私の疑問をヅケさんに回答していただいたものです。（数独日誌100924より　ヅケさんは激辛数独などのペンネームでは福神ヅケさんです）

   まず私の記事から
『XY-Chainは言葉では少し説明しにくいですが、例えば12,23,34,45,51という２択マスが５つ連鎖していたとします。１からスタートしてまた１に戻る感じです。この５つのうち１番目のマスと５番目のマスが同じ行（or列orブロック）にある場合、その行（or列orブロック）の１番目と５番目以外のマスから１を排除できる、という理論だと思います。なぜなら１番目と５番目以外のマスに１が入ると、１番目のマスは２、２番目のマスが３、・・・最後の５番目のマスが１となり、１つの行、列、ブロックに１が二つ存在してしまうからです。

   １番目のマスと５番目のマスが同じ行（or列orブロック）にない場合は、１番目のマスと５番目のマスの交差点のマスから同じ理由で１が排除できます。

   ところが前にXY-Chainを探していたところ、うまく探せず、次のように考えたものをXY-Chainとして解答メモに書いたことを思い出しました。同じような設定で12,23,34,45,52という２択マスが５つ連鎖していたとします。ここで１番目のマスに２が入るとすると、２番目のマスは３、・・・最後の５番目のマスが２となります。ここで１番目のマスと５番目のマスが同じ行（or列orブロック）にあると２が二つ存在して矛盾するので、１番目のマスには２は入らず、１で確定する、というものです。

   背理法（仮定法）と言ってしまえばそれまでですが、何か浜田ロジックの自己完結型という感じがしないでもないです。ミシチャンさんのHPを見ても、こんな手筋は特に記述はないようです。Sudopediaはまだ調べていませんが、これは何か名前のある手筋でしょうか？』

   この疑問について、ヅケさんから回答をいただきました。
『まず、ikachanさんが最初に挙げた[12]～[51]までの例は、 両端のマスが同一領域内にあるという条件なのでXY-cycle。(XY-chainの特殊ケース、ミシチャンさんサイトだとXY-chain（連続ループ））

   で、２つ目の例ですが、
[23]～[52]までの４マスでXY-chainが成立し、[23]マスと[52]マスの共通ピアにある[12]マスから数字2（両端のマスの共通の候補）を排除するイメージですね。 （ミシチャンさんサイトだとXY-chain（不連続ループ））

   後者の方がより一般的で、最も単純な例はXY-wingです。XY-wing（[ZX]-[XY]-[YZ]で両端のマスの共通ピアから共通候補Zを排除）の３マスを１マス増やして４マスにしたイメージ と言えば分かり易いでしょうか？』

   で、私の返事が、
『ヅケさんへ
コメントありがとうございます。XY-Chainが成り立っていたんですね。私にとっては目からウロコという感じでした。

   私には２つの数字の連鎖をたどって最初の数字に戻る、という形より、２番目の例のように、１つのマスに１つの数字が決まる、という形にしたほうがXY-Chainは探しやすいように思いました。』

   一番最後に書いてあるように、マスXに数字Aが入るとして、２択マスを辿って、１つのマスに１つの数字が入ることを続けていくと、矛盾が起こる、よってマスXに数字Aは入らない、というやり方で探しています。つまり背理法です。

   マスXに数字Aが入ると矛盾が起こる、というのと、ある手筋でマスXから数字Aが除外できる、というのは表裏の関係にあると思います。

   ミシチャンさんのSimple Chainの説明にも背理法との関係の記述がありますが、ある手筋を探すのに背理法を使うというのは許容範囲ではないか、と考えているのですが、皆さんはどうお考えですか？