数独の答えは1つだけ：唯一解と最少ヒント数17
Hiroki Obara · Developer
数独のルールは、9×9のマスに1から9を入れ、どの行にも、どの列にも、どの3×3のブロックにも同じ数字が入らないようにする、というものです。ルールそのものは ナンプレのルール に書きました。
ルールには書かれていませんが、ちゃんと作られた数独の問題には、もう一つの約束があります。答えが1つだけ、ということです。これを「唯一解」といいます。この記事では、唯一解と、そこから出てくる「ヒントは最低でも17個いる」という数学の結果について書きます。
唯一解とは
ヒント（最初から入っている数字）が少なすぎると、ルールを守る埋め方が何通りもできてしまいます。極端な例では、ヒントが一つもない空の盤面は、ルールを守る埋め方が膨大にあります。英語版 Wikipedia の Mathematics of Sudoku によれば、ルールを満たす9×9の完成盤面は、全部で約 6.67×10²¹ 通りあります。
ヒントを置いていくと、その数がどんどん減っていきます。そして、ちょうど1通りになったところで、問題として成り立ちます。答えが1つしかない問題を、英語では proper（正しい）な問題と呼ぶこともあります。
唯一解が解き方にどう関わるか
私は、唯一解であることが、数独を「推理のパズル」にしている一番の理由だと考えています。
答えが1つなら、どのマスの数字も、ヒントから論理だけで決まるはずです。初心者が最初に覚える手筋は、どれも「このマスにはこの数字しか入らない」「この数字はこのマスにしか入らない」と決める考え方です。答えが2通りある問題では、どこかで「どちらでもよい」マスが残り、論理では先に進めなくなります。そのときは、当てずっぽうに選ぶしかありません。
上級者向けには、唯一解であることそのものを使う手筋もあります。たとえば、二つの行と二つの列が交わる4マスが、ちょうど2つのブロックにまたがっていて、その4マスに同じ2つの候補だけが残る形があったとします。その4マスは、2つの数字をどちらの向きに入れてもルールを満たすので、そのままでは答えが2通りになってしまいます。答えは1つのはずなので、そうならない候補を選ぶ、という考え方です。英語では「ユニークレクタングル」と呼ばれています。
ヒントは最少で17個
では、唯一解になる問題は、ヒントがいくつあれば作れるのでしょうか。
ヒントが17個で唯一解になる問題は、昔から見つかっていました。収集されている17個の問題は、数万個にのぼります。けれど、16個のものは、どれだけ探しても見つかりませんでした。16個の問題は存在しないのか、まだ見つかっていないだけなのか。これは長いあいだ、未解決の問題でした。
2012年に、アイルランドのゲイリー・マクガイアらが、論文 There is no 16-Clue Sudoku を発表しました。本質的に異なる完成盤面（数字の入れ替えや回転などで同じになるものを1つと数えたもの）は約54億7千万通りあり、そのすべてについて、16個のヒントで唯一解になる置き方がないことを、コンピュータで調べつくしたものです。論文は2014年に学術誌に掲載されました。これで、唯一解になる数独のヒントは最少で17個だと分かりました。
手で考えて証明する方法ではなく、すべての場合を調べる方法です。4色定理の証明もそうでしたが、数学には、こうして計算機の力で決着がついた問題がいくつかあります。
少なくとも8種類の数字がいる
ヒントの数とは別に、もう一つ簡単に分かる決まりがあります。唯一解の問題では、ヒントの中に1から9のうち少なくとも8種類の数字が入っていなければなりません。
理由は短く説明できます。もしヒントに3と7がどちらも1つも入っていなければ、答えの盤面の3と7をすべて入れ替えても、ルールは守られたまま、ヒントとも矛盾しません。つまり答えが2通りになります。ヒントに出てこない数字が2種類あると、唯一解にはなりません。
ヒントが少ないほど難しいのか
ヒントが少ないほど難しそうに見えますが、私は、ヒントの数と難しさはあまり関係がないと考えています。17個の問題でも、初心者の手筋だけで解けるものがあります。逆に、ヒントが30個近くあっても、上級の手筋が必要な問題もあります。
難しさを決めるのは、ヒントの数ではなく、解くのにどんな手筋が必要かです。そのことは ナンプレの難易度は何で決まるか に書きました。
唯一解でない問題に出会ったら
解いている途中で、「どちらの数字を入れても成り立つ」ように見えるマスに出会うことがあります。私は、そのときはまず自分の見落としを疑うのがよいと思います。たいていは、どこかの候補を消し忘れているか、置いた数字が間違っています。
本当に答えが2通りある問題は、作り方に不備がある問題です。きちんと検証された問題集やアプリでは、まず出てきません。
Sudoku365 の問題
Sudoku365 は、毎日解ける数独のアプリです。「かんたん」「ふつう」「むずかしい」「エキスパート」の4つの難易度に300問ずつ、計1200問が入っています。この記事を書くにあたって、1200問すべてについて答えの数をプログラムで数え、どれも答えが1つだけであることを確かめました。ヒントの数は21個から28個で、難易度によって大きな違いはありません。
答えが1つに決まっているので、「間違えた数字を表示」をオンにしておけば、置いた数字が正しいかどうかをその場で知らせてくれます。じっくり自分で確かめたいときは、オフにもできます。
アプリは無料で、広告が入ります。「広告を削除」の買い切り(300円)で広告を消せます。最初の一問の始め方は Sudoku365 の始め方 に書きました。
