数独(ナンプレ)の解き方(アルゴリズム)

質問

プログラミングの宿題で、Javaを使って数独を解くプログラムを作っています。雑誌などにある数独の問題を解くことはできたのですが、今回はその問題もプログラムで作ってそれを解かせようというお題になってしまいました。今のところ下のような感じになっています。

1. 乱数を使って0-80までのマス番号に1-9の数字を数個適当に入れていきます。(0が左上の角で、80が右下の角です。) 乱数でマスに数字を入れますから、同じマスに数字が入ることがありますが、それはそれでそのマスを上書きしています。さらにこの段階で、数字が同じ列または3×3マスで重なることがないようにしています。

2. それを元に各マスに入る可能性のある数字をリストアップ

3. リストアップした中で、最後に必ず1つだけ数字が残るのでそれをそのマスに入れます。

とここまではできました。しかし、乱数で適当に問題をつくったにしか過ぎないから、当然ダブってしまうところや、数字が入らないマスがあります。ですから、そういったダブるところや数字の入らないマスのために補正をしたいと思うのですが、まったくアイディアが浮かびません。どのようにしたら補正をして問題を回答できますか? アルゴリズムが少々長くてもかまいません。また、Javaのコードでの回答でなくてもかまいません。とにかく、如何の様に補正するのかを知りたいです。

下にあるのが、上の1.で作った問題です。
# 0は数字が入っていないマスを示します。

060 | 000 | 080
030 | 080 | 017
000 | 100 | 000
---------------
800 | 000 | 903
000 | 803 | 060
000 | 096 | 500
---------------
908 | 407 | 000
205 | 000 | 400
700 | 001 | 000

回答No.5

pueplo · ベストアンサー

＃１です。

スードコードって以外に難しいんですよね～

本アレー　をｓｕ[a,b]
ダメアレーをdoku[c,d,e]　として。

{
まずは抽選　suに入る数字を乱数より導く。

dokuアレーを使って検査

dokuアレーにその数字の記載があれば、ここでループを終えるか？もう一度再抽選（ループはじめに戻る！）

もし、dokuアレーに乱数で引き出した数字が無ければ～
ポジションa,bを使って、数字が入るか？検査をする。

レツ検査su[a,*]　
ココでボツなら、dokuアレーに代入＆再抽選（ループはじめに戻る）

OKなら

レツ検査su[*,b]
ココでボツなら、dokuアレーに代入＆再抽選（ループはじめに戻る）

OKなら

コワクはちょっと難しいですが、switchなどを使ってみては？

ポジション

0<=a<=2,0<=b<=2 3<=a<=5,0<=b<=2 6<=a<=8,0<=b<=2
0<=a<=2,3<=b<=5　～　～
～　～　～
てなかんじでコワクをスイッチ回路で制限して
検証する。

もしコワクの中で数字を共有していれば、dokuアレーに数値を代入、再抽選

無ければ、それが当たりの数字！！

オプション（（レツのほかのdokuアレーとコワクの他の場所に当たりの数字を代入すれば、抽選効率は後々になると、早くなるはずです。））
｝

//コメント//
dokuアレー９X9X9のアレーにしておいて、９個数字が埋まったら、そのパターンは廃棄！という回路を作っておいてもよさそうですね。

ｊａｖａが専門ではないので、ＣとＶＢが混じっていますが、同じように出来るはずです。

頑張ってみてください！

お礼

アルゴリズムの提供ありがとうございました。

なかなか、うまくアルゴリズムの再現ができなくて結局宿題の期限となんてしまいました。提供してもらったのに、申し訳ない気持ちでいっぱいです。

補足

自分に技術力が無いばかりに本当に申し訳ないのですが、上のアルゴリズムを得意としている言語でかまわないので(でも、Basic以外だと助かります)、実際のコードに起こしてもらえませんか? 本当にすみません。

また、＃4さんのアルゴリズムもコードに起こしてもらえると助かります。

回答No.6

laputart

VBで問題と解答のプログラムを作りました。５年以上前からパズル雑誌に掲載されていました。

考え方としては、
(1)まず解答を作成する（配列０から８０まで数字が確定した）
(2)これを元にヒント升を決定する
(3)実際にPCに問題を解かせて最後まで出来るかどうか検証する
という事が一番速いと思います。

まず(1)についてですが、
◆どの数字２つ（例えば数字の１と９）を全て入替えても矛盾はしないという事
◆列番号（０から８で）０１２を全て入替えても矛盾しないと
いうこと
◆行も同様です。
◆更にブロックの入替えも出来ます

よって配列０から８０までを乱数ではなくてシリアル値代入して矛盾ないように最後まで完成しても一般性を失わないという事です。

VB的な書方になりますが

Dim A(80) as Integer (整数）
Dim B(80) as String * 9 (文字列）
B(0から80)に　"123456789"を代入　＜－どの数字が入ってもいいということ
A(0から80)に0を代入
A(0)=1
b(0)="1********" <--- 数字１が確定
b(1から8)を　"*23456789"にする　（数字１が入らない）
B(縦の列）、B(0)を含むブロックも同様にする

A(1)=2を代入　（１は入らない）
と同様の試行を続けていきます。

この方法なら乱数を使わずに問題を作成する事が可能です。
それと乱数の場合は途中で矛盾が発生した場合、何度も後戻りするので
なかなか最後まで行かないのではないかと思います（まだ試した
事はありませんが）

回答No.4

SortaNerd

{
既出数字チェック用に9×9×9の配列を作る。
乱数でマスを選ぶ。第i行第j列とする。
乱数で数字を選ぶ。nとする。
[i,j,n]を見る。既にチェックがあったらやり直し。
チェックがなかったら第i行第j列の数字はnと決定し、その数字と、それによって置けなくなる数字にチェックをつける。
ここで置ける数字がただ一つに決まってしまったマスがあるならば、そのマスのその数字の部分にチェックをつける。そしてそれにより置けなくなる数字にもチェックをつける。
}
をチェックが全部埋まっていない限り続ける。

といった感じでしょうか。ソースを人に伝えるのって難しいですね。

お礼

アルゴリズムの提供ありがとうございました。

なかなか、うまくアルゴリズムの再現ができなくて結局宿題の期限となってしまいました。提供してもらったのに、申し訳ない気持ちでいっぱいです。

補足

#1・#3さんへの補足もこちらでさせていただきます。

ということは上にあるソースの説明がバックトラック法で解く場合の方法ということでいいのでしょうか? (自分が解釈できた範囲で言えば、これじゃないかと思うのですが・・・)

回答No.3

rabbit_cat

こういう問題は、基本的には、いかに枝刈りをして、可能性を少なくできるか、にアルゴリズムの良し悪しがかかっています。

一番、基本的な枝刈りの方法は、＃１さんにでている、いわゆる「バックトラック」というやつです。
バックトラックでWeb検索すれば、たくさんページが見つかると思います。
バックトラックは、この枝は刈ってかまわない、ということをいかに早く見つけられるかで性能が決まります。

さらに高度な枝刈りとしては、バックトラック（深さ優先探索）に幅優先探索を組み合わせるとか、確率的なアルゴリズムを取り入れるとか、いろいろあります。

お礼

アルゴリズムのヒントありがとうございました。

なかなか、うまくアルゴリズムの再現ができなくて結局宿題の期限となってしまいました。

回答No.2

age_momo

最近、Excel　VBAで同様の解法プログラム作りました。

質問者さんの解法のプログラムは白紙の問題にも対応しているのでしょうか？
もし、対応しているなら全て決めてからランダムに空白を作った方がいいと思うのですが。

また、ここで言う問題の定義ですが、普通、解答が一意的に決まるものを言っているでしょうか？何通りも解答があるのでは例えば空白でも問題と言えるわけで、少し適当でないように思いますが。(その場合は出来上がった答えから空白を作っていくときに解答が一通りかどうかチェックしながら抜いていく事になりますね。こちらは考えた事ないですが結構面倒そうです）

回答No.1

pueplo

絶対入らない！数字がありますよね。
例えば、コワク（３Ｘ３のセット）とレツ（１Ｘ９と９Ｘ１）
この2つを乱数で入力した時に、チェックする検査をつくり、ボツが出れば、直前に入れたバリューを無効にする！という方法でどうでしょうか？

アレーを作っているはずですから、簡単な分岐でこれらのチェックは簡単に出来るはずです。

もう少し高度になると、没リストアレーを製作（９Ｘ９Ｘ８の３Ｄアレー）ボツにした数字をコレクトしておいて、乱数で弾き出した数字が、ボツリストにあれば、再抽選する！なんて作っておけば、チョッピリ高速化？しません？？？

参考まで。