- 9x9のマス目があって、マス目はさらに3x3ごとにまとめられています。
- そこに、1から9までの数字を入れていきます。
- 縦、横には同じ数字は1つしかはいりません。また、3x3でまとまったマス目(ブロック)でも同様の制限をうけます。
- すべて矛盾なく埋まればパズル成功となります。
というルールはいまさらここで書くまでもなくご存じの方も多いかと思います。
ついこの間これに関して「スパコンで力任せに数独の難しい問題を作る」と題したナンバープレースの問題が発表されましたが、人間の手であっさり解かれてしまいました。
ここではなぜそんなことが起こったのか考えてみたいと思います。
数独はどうやって解くか。
「1から9までの数字が縦、横、ブロックに1度だけ入る」という制限が数独の基本解法の全てです。どんな応用解法も、この制限なしには生まれません。
さらに、仮定や背理法などの少し高度な論理を必要とするテクニックを避けると、具体的には以下の2つにまとまります。
- 各空きマスに入る可能性のある数字候補を数え上げ、候補が1つしかないマスをその数字で確定させる。
- 各数字について、制限のせいでその数字の入らない空きマスを排除していき、空きマス候補が1つになったマスをその数字で確定させる。
前者が「1つのマス目に入る数字は1種類1つだけ」後者が「同じ数字が出現するのは行、列、ブロックごとに1度だけ」を用いた解法です。
つまり、難しく書きましたが、特に2番目のほうはルールを踏まえれば基本中の基本ですから、数独やナンバープレースをやったことのある人なら普通にやっているはずのことなのです。この場合必要なのは、推論よりも、離れているところにある数字を見落とさないことでしょうか*1。ちなみに1番目の解法で、特に候補を記入していくところが狭義の「pencil marks」と呼ばれているようで、今回の問題を作った方もその点までは踏まえていたようでした。
実際に解いてみると……
さて、今回の「おそらく世界で一番難しい問題」を改めて見てみましょう。
pencil marksを行うのは後回しです。もともと難しい問題にするつもりで、狭義の「pencil marks」は役に立たない問題になっている可能性もありますし。
ですので、もう一つのテクニック、空きマスを絞り込む方法で行けるところまで行ってみます。
例えば1について左下のブロックを見てみると、中央下のブロックの1,右下のブロックの1でブロック内上2行には1が入れられないこと、左上のブロックの1でブロック内右1列にはやはり1が入らないことから左下のブロックで1が入る可能性があるのは中央下のマスしかないことがわかります。同様に、中央右のブロックでは8が中心に入ることが中央、および中央左のブロックにある8から読み取れます。
(影響範囲を塗りつぶしてみた図。前のが初期配置での1の、後のが同様に8の影響範囲。8の影響範囲はその後埋められる部分も色分けしてみました。)
さらに、数字が埋まったことで空きマス候補が減ることでまた数字が入れられるようになります。左下のブロックは、1が入ったことから同じようにして8が入れられますし、そこに入った8のおかげでマス目候補が一気に減った左上のブロックにも8を入れられる場所がみつかります。その先、右上のブロックまで8は一気に記入できますね。
まあ、このような感じで、行、列に着目して、ブロックごとに数字を見ていくのはけっこう簡単なのです。ただ、行に着目して、列の情報を元に数字を見ていく、もしくは列に着目して行の情報を元に数字を見ていくのはけっこう忘れがちで。でもこちらも、数字が埋まってきて、残りの空きマスが3つとかになってくる列が出現する中盤からはかなり役にたちます。
で、これを続けてやっていくと……この問題、これだけで解けてしまうんですね。
数独やナンバープレースの解法支援プログラム「数独解析」に「w9h9sn6n1s2n7s2n3sn9n2s2n3s14n8n5n3s10n5sn4n5s4n8s4n4s6n1s3n1n6sn8s2n6」というふっかつのじゅもんを入れて解いてみて下さい。「消去法」「補完」の初歩的なテクニックしか使っていないことがわかります。
つまり「人間の手だけにできる(人間の感性を利用した)テクニック」とか「難易度の定義に含めていない解法(n国同盟など)」まで進むまでもない問題だったわけです。パズルを作るのって難しいですね。
では、どうすればよかったのか
消去法で空きマスの候補を減らしていくのは盤面の観察能力のみに依存するもので、パズルの難度には関係なさそうだ、ということは言えそうです。ですから、パズルの完成時点で「消去法で空きマス候補が1のマス(確定で数字の埋まるマス)がない」ことを確認しておくのがいいのではないかと思います。あらかじめそういうマスは数字で埋めておいてもいいですが、埋めた結果さらに別の同様なマスが発生することのないように、ということで。
まあ、テストプレイはきちんとしたほうがいいですね。難度にこれら初歩テクニックは関与しないと定義するなら、仮定を用いた再帰とかまではしない簡単な解法支援プログラムを利用するのも手だと思います。
ちなみに、日本では「数独」は「ナンバープレース」のうち、数字の初期配置が対称になっている条件が加わっているとする人が多いですので、日本人に通じる「数独の難しい問題」を作るには、さらに、盤面を対称形にする必要があるかもしれません。
やっぱり、パズルを作るのって難しいですね。
おまけ
n国同盟というのは、先に書いた
- 各空きマスに入る可能性のある数字候補を数え上げ、候補が1つしかないマスをその数字で確定させる。
この解法の発展系です。
- 各空きマスに入る可能性のある数字候補を数え上げ、候補が同じ2つしかないマスが群(行、列、ブロック)の中に2つ出現したら、その群の他のマスにその候補の数字は入らない。
これが2国同盟、2をnに変えればn国同盟です。*2
おまけ(n国同盟)に関して追記
基本テクニック部分はきちんとチェックして作られたナンバープレースが元サイトで発表されましたが、ちょうどここに2国同盟が出てくる場所がありますのでそれで解説しましょう。
この中の下から4番目の行、ヒントが4,5,2,8とあるところに注目します。残りの数字は1,3,6,7,9です。
7と9が盤面に多いので注目すると、7と9が入れられる場所は2ヶ所しかありません。これが2国同盟で、この場所は7と9のどちらかしか入らず、7と9はそれ以外の空白には入らないことになります。
逆を見れば、残りの空白には1,3,6しか入らないので、それら(7,9の入らない)空白は1,3,6の3国同盟とも見なせますね。さらによく見ると、その3国同盟のうち3が入れられるところは1ヶ所しかないので、残る2マスが1,6の2国同盟となります。なお、以下に7,9を塗りつぶしたイメージを載せてみました。(図の★部分が7と9の2国同盟となります)
もうひとつ、左から2番目の列、上からヒントが4,9,3,8,7とあるところに着目します。残りの数字は1,2,5,6です。
2と5が盤面に多いので注目すると、2と5が入れられる場所は2ヶ所だけになり(図の★部分)、2と5の2国同盟が生まれます。もちろん、空きマスはあと2つあって、そこには1と6の2国同盟となるわけです。おや、1,6の2国同盟が2つ出来た上に、1マスは共有していますねえ(意味深)。
評価のしかたをきちんとしただけあって、このナンバープレースはここで軽く手詰まりとなって、この1と6の2国同盟に関して背理法で矛盾を示して確定する作業が発生します。
もっとも、間違っているほうを仮定した後の矛盾はけっこう早く見つかる*3ため、それほど複雑ではなく、さらにそれが決定したあとは初歩的なテクニックだけで解けるのですが。
実際にどう解けていくかは先ほどの「数独解析」に「w9h9sn4n6s2n5n7s5n9s6n9s3n1s2n6s6n9s3n3s7n4s2n5n2s3n8sn8s5n7sn5n7sn3s3n8n2n2s5n3」を入れて試してみてください。
この部分をどう難易度判定するかについてですが、着目するときに「ヒントの多い群」を狙っているので、群のなかでのヒント数(要素)が偏っていないことも評価に入れたらいいのではないかな、と思ったりもしました。
(追記ここまで)
なお、n国同盟について、詳しくは、
「ナンバープレイス、数独 解法まとめ」を参考にしてみて下さい。
基本的には、仮定を元にした再帰の枝刈りをするためのテクニックとして帰着する類のものだと思います。
繰り返しますが、この解法を使わなくても、知らなくても、最初に出た問題は簡単に解けます。
さらに追記
3月13日21時にアップされた新しい問題は、さすがにいろいろ見直したようでヒントのなかなか出ない問題になっているようです。世界で一番難しい、というほどではないですけどけっこう辛い(からい)ですよ。
