この数独、解が二つあるのはなぜ？
現実に考えられる四つの原因、必ず二つ目の解を生む長方形の形、17 という有名な数字が何を言っているのか、そしてソルバーが実際に何を確かめているのか。
数独が問題として成立するのは、解がちょうど一つのときだけです。これは好みの問題ではなく、推論が成り立つための条件です。異なる二つの完成盤がどちらもヒントと矛盾しないなら、どこかで必ず、どちらへ進むべきかを論理が教えてくれない地点に来ます。そこから先は、片方を選んで様子を見るしかありません。
その状況に行き当たったとき、現実的な原因は四つあります。
一、前のどこかで間違えている
これが圧倒的に多く、しかもうまく化けます。二十手前に置いた誤りは、その場で矛盾を起こしてはくれません。代わりに、二つのマスが入れ替え可能に見える局面を作ります。その二つを区別していたはずの制約が、誤った数字によって壊されているからです。
確かめるのは簡単です。自分で入れた数字を一つずつ、行・列・ブロックの規則に照らして見直します。同じユニットに同じ数字が二回現れていれば、それが答えで、問題のほうには何の落ち度もありません。ミスを色で示すアプリならその場で分かりますが、紙なら手で確かめるしかありません。
二、致命的長方形
これは本当に解が二つになることを保証する形なので、見分けられるようにしておく価値があります。
四つのマスが長方形の四隅にあるとします。二つの行、二つの列、そしてここが肝心ですが、またぐブロックはちょうど二つ。さらにその四マスがすべて空で、どれも同じ二つの数字、たとえば 2 と 5 しか入らないとします。
このとき、どんな解が出てきても、四隅をまとめて入れ替えられます。長方形上の 2 をすべて 5 に、5 をすべて 2 に。どの行にも両方が一つずつ残り、どの列にも一つずつ残り、二つのブロックにも一つずつ残ります。各ブロックが長方形の一辺をまるごと抱えているからです。盤面の他の場所には何も触れません。だから、まったく同じだけ正しい二つ目の解が必ず存在します。
ブロックが二つ、という条件こそがこれを成立させています。四隅が四つの異なるブロックに散っている場合、入れ替えはブロックの制約を壊すので、この形は無害です。
慣れた人はこれを逆向きに使います。一意性が保証された問題なら致命的な形は起こりえないので、それを作ってしまう候補のほうを消せる、という理屈です。ただしこの推論は、その問題が本当に検証済みである場合にしか成り立ちません。だからこれは近道であって、手筋ではありません。
三、ヒントを消しすぎた
自分で問題を作った場合や、完成盤から数字を抜いていった場合、解の一意性は自動的には守られません。一マス空けるたびに制約を一つ削っているのに、線を越えたその瞬間には何の警告も出ません。
知られている下限は 17 です。2012 年、McGuire、Tugemann、Civario による全数コンピュータ探索によって、ヒント 16 個で解が一つになる数独は存在しないことが確定し、ヒント 17 個の問題は実在することが示されました。
この結果が何を言い、何を言っていないかに注意してください。17 は問題全体の空間についての床であって、個々の問題についての保証ではありません。ヒント 17 個の配置のほとんどは解がいくつもありますし、25 個の配置にも複数解のものは大量にあります。個数はほとんど何も教えてくれず、数えることだけが教えてくれます。
四、生成器がそもそも検証していない
無料の盤面印刷サイト、古いアプリ、よそから拾ってきた問題集など、ヒント数の目標に届くまで穴を掘って、そのまま出荷している供給元があります。一意性の検証には本物の計算が要るので、省いてもプレイヤーが曖昧な局面に突き当たるまで表には出ません。そしてそのときプレイヤーは、たいてい自分のミスだと思い込みます。
本物の検証はどう動くのか
一意性を確かめるとは、解を一つ見つけることではなく、解を数えることです。ソルバーは普段どおり探索しますが、最初の完成盤で止まらずにそのまま続けます。これを安く済ませるコツが早期打ち切りです。合計は必要なく、一つなのか二つ以上なのかだけ分かればよいので、数える上限を二にして、二つ目が見つかった瞬間に探索をやめます。
Sudoku - Calm Number Puzzle は、これを一回掘るたびに行います。マスは対称な二つずつ取り除かれ、取り除くたびにソルバーが上限二で解を数えます。ちょうど一つでなければ、その二マスはすぐ埋め戻され、生成器は別の場所へ移ります。検査に落ちた問題はあなたのところまで届かないので、このアプリで曖昧な局面に見えたなら、原因は必ず一番目です。
短いチェックリスト
- 二つのマスが入れ替え可能に見える → まず自分の入れた数字に重複がないか確かめる。
- 空の四隅、二つの行、二つの列、二つのブロック、共通の二つの候補 → 致命的長方形。その問題は本当に解が二つある。
- ヒントを自分で消した → 何も仮定せず、解の個数を数える。
- 印刷物や出所の分からない盤面 → 供給元が一度も検証していない可能性がある。
よくある質問
解が一つの数独に必要な最小のヒント数はいくつですか
十七です。2012 年の McGuire、Tugemann、Civario による全数探索が、ヒント 16 個で解が一つの数独は存在しないことを示し、ヒント 17 個の正しい問題は知られています。これは問題空間全体についての床であって、特定のヒント 17 個の配置が自動的に備える性質ではありません。
解が二つある問題でも解けますか
埋め終えることはできますが、推論しきることはできません。どこかで、どちらも矛盾しない二つの選択肢を、どちらを選ぶ理由もないまま選ぶことになります。多くの人はその時点で数独ではなくなると考えます。
解が一つかどうかを見分ける方法はありますか
ソルバーで解を数えるしかなく、目で見て判定する方法はありません。唯一の例外が致命的長方形です。二つの行、二つの列、二つのブロックにまたがる四隅の空マスが、どれも同じ二つの候補数字だけを持っていれば、それ以上調べなくても解は二つ以上あります。
このアプリで解が二つある問題が出ることはありますか
ありません。生成中は一マス取り除くごとに一意性を検査し、それを壊す除去はその場で取り消されます。一意でない問題は完成すらしませんし、まして表示されることはありません。
実際の問題で試す
Sudoku - Calm Number Puzzle は、解くのに実際に必要な一番難しい手筋で難易度を決め、盤面を見せる前に解が一つであることを検証し、ヒントでは数字を埋めるだけでなく手筋の名前を答えます。無料、オフライン、広告なし、アカウントなし。