# なぜ17個の手が必要？ これ以上小さくできない数独

クラシック数独では、解が1つに定まるために初期の手が最低17個必要なのはなぜ？ 限界、証明、そしてプレイヤーにとって何が意味するのかを探ります。

数独から1つの数字を消すと、難しくなるかもしれません。間違ったものを消してしまえば、パズルの唯一の答えを壊してしまうかもしれません。満タンの盤面と真っ白なページの間には、はっきりした上限があります。**初期の手（与えられた数）は17個**。なぜ数独はここで止まるのでしょう？

答えは、見落としやすい問いから始まります。あなたのパズルには、**解が1つだけ**ありますか？

## 1つの完成盤、1つの答え

クラシックな9×9数独では、各行・各列・各3×3ボックスに1〜9の数字が**ちょうど1回ずつ**入る必要があります。これらは[日刊工業新聞社ではなく、日?]ではなく、[ニコリが公開している標準ルール](https://www.nikoli.co.jp/en/puzzles/sudoku/)です。盤面に最初から印刷されている数字は、_与え（givens）_、あるいは手（clues）と呼ばれます。

完成した盤面が、そのルールをすべて満たしていても、最初に入っていた手だけで一意に定まるとは限りません。もし2通りの完成が両方とも成り立つなら、出題者がどちらを意図したのかプレイヤーには判断できません。

だからこそ「一意性」が重要です。よく定義されたクラシック数独は、完成盤を**ちょうど1つ**に特定するのに十分な情報を与えてくれます。ルールに慣れていないなら、私たちの[数独の遊び方ガイド](/en/blog/how-to-play-sudoku)が始めるのにちょうどよい場所です。

## たった1つの手の変更で全部が変わる

意図的に、ほとんど完成しているパズルを用意しました。ドットは空白マスを表します。

```text
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つになるものは存在しない」**ことを証明しました。彼らの[元の研究論文](https://arxiv.org/abs/1201.0749)では、総当たりのコンピュータ探索が説明されています。一意に解ける17手のパズルは存在するので、17が最小です。

ただし、**17個なら何をどう並べても有効なパズルになる**わけではありません。位置と値が重要です。結論はクラシック数独についても成り立ちますが、バリエーションの追加ルールは問題そのものを変えてしまいます。

では、16を排除できれば、なぜそれより少ない手数も排除できるのでしょう？もしもっと少ないパズルで解が1つだけなら、その解から正しい手を追加していけば、与えが16になるところまで持っていけます。手を足しても一意の答えは保たれ、結果に反することになります。

## もっと小さいパズルが存在しないことはどう証明する？

17手のパズルを1つ見つけることは、何が可能かを示します。16がダメだと証明するには、**ありとあらゆる可能性を潰す**必要があります。

研究者たちは、同値な盤面を考慮しながら、完成盤を系統的に探索しました。手法では、_避けられない集合（unavoidable sets）_ を使います。これは、別の完成を防ぐために「どれかは必ず手に含まれなければならない」マスのグループです。さらに、_ヒッティングセット（hitting sets）_（それらのグループと必ず交わる選び方）を列挙するための効率的なアルゴリズムを開発し、唯一性を満たす候補の手の集合を検証しました。[論文で方法が説明されています](https://arxiv.org/html/1201.0749v2)。

上の長方形は、その考え方を小さく示す例です。4つのマスをすべて手なしにすると、2通りが生き残ります。すると、そのうち少なくとも1つを固定すると、その入れ替えが塞がれてしまいます。手の少ないパズルでは、多くの代替案をまとめて同時に塞がなければなりません。

## 「最小の手数」＝「最大の難しさ」ではない

手数の数は「印刷されている情報量がどれくらいか」に答えてくれます。しかし、次にどんな推論を見つけることになるかは教えてくれません。与えの数を数えても、次の一手が、すぐ分かる「単独候補」なのか、まだ学んだことのないパターンなのかは分かりません。

もう1つ役立つ区別があります。_minimum_ と _minimal_ です。minimum は、クラシック数独で可能な最小の手数です。minimal なパズルは、どの与えを消しても一意性が失われるものです。パズルを minimal と呼んでも、必ずしも17手だとは言えません。

次のゲームでは、配置する前に一言説明してみてください。「この4は、このボックスで入れられるのはここだけ」などです。まだ説明できないなら、候補を確認するか、私たちの[数独攻略ガイド](/en/blog/common-techniques-for-solving-sudoku)からテクニックを試してみましょう。

次に手が少ない数独に出会ったら、まず手の数を数えます。そして次に、「なぜそれが必要なのか」を探してください。
