なぜ17個の手が必要? これ以上小さくできない数独
数独から1つの数字を消すと、難しくなるかもしれません。間違ったものを消してしまえば、パズルの唯一の答えを壊してしまうかもしれません。満タンの盤面と真っ白なページの間には、はっきりした上限があります。初期の手(与えられた数)は17個。なぜ数独はここで止まるのでしょう?
答えは、見落としやすい問いから始まります。あなたのパズルには、解が1つだけありますか?
1つの完成盤、1つの答え
クラシックな9×9数独では、各行・各列・各3×3ボックスに1〜9の数字がちょうど1回ずつ入る必要があります。これらは[日刊工業新聞社ではなく、日?]ではなく、ニコリが公開している標準ルールです。盤面に最初から印刷されている数字は、与え(givens)、あるいは手(clues)と呼ばれます。
完成した盤面が、そのルールをすべて満たしていても、最初に入っていた手だけで一意に定まるとは限りません。もし2通りの完成が両方とも成り立つなら、出題者がどちらを意図したのかプレイヤーには判断できません。
だからこそ「一意性」が重要です。よく定義されたクラシック数独は、完成盤をちょうど1つに特定するのに十分な情報を与えてくれます。ルールに慣れていないなら、私たちの数独の遊び方ガイドが始めるのにちょうどよい場所です。
たった1つの手の変更で全部が変わる
意図的に、ほとんど完成しているパズルを用意しました。ドットは空白マスを表します。
5 3 4 | 6 . 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | . . 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9
これは手が78個で、解は1つです。最上段の行には7が必要です。すると4行目では、4列目に7、5列目に6が必要になります。
では、1行目4列目の6を消してください。空白は4つになり、2通りの配置が成立します。
| マス | 完成A | 完成B |
|---|---|---|
| 1行目4列目 | 6 | 7 |
| 1行目5列目 | 7 | 6 |
| 4行目4列目 | 7 | 6 |
| 4行目5列目 | 6 | 7 |
他の数字はすべて同じです。どちらの配置も、各行・各列・各ボックス、および残りの手を満たします。この4つのマスは長方形を作っていて、6と7を入れ替えてもルールを壊さないのです。解の数を確認しました。最初のパズルは完成がちょうど1通りでしたが、消したあとではちょうど2通りになります。
手を1つ減らしても、すでに機能していた解が無効になることはありません。その解は、残った手をすべて満たし続けるからです。手ができるのは、別の答えを「許してしまう」ことです。手が77個あるこのパズルですら曖昧(複数解)なので、手数の多さだけでは一意性は保証できません。
なぜ17が最小なのか
Gary McGuire、Bastian Tugemann、そして Gilles Civario が、**「与えが16個のクラシック9×9数独で、解がちょうど1つになるものは存在しない」**ことを証明しました。彼らの元の研究論文では、総当たりのコンピュータ探索が説明されています。一意に解ける17手のパズルは存在するので、17が最小です。
ただし、17個なら何をどう並べても有効なパズルになるわけではありません。位置と値が重要です。結論はクラシック数独についても成り立ちますが、バリエーションの追加ルールは問題そのものを変えてしまいます。
では、16を排除できれば、なぜそれより少ない手数も排除できるのでしょう?もしもっと少ないパズルで解が1つだけなら、その解から正しい手を追加していけば、与えが16になるところまで持っていけます。手を足しても一意の答えは保たれ、結果に反することになります。
もっと小さいパズルが存在しないことはどう証明する?
17手のパズルを1つ見つけることは、何が可能かを示します。16がダメだと証明するには、ありとあらゆる可能性を潰す必要があります。
研究者たちは、同値な盤面を考慮しながら、完成盤を系統的に探索しました。手法では、避けられない集合(unavoidable sets) を使います。これは、別の完成を防ぐために「どれかは必ず手に含まれなければならない」マスのグループです。さらに、ヒッティングセット(hitting sets)(それらのグループと必ず交わる選び方)を列挙するための効率的なアルゴリズムを開発し、唯一性を満たす候補の手の集合を検証しました。論文で方法が説明されています。
上の長方形は、その考え方を小さく示す例です。4つのマスをすべて手なしにすると、2通りが生き残ります。すると、そのうち少なくとも1つを固定すると、その入れ替えが塞がれてしまいます。手の少ないパズルでは、多くの代替案をまとめて同時に塞がなければなりません。
「最小の手数」=「最大の難しさ」ではない
手数の数は「印刷されている情報量がどれくらいか」に答えてくれます。しかし、次にどんな推論を見つけることになるかは教えてくれません。与えの数を数えても、次の一手が、すぐ分かる「単独候補」なのか、まだ学んだことのないパターンなのかは分かりません。
もう1つ役立つ区別があります。minimum と minimal です。minimum は、クラシック数独で可能な最小の手数です。minimal なパズルは、どの与えを消しても一意性が失われるものです。パズルを minimal と呼んでも、必ずしも17手だとは言えません。
次のゲームでは、配置する前に一言説明してみてください。「この4は、このボックスで入れられるのはここだけ」などです。まだ説明できないなら、候補を確認するか、私たちの数独攻略ガイドからテクニックを試してみましょう。
次に手が少ない数独に出会ったら、まず手の数を数えます。そして次に、「なぜそれが必要なのか」を探してください。
コメント
感想を共有したり、質問したり、ほかのプレイヤーを手助けしましょう。
ログイン状態を確認中…
コメントを読み込み中…