数独で勘に頼ってもいいのか
コンピュータの言う「推測」とは何か、人がやる推測がなぜ別物なのか、正当な場合分けとはどういうものか、そして「試行錯誤が要る問題」の本当の意味。
数独のルールに、推測を禁じる条項はありません。ルールは各数字が行・列・ブロックに一度ずつ現れると言っているだけです。推測は反則ではなく、ただ見た目よりずっと悪い道具だというだけ。その理由をはっきりさせておく価値はあります。
混乱の元は、コンピュータが数独をほぼ推測で解き、しかもきわめて強い、という事実です。機械がやっていることと、人が「一つ書き込んでみる」ことは、同じ行為ではありません。
コンピュータの解き方
標準的なアルゴリズムはバックトラック探索です。可能性が最も少ない空マスを見つけ、候補の一つを試し、その帰結を伝播させ、先へ進む。矛盾に達したらその選択を取り消して次の候補へ。全部だめなら、その一つ前の選択も取り消す。
重要な性質は二つ。機械はどの選択の直前の局面も正確に覚えていること、そして探索が網羅的であること。誤った推測で失うものは何もありません。いつでも元の場所へ正確に戻れるからです。解が存在するなら、試し尽くせば必ず見つかります。
解の個数を数えるのも同じ仕組みで、一点だけ違います。最初の完成盤で止まらず、そのまま続ける。一意性の確認に総数は要らず、「一つ」か「二つ以上」かだけが分かればいいので、数える上限を二に設定し、二つ目が見つかった瞬間に探索を打ち切ります。Sudoku - Calm Number Puzzle が生成中、マスを取り除くたびに走らせているのがこれです。
人がやる推測は別のこと
人が推測するとき、いま挙げた性質は一つも成り立ちません。推測前の盤面の正確なスナップショットは手元になく、あるのは数字が一つ増えた紙だけ。矛盾が現れるころには、その上にさらに二十個の数字が書かれています。正確に巻き戻すのは難しく、間違えやすい。
さらに厄介なのは、矛盾がすぐには来ないことです。誤った数字は長いあいだ何とも矛盾せず、その帰結が静かに盤面へ広がります。ようやく壊れたとき、当時の推測が外れたのか、その後の普通のミスなのかを区別できません。
つまり人が推測しているとき、それは探索ではありません。矛盾より先に盤面が終わることに賭けているのです。この賭けこそ、あと少しで終わる数独を壊す最大の原因です。
正当な版：最後まで詰める場合分け
完全に健全な仮定的推論もあり、上手い人ほど日常的に使っています。違いは、どの分岐にも身を委ねないこと。全部の分岐を評価します。
候補が二つのマスを選び、まず片方だと仮定して帰結をたどる。矛盾に当たるか、何かが分かるまで。次に、盤面には何も書かずに、もう片方でも同じことをする。有用な結果は二種類あります。
- 一方の分岐が矛盾を生む。ならその候補は不可能で、もう一方が証明された——これは背理法であって推測ではありません。
- 両方の分岐が、別の場所で同じ事実を強制する。ならその事実はどちらにせよ真で、どちらの分岐が本物かを知らないまま書き込めます。
二つ目がまさに XY-Wing です。軸は X か Y で、どちらにせよ挟みのどちらかが Z になるので、二つの挟みが同時に見ているマスから Z を消せる。ウィング系やチェーン系の手筋はすべて、包装された場合分けです。片方だけでなく両方の分岐を最後まで運んだ仮定、というだけのこと。
実践的な規則は単純です。仮定について考えるのは構わない。仮定を盤面に書き込んで祈るのはだめ。両方の分岐を抱えられないなら、候補がちょうど二つのマスに限定し、分岐を短く保ってください。
本当に推測が必要な問題はあるのか
それはソルバーの手筋リストがどこで止まっているかで決まります。まともな数独はどれも解が一つで、原則としてどの一手も何らかの推論の連鎖で正当化できます。ただしその連鎖は、人が追えば実質的に探索になるほど長くなりえますし、名前のついた手筋の有限のリストがそのすべてを覆うことはありません。
つまり「推測が必要」の実際の意味は「我々が実装していない何かが必要」です。手筋で格付けされたよくできた問題では、その境界は意図的に引かれています。このアプリでは、むずかしいまでの各段階がその帯の手筋の範囲で解けることを検証済みなので、推測は決して必要になりません。試行錯誤が要ってよいのはエキスパートだけで、そこでも生成器は純粋な論理で解ける問題を優先し、どうしても見つからないときにだけ譲ります。どちらにせよ解は一つのままです。
推測したくなったら、別のところが問題
きちんと格付けされた問題で推測に手が伸びるのは、戦略ではなく信号です。たいていは次の三つのどれかです。最後に確定させて以降、安い手筋を回し直していない。その帯の手筋のどれか一つをまだ知らない。あるいは盤面にすでに誤った数字があり、推論が存在しない。
各行・各列・各ブロックの重複を確認すれば一分で三つ目が消えます。残る二つは、安い手筋から始めて確定のたびに先頭へ戻る順序で片付きます。
よくある質問
コンピュータは論理で解いているのですか、推測で解いているのですか
主に推測です。バックトラック探索という形で、候補を試し、伝播させ、矛盾したら取り消します。機械が直前の局面へ正確に戻れて、すべての分岐を尽くせるから成立します。高速化のために人間の手筋を先に回すソルバーもありますが、答えを保証しているのは探索です。
推測が必要な問題は出来が悪いのですか
必ずしもそうではありませんが、最上位以外では体験としてよくありません。多くの場合、推論が存在しないのではなく、格付け側が実装していない手筋が必要だというだけです。本当に解が一つでない盤面は、別の、もっと深刻な問題です。
推測と場合分けの違いは何ですか
推測は一つの分岐に決めて進みます。場合分けはすべての分岐を評価し、全分岐で成り立つ結論だけを出すか、矛盾する分岐を消します。前者は盤面を壊しうる行為で、後者はただの論理です。
外れた推測は取り消せますか
スマホでは取り消せます。取り消しは盤面と候補数字を、周辺マスから消えた候補も含めて戻します。紙では記憶から復元することになり、だからこそ紙の推測は致命傷になりがちです。
実際の問題で試す
Sudoku - Calm Number Puzzle は、解くのに実際に必要な一番難しい手筋で難易度を決め、盤面を見せる前に解が一つであることを検証し、ヒントでは数字を埋めるだけでなく手筋の名前を答えます。無料、オフライン、広告なし、アカウントなし。