数独を解く問題です。
95を2月に解いて、それから取り組んでいたのですが、昼休みとか暇なときにしかやってないとは言え、なかなかタフで時間がかかりました。
結果的には、ネットからのデータの取得も含めて3.4秒ほどで解けたので上々でしょう。
数独は大学時代(ずーっと昔ですねぇ)にニコリで嵌ったので解き方は知っていました。
プログラムなので、全面的にBacktrackを使った探索で解く(brute force)のもいいのでしょうが、それでは面白みがありませんので、先ずは解き方(rule)を試して、だめなら探索することにしました。
ですが、解き方を実装するにあたって、それぞれのマス目を直接操作する必要があるので、hashを使うことにしました。 キーは座標のベクタです。値は、マスの数字が決っているときはその数字をいれます。決っていない場合は、候補の数字が入ったsetを入れます。
こうすると、値の種別を見るだけで、そのマスが決っているかどうか判別できます。
のような具合です。この場合、[7 6]のマスは7で決定、[2 1]のマスは1 3 6のいずれかが入るということになります。
95を2月に解いて、それから取り組んでいたのですが、昼休みとか暇なときにしかやってないとは言え、なかなかタフで時間がかかりました。
結果的には、ネットからのデータの取得も含めて3.4秒ほどで解けたので上々でしょう。
数独は大学時代(ずーっと昔ですねぇ)にニコリで嵌ったので解き方は知っていました。
プログラムなので、全面的にBacktrackを使った探索で解く(brute force)のもいいのでしょうが、それでは面白みがありませんので、先ずは解き方(rule)を試して、だめなら探索することにしました。
結果
96番の50問をすべて解くことができました。また、いくつかのサイトで難しいと言っている問題を解いてみましたが、すべての問題を解くとこができました。数独の解決プログラムとしても合格でしょう。
プログラム
ruleを入れたので、大きくなってしまったのと、いずれ数独解法ツールとして使えるようにしてもいいかなと思ったことから、プロジェクトにしました。なのでgistではなくgithubに入っています。これがプロジェクトです。
今後
数独とかカックロあたりを解くプログラムはいずれ作ろうと思っていたので、今回のきっかけはちょうどよかったのかもしれません。
そのうちインターフェースを作ってあげようかと思っています。スタンドアロンでもいいし、Webアプリでもいいかも。両方でもいいかも。
また、使っているルールで実装していないものが1つあるので、それを入れてみたいとも思っています。ちなみに、現在の所要時間は、世界一難しいもの(ほんと？)でも0.5秒弱でした。
以下プログラムについて
データ構造です。
始めは、数字を列ごとにならべたもので進めていました。[[ 1 2 3 ...... 7 8 9] [ 1 2 3 ...... 7 8 9] ... ... [ 1 2 3 ...... 7 8 9]]
ですが、解き方を実装するにあたって、それぞれのマス目を直接操作する必要があるので、hashを使うことにしました。 キーは座標のベクタです。値は、マスの数字が決っているときはその数字をいれます。決っていない場合は、候補の数字が入ったsetを入れます。
こうすると、値の種別を見るだけで、そのマスが決っているかどうか判別できます。
{[2 1] #{1 3 6}, [7 6] 7, ....}
のような具合です。この場合、[7 6]のマスは7で決定、[2 1]のマスは1 3 6のいずれかが入るということになります。
ルール
基本：候補
ある未決定のマスに入るのは、そのマスのある行・列・枠の決定したマスのどれにも入っていない数字です。それらの数が候補です。
候補が一つ
候補が一つしかないマスは、その数が入ります。また、そのマスのある行・列・枠にはその数字は入りませんので、候補から外します。
1ヶ所にしか無い
ある数字がのそ数のあるマスのある行・列・枠の他のマスに無ければ、その数がそのマスの数になります。その数は他のマスの候補から外します。
双子
ある行、もしくは列、もしくは枠に注目したときに、2つの同じ数が入っているますが2つだけの場合、その行などの他のマスにはその2つの数は入りません。
バックトラック
ルールを適用して解けない場合、候補の数が少ないマスの候補の1つを仮に決めてしまい、それにルールを適用します。それでも解けない場合さらにどれかを選んでという具合に進めます。ルールを適用して、候補の無いマスができてしまった場合、仮に決めた値が間違っていたことになるので、もとに戻って違う候補を選びます。
0 コメント:
コメントを投稿