はじめに
最近なかなかQiitaで記事を書くことが出来なかったので、リハビリ感覚で書かせてもらいます。稚拙な文章である可能性高いですが、chatGPTにも手伝ってもらってなんとか書いています。便利な時代になりましたね。
早速本題の前に 「ナンプレ」 とは？
とりあえずchatGPTさんにナンプレについて聞いたら、こんな感じの文章が返ってきました。
ナンプレは、9x9のマス目を持つ数独パズルゲームです。目標は、各列、各行、および各3x3の小さなエリアに、1から9までの数字を重複なく配置することです。最初に与えられた一部の数字（ヒント）を基に、論理的な推論と試行錯誤を駆使して、すべてのマスを埋めることが求められます。数字を正確に配置することができれば、問題は解決されます。ナンプレは論理力と推論力を鍛えるたのしいパズルゲームとして知られています。
みなさん、新聞やアプリなどで一度はこんな感じの、9×9のマスを見たことがあると思います。
5 3 * | * 7 * | * * *
6 * * | 1 9 5 | * * *
* 9 8 | * * * | * 6 *
---------------------
8 * * | * 6 * | * * 3
4 * * | 8 * 3 | * * 1
7 * * | * 2 * | * * 6
---------------------
* 6 * | * * * | 2 8 *
* * * | 4 1 9 | * * 5
* * * | * 8 * | * 7 9
*となっているところを埋めて、以下のように解くというゲームです。
5 3 4 | 6 7 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 | 7 6 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
ナンプレとぼくとの関係
ナンプレはいい意味で暇つぶしになります。
毎日アプリで新しい問題が出るのですが、出た瞬間に解くようにしています。
デイリーで出る問題は、早くて2分ぐらい、遅くても5分もあれば解けるようになりました。
毎日やっているということもあって、まだハマっている状況（2023年9月現在）ではあるものの、結構解き方が決まってきて、作業ゲーになりつつあります。
今までの自分の傾向だと、あと数週間もしたら飽きてしまうだろうな、と思っていました。
とはいえ、ただ辞めるのも勿体無いなと思い、
「せっかくなら、自分の解き方をプログラムに残しておきたいな、、、」
と思い、こんな記事を書きました。
一般的な解き方
ググれば出てくると思いますが、基本的な方法をまとめると
- 同じ行内で埋まっていない数字が入る候補を各マスで出す
- 同じ列内で埋まっていない数字が入る候補を各マスで出す
- 同じエリア（3×3）で埋まっていない数字が入る候補を各マスで出す
回りくどい言い方をしましたが、
要は、各マスごとに、同列、同行、同エリアで入っていない数字をメモとして出し上げれば、簡単~普通の問題であれば各マスの候補が1つになるものが出てきて、芋づる式に解くことが出来るという感じです。
少し難しい問題になると、上記の方法だけだと難しいパターンがあります。
（各マスの候補が1つになるものがない場合が出てくる）
この場合は、もう少しテクニックを使うのですが、書き出すにはちょっと労力がいるので、ググってみるといいかもです。
プログラムに解いてもらう
ちょっと前置きが長くなってしまいましたが、早速ナンプレを解いてくれるプログラムを書いていきます。
ちなみに、実行時のpythonのバージョンは以下のようになっています。
python --version
Python 3.11.1
今回解く問題
気軽に一度解いてください、とは言えないぐらい難しい問題です。
こればっかりは自分も解こうと思ったことないです。
せっかくプログラムに解かせるので、めちゃくちゃ難しい問題にしました。
ひとまずナンプレが解ける状態に持っていく
まずは、少し雑にはなりますが、答えが出る状態にしないといけないので、以下のcommitで答えが出る状態にまで持っていきました。
解き方を簡単にまとめると、
- 初期で与えられた表を元に、各列、各行、各エリアでどの数字が埋まっていないかを求める（各マスでの候補を簡単に計算するためにあらかじめ処理をしておく）
- 以下の処理を繰り返す
- 各マスの候補となる数字の集合が入ったリストを取得する
- まだ決定していない座標のリストを取得する（埋まっていないマスを求める）
- まだ決定していない座標がない場合、ナンプレが正しいかどうかを判定する（間違っていても数字を入れるようにしている、ここで弾くので結果に問題ない）
- 候補が1つしかない座標のリストを取得する
- 候補が1つしかない座標がある場合、その座標を埋めて再帰処理を行う
- 候補が1つしかない座標がない場合、候補の中から1つ数字を選んで再帰処理を行う
結構無理矢理な方法です。各マスに複数候補が出てきた場合には、ゴリ押しで全ての可能性を考え、間違っていたら、それが分かった時に弾くという感じです。
上記の方法でやった結果を以下に記載します。
かかった時間に関しては気にせず、以下のような見方をしてください。
パラメータの見方
- count: 再帰に入った回数。無駄な処理が多いほど数字が大きくなる。
- no_cnt: 間違った答えだったため、弾いた回数。これも無駄打ちしている数が多いほど大きくなる。
- ans_cnt: 答えの数。
---first answer---
[[8 1 2 7 5 3 6 4 9]
[9 4 3 6 8 2 1 7 5]
[6 7 5 4 9 1 2 8 3]
[1 5 4 2 3 7 8 9 6]
[3 6 9 8 4 5 7 2 1]
[2 8 7 1 6 9 5 3 4]
[5 2 1 9 7 4 3 6 8]
[4 3 8 5 2 6 9 1 7]
[7 9 6 3 1 8 4 5 2]]
time : 5.497s
count: 5126
no_cnt: 1009
ans_cnt: 1
---result---
[[8 1 2 7 5 3 6 4 9]
[9 4 3 6 8 2 1 7 5]
[6 7 5 4 9 1 2 8 3]
[1 5 4 2 3 7 8 9 6]
[3 6 9 8 4 5 7 2 1]
[2 8 7 1 6 9 5 3 4]
[5 2 1 9 7 4 3 6 8]
[4 3 8 5 2 6 9 1 7]
[7 9 6 3 1 8 4 5 2]]
time : 464.888s
count: 509308
no_cnt: 112447
ans_cnt: 1
答えが出ましたね。
見てお分かりの通り、結構無駄打ちが多いです。もう少し効率的に解きたいので、以下の考え方を追加します。
まだ決定していない座標のリストを返却するメソッドを改良する
上記の方法から、各マスの候補となる数字の集合の数が最小となるマスの座標のリストを返すようにしました。
（コミットメッセージミスっちゃったのですが気にせずに）
何をしているかというと、
先ほどまでの方法は、まだ埋まっていないマスを、序列なしに探索するようになっていたのですが、
今回の方法は、各マスでの候補が少ないマスを優先的に探索するようにしています。
1,2,3,4,5が候補となっているマスよりも、1,2が候補となっているマスを優先的に解いた方が、後々の組み合わせが少なくなるという考えです。
さて、結果的には以下のようになりました。
---first answer---
[[8 1 2 7 5 3 6 4 9]
[9 4 3 6 8 2 1 7 5]
[6 7 5 4 9 1 2 8 3]
[1 5 4 2 3 7 8 9 6]
[3 6 9 8 4 5 7 2 1]
[2 8 7 1 6 9 5 3 4]
[5 2 1 9 7 4 3 6 8]
[4 3 8 5 2 6 9 1 7]
[7 9 6 3 1 8 4 5 2]]
time : 2.952s
count: 3545
no_cnt: 655
ans_cnt: 1
---result---
[[8 1 2 7 5 3 6 4 9]
[9 4 3 6 8 2 1 7 5]
[6 7 5 4 9 1 2 8 3]
[1 5 4 2 3 7 8 9 6]
[3 6 9 8 4 5 7 2 1]
[2 8 7 1 6 9 5 3 4]
[5 2 1 9 7 4 3 6 8]
[4 3 8 5 2 6 9 1 7]
[7 9 6 3 1 8 4 5 2]]
time : 40.415s
count: 47876
no_cnt: 8969
ans_cnt: 1
countを見る限り、約500000->約50000と、処理数が10%程度に圧縮されました！
当たり前といえば当たり前ですが、時間も10%程度になってますね。
探索方法に関しては変えてないので、予想はできましたが。
さて、もう少し改善してみましょう。
候補が1つしかない座標のリストのメソッドを改良する
うまいこと文章に出来なさそうだったので、chatGPTにまとめてもらいました。
base_listの初期化: base_list は、候補が1つしかない座標の情報を格納するリストです。最初に、既に候補が1つしかないマス（数字が確定しているマス）をリストに追加します。
行ごとの確認: 各行ごとに、候補が1つしかないマスを探します。行内で数字が1つしか選択肢がない場合、その座標を base_list に追加します。
列ごとの確認: 各列ごとに、候補が1つしかないマスを探します。列内で数字が1つしか選択肢がない場合、その座標を base_list に追加します。
エリアごとの確認: 各エリア（サブグリッド）ごとに、候補が1つしかないマスを探します。エリア内で数字が1つしか選択肢がない場合、その座標を base_list に追加します。
最後に、base_list を返します。
こんな感じです。
何をしているかというと、再帰関数に入る際に、毎度各マスに入る可能性がある数字を計算し、マスに1つの数字しか入らないことが分かった場合、即座に埋めてしまう、という方法です。
これによって探索数を圧倒的に減らすことが出来ますからね。
というわけで、結果は以下のようになります。
---first answer---
[[8 1 2 7 5 3 6 4 9]
[9 4 3 6 8 2 1 7 5]
[6 7 5 4 9 1 2 8 3]
[1 5 4 2 3 7 8 9 6]
[3 6 9 8 4 5 7 2 1]
[2 8 7 1 6 9 5 3 4]
[5 2 1 9 7 4 3 6 8]
[4 3 8 5 2 6 9 1 7]
[7 9 6 3 1 8 4 5 2]]
time : 0.218s
count: 196
no_cnt: 18
ans_cnt: 1
---result---
[[8 1 2 7 5 3 6 4 9]
[9 4 3 6 8 2 1 7 5]
[6 7 5 4 9 1 2 8 3]
[1 5 4 2 3 7 8 9 6]
[3 6 9 8 4 5 7 2 1]
[2 8 7 1 6 9 5 3 4]
[5 2 1 9 7 4 3 6 8]
[4 3 8 5 2 6 9 1 7]
[7 9 6 3 1 8 4 5 2]]
time : 1.969s
count: 1993
no_cnt: 211
ans_cnt: 1
なんかとんでもなく処理回数が減りましたね！！！
自分で作っておいてなんですが、かなりびっくりしています。
先ほどの結果と比べようかと思いましたが、せっかくなので、3つの結果をいっぺんにまとめようかと思います。
first answer
| commit | count | no_cnt | ans_cnt |
|---|---|---|---|
| 1つ目 | 5126 | 1009 | 1 |
| 2つ目 | 3545 | 655 | 1 |
| 最新 | 196 | 18 | 1 |
result
| commit | count | no_cnt | ans_cnt |
|---|---|---|---|
| 1つ目 | 509308 | 112447 | 1 |
| 2つ目 | 47876 | 8969 | 1 |
| 最新 | 1993 | 211 | 1 |
桁が鬼ほど違いますね。
何が嬉しいかって、no_cntが圧倒的に減ってるんですよね。
無駄打ちをほとんどしていないということですね。
とはいえ、211もミスっているのは、まだ改良の余地がありそうだということですか、、、？
最後に
と、勢いよく記事を書いてみたのですが、どうでしょう？
1時間ちょいで記載が出来たのは悪くはないですね。
まだまだだなーと思うのは、あまりchatGPTを使えなかったことですね。
もっと使ったら簡単に書けてたのかは不明ですが、チャレンジしてみないと分からないので、次回はより多用してみようと思います。
今回のソースはこちら
README.mdも簡単に書けるようになったこんな時代に感謝です。