はじめに

初めまして。traP Advent Calender2017/11/29担当のkanjiです。
今回はタイトル通り数独を解いていきたいと思います。と言ってもただ解くだけだとあれなのでプログラムを使って解いていきます。

数独とは

別名ナンプレと言います。知ってる人も多いと思いますが一応知らない人のために説明をします。
が、その前に、今回の記事内で使う用語についていくつか定義しておきたいと思います。

• プレート
  • 数独で出てくる９×９のマス目全体
• 行
  • 横並びの９マス全体
• 列
  • 縦並びの９マス全体
• 箱
  • プレートを横と縦それぞれで三等分した時の３×３のマス目全体
• (n,m)
  • 上からn個目で左からm個目のマス

• 一つの行に１から９の数字がそれぞれ１つずつ入る
• 一つの列に１から９の数字がそれぞれ１つずつ入る
• 一つの箱に１から９の数字がそれぞれ１つずつ入る

言葉だけの説明では難しいので実際に問題を見てみましょう。(実はトップ画像がこの問題になっています)

この問題の場合、例として(9,7)の属する箱に注目します。この箱には１がないのでどこかに一つ１を入れる必要があります。８列目と９列目にはすでに１があるので入りません。７行目にも１があるので入れられないです。すでに数字の入っている部分には入れられないので消去法で(9,7)に１が入ります。

アルゴリズム

それではこれから数独の問題を解くためのアルゴリズムを考えていきましょう。ただし、この方法はあくまで私が考えた方法なので、実際にはもっといい方法があるかもしれません。もっと上手く解ける方法を知っている、もしくは思いついた方は、どうか暖かく見守ってやってください。

ボツ案

簡単に思いつく方法としては全ての数字のパターンを試して矛盾がないものを選ぶ、という方法があります。コンピュータは人間よりはるかに早く計算することができるのでこの方法でもいつかは解き終えることができるでしょう。しかしこれではつまらないし無駄が多すぎるのでこの方法はボツにしました。

採用案

まず数独の問題を解くには当たり前ですが数字を埋めていく必要があります。それをいちいち場合分けしていては無駄になるので、まず入れられる数字が確定する条件を調べてみましょう。
　例であげた問題では(9,7)の数字が１と確定していました。これを考察すれば良さそうです。まず最初に(9.7)の属する箱には１が入っていないのでどこかに１を入れる必要がありました。しかし(9,7)のマスを除いて１が入れられないので(9,7)が１と確定していたのです。
　これを一般化すると、「ある箱に対して、そこにない数字kの入れられる候補地が１つの場合に限り、その候補地の数字がkと定まる」と言えそうです。なんだか当たり前の話ですね。また、数独のルールの類似性を見ればわかりますがこの方法は行、列にも転用できそうです。よって「ある行、列、箱のいずれかに対して、そこにない数字kの入れられる候補地が１つの場合に限り、その候補地の数字がkと定まる」とまとめられそうです。
では次にその候補地の求め方を考えましょう。ある数値kの入れられる候補地は簡単で、次のように求められそうです。

1. プレートの全てのマスを候補地とする。
2. k以外の数字の入ったマスを候補地から取り除く。
3. kの入ったマスの属する行、列、箱に属する全てのマスを候補地から取り除く。
4. 残ったものがkの入れられる候補地になる。

これで数字が確定する場所を求めることができるようになりました。大体の問題はこれだけでも解けますが中にはこれだけだと解けない問題もあります。
　それが仮置きして解く問題です。この方法はアルゴリズム的に見ればただの場合分けなので、上記の方法を使って確定する場所がない、かつまだ埋められていない場所がある場合には場合分けをすれば良さそうです。
　これでだいぶ無駄が省けました。これよりもさらに無駄を省く、あるいは早く解ける方法があるかもしれませんが私にできたのはここまでなので、説明は終わりにしたいと思います。
　ちなみに例として出した問題を解かせてみた結果がこちらです。

終わりに

今回は数独の問題を解くアルゴリズムを紹介しましたが、読んでみてわかるように実はやってみると割と簡単だったりします。(いいアルゴリズムかどうかは置いといて) 本当に難しいのは問題を解く方ではなく作る方で、解ける(答えが一つに定まる)問題を生成するアルゴリズムはほとんど検討もつきません。数独はこのように単純なルールなのに奥が深く、考えた人はすごいなぁ...と思いました。(小並感
　え？ソースコード？知りませんねそんなもの

明日のAdventCalenderはerukkuさん、kakuoさん、phi16さんです。お楽しみに！