数独をとくプログラム

質問

Ｃ初心者です。大学生です。
タイトルの通り、Ｃで数独を解くプログラムを考えています。
数独については
http://www.nikoli.co.jp/puzzles/1/
をご参照ください。

で、数独にも難易度があり、初めからある程度数字が埋まっている（簡単な）
問題を解くプログラムは作ることが出来ました。
単純に、各マスの構造体Cellに対してsign[1],sign[2],,,,,sign[9]を定義し、
それが１なら可能性あり、０なら可能性なし、として
（例えばsign2]==1,sign[5]==0ならそのマスは２になる可能性はあるが５になることはない）
丹念に各マスに対してそのマスが属するブロック、列、行を調べて最後まで１であるflagを探すようにしたのです。

しかし初めから埋まっている数字が少ないと（難しいと）そもそも回答が１通りでない、
などの理由から上記のアルゴリズムでは解くことが出来ません。
あきらかにどこかをあてずっぽに仮定する作業（バックトラック？）
が必要になりそうです。
・・・が、それをどうやって実現したらいいかで行き詰っています。
どうか知恵を貸してください。よろしくお願いいたします。。。

回答No.8

BLUEPIXY · ベストアンサー

＃７の問題は、私のプログラム（制約によるマス埋めのもの）でも解けませんでした。
結果：
+---+---+---+
|200|670|000|
|906|000|201|
|400|000|800|
+---+---+---+
|500|009|380|
|830|000|150|
|102|835|007|
+---+---+---+
|301|000|004|
|708|000|600|
|600|053|008|
+---+---+---+
＃１でも言ってますけど結局上級問題は単なる制約によって埋めていくだけでは解けない問題があると思います（私のプログラムの抜けがあるのかもしれませんが）。
ちなみに
解け残りの左上の正方ブロック
+---+
|200|
|906|
|400|
+---+
の部分で
+---+
|2X0|
|906|
|400|
+---+
+---+
|200|
|906|
|4X0|
+---+
のＸの部分で１が見合い（どちらかに１が入る）になっています。
上の方に１を入れたら手詰まりで
下の方に１を入れたら解けました。
+---+---+---+
|283|671|945|
|976|548|231|
|415|392|876|
+---+---+---+
|567|419|382|
|834|267|159|
|192|835|467|
+---+---+---+
|321|786|594|
|758|924|613|
|649|153|728|
+---+---+---+
なので、やはり、そういう仮にどこそこへＸを入れたらどうなるという仮の実行をしてみれば解けるということになります。
普通、手詰まりになってからそのような探索を始めれば、
数独自体制約が厳しいパズルなので、全探索する前に解が求まると思います。（なので、それほど深い再帰にはならないと思われます）
解が複数あることを調べる場合には、全探索しないといけないと思われますが、その場合は、見つかった解を見つからなかったとして（バックトラックして）探索を続けるということになろうかと思います。
メモリが豊富に使える昨今では多分大丈夫じゃないでしょうか。
ただ、数独のパズルとしては、解が２つ以上あるというのは、ミスだと思うので、全探索する必要はないと思っています。

回答No.9

swimeye

＃７の問題は、手作業ですが理詰めだけでとけました。
また、＃４さん回答にあるサイトにJava Appletがあり、
そちらでも解けるようです。
このサイトは仮定（背理法）を使う機能もあるようですが、
この機能なしでも解けました。

素人作成の問題はともかく、プロの作った問題は理詰めで解けることが
特徴のひとつです。
手元にニコリ社の数独の問題集（難問ばかり）がありますが、
理詰めで解けることが明記されています。
中には上記のサイトでも理詰めだけでは解けないものがありますが、
何とか自力では理詰めで解けたので、"仮定を入れないと解けない"
という発想は捨てたほうがよいでしょう。

課題の趣旨がコーディング技術だけならいいですが、
アルゴリズム考案を含むなら、減点対象にもなりかねませんので。

考え方がまったくわからなくて、他人に聞くことが反則に
ならないなら、＃４さんのサイトを見るのが早いですが、
その内容の説明なり、もう少し軽いヒントなり、
多少のアドバイスはできます。

ご健闘ください

参考URL：

http://puzzle.lavot.com/java/numberplace/index.html

お礼

わぁ。。。。。

できました。quiz3もきちんと解いてくれました。
本当にうれしいです。参考URLも参考にしました。
”ある行で同じ２つの候補を持つマスが２つあるときその他のマスから
その２つの候補を消す”というのがかなり効きました。
BLUEPIXYさんのご自身のプログラムでの出力がヒントになって
いろんなことに気づいて色々改善できました。

本当に感謝の気持ちでいっぱいです。
正直皆さんに１００ポイントくらい上げたいのですが特にお世話になった
方々にポイント配分させていただきます。
でも本当に皆さん全員に感謝しています。
ありがとうございました！！！

ちなみにquiz3の回答は以下のように成りました。
+---+---+---+
|283|671|945|
|976|548|231|
|415|392|876|
+---+---+---+
|567|419|382|
|834|267|159|
|192|835|467|
+---+---+---+
|321|786|594|
|758|924|613|
|649|153|728|
+---+---+---+

回答No.7

BLUEPIXY

#6>現段階で私の作ったのが理詰め（だけ）でやってくれるやつです。
昔、理詰め（だけ）でやってくれるやつを作ったことがあるのですが、
＃６の問題は解けましたよ。
692381547
435627189
187549236
918274653
574936821
263158794
746892315
321465978
859713462

お礼

昨晩から改良を続けていました。でANO.6の問題が解けました！
BLUEPIXYさんのと全く同じ回答になったのでひと安心です。
…ダメだったところがわかり、それでもう完璧かと思ったのですが
（課題の問題は３問あって、１，２は解けた）
最後のquiz3を実行したら解けませんでした。。。
たびたび申し訳ないのですがBLUEPIXY様の理詰めで説くプログラムは下の問題は解けますでしょうか？
もう正直これ以上何をしていいのかわかりません。。。
正直皆様にソースを見て指摘してもらいたいのですが課題提出用ですしこのページも普通に検索に引っかかるので
躊躇われるところです。なにかいい手があれば良いのですが。

+---+---+---+
|200|670|000|
|006|000|201|
|400|000|800|
+---+---+---+
|500|009|300|
|030|000|050|
|002|800|007|
+---+---+---+
|001|000|004|
|708|000|600|
|000|053|008|
+---+---+---+
本当に申し訳ないのですができればお願いいたします。。。

補足

お礼補足です。一番大事なことが抜けていました。
回答ありがとうございました。長々と付き合っていただけて本当に助かっています。。。

回答No.6

Qwerty-36

数独をとくプログラム、Win32版、作りました。
そこそこ動いています。
9×9をブルートフォースではなく、自分が"1"だと確定したら、「関連するセル」に『僕は"1"になったよ』って、メッセージを飛ばせば良いんです。
で、そのメッセージを受けたセルは、「あ、こいつから"1"だってメッセージ受けたから自分のセルの候補リストから"1"を消そう」、で次に「候補リストを見たら5しか残ってないぞ」、「じゃ自分は"5"だと宣言してしまえ」で上に戻ります。

判るかなぁ。こんな物で(^^;)。

確定したセルがメッセージを出し、受け手がメッセージで自分のリストを見直し、その結果、確定したセルが増えていく。

面白いですよ。問題を入力していると、パラパラとセルの内容が書き込まれていきます。

# メッセージを飛ばすのに、WM_Userを使ったので、上手く動かないときがありますが。

お礼

これだとやはり限界がないですか？
自分的にはやはり総当りは不可欠だと思っているのですが。
現段階で私の作ったのが理詰め（だけ）でやってくれるやつです。
例えば
600 000 540
030 027 000
000 009 000

000 000 053
004 000 800
260 000 000

000 800 000
000 460 070
059 000 002

という問題ですと（'0'は空白を示します）
私のお馬鹿プログラムは

600 000 540
430 027 000
000 049 000

000 004 053
004 000 800
260 000 004

046 890 000
000 460 070
059 000 402

までしか突き止めてくれません。
ちなみにこのお馬鹿プログラムでも
http://www.nikoli.co.jp/puzzles/1/
の問題はきちんと完答してくれます。

補足

***********************************
***********************************
すみません、ここまでやっておいて何なのですが
先ほどANo.6に対するお礼にかいたプログラムの出力結果と
同じものを新に問題として作って(datファイルにして)再度同じプログラムに
解かせたところなんと一歩前進していました。

そこで何かおかしいところがあると思いテストをしていくと
必須であると思っていた関数の一つを/*.....*/でくくっても
出力に変わりなかったのです。つまりそれがおかしいということです。
もしかしたら＋αでうまくいけるかもしれません。
とりあえず今までの自分にとんちんかんなミスがあったことをお詫びいたします。
申し訳ありませんでした。
ただ今回でバックトラックなどについて少し詳しくなったので無駄ではないと思っています。
*****************************************

回答No.5

chirubou

多分答えには全くなっていないとは思うのですが。

私ならバックトラックを自動で行ってくれる Prolog を使います。

お礼

なるほど。。。wikiで調べてみました。
確かにProlog（使ったことないです)だと簡単に実現できるそうですね。
もしPrologとやらに触れる機会あれば試して見ます。
ご回答ありがとうございました。

補足

ちなみにこの数独のプログラムは大学のＣの課題ですので
やはりＣでやらなければいけません。。。

回答No.4

Trick--o--

注意：ナンバープレースの解き方に触れています。読みたくない方はご注意ください。
http://puzzle.lavot.com/java/numberplace/algorithm.html

仮定したものを覚えておけばいいじゃない。
理詰めで解けなくなった時点で、問題が成立していないと思うが。

お礼

これはもう少し突き止めてみることにします。
ありがとうございました！

回答No.3

BLUEPIXY

#1>全部で3*3*2=18通りの組み合わせがありますが、それらを全て試させるには
例えば、
Ａマスで２通り、Ｂマスで３通りある場合、
Ａの状態で（仮に）１つ決定して問題を解かせると、
・問題が解けた
・問題が解けずに行き詰まった
という状態になります。
問題を解く手順として、問題が解けずに行き詰まった場合の手順として、決定していないマスの手を１つ選んで仮に進めるという手法を組み込み済みなので、Ａが埋まった状態でＢのマスの状態を調べる状態になります。
そのように再帰的に手順が呼び出されて（メモリがオーバーフローしないで正解があるなら）いつか結果が求まります。
その場合、
最初のＡマスの１つの探索が終わったとき次の（残りの）１つの手を調べるようになっていれば、
結果的に、全ての組み合わせを調べることになります。（樹形図を描いたような感じで、プログラムが再帰的に木を深さ優先でたどる）

お礼

再帰を使えば確かにうまくできそうです。。。が正直いまいち再帰がわかっていない私。。。
でも特に不確定マスの個数が状況による、となると再帰を頼らずにはいられなさそうです。
もしくはwhile(1)で永遠ループを作って、あるifの元でbreakさせるか。。。
http://www.pro.or.jp/~fuji/puzzlestudy/sudoku.html
のサイトのbakadoku.cというファイルだと再帰を使ってシンプルに
実現しているようなのですが正直ソースを見てもよく仕組みがわかっていません。。。

ご解答ありがとうございました。

回答No.2

dra2jp

数独ですかぁ、ひゃ～難しそうですねぇ。
解き方がわからないのでプログラムかけませんけど

＞マスＡの候補が1,3,5、マスＢの候補が3,4,7、マスＣの候補が8,9、出会った場合、全部で3*3*2=18・・・

の部分だけお答えしましょう。
3*3*2の18通りの組み合わせの計算は３つのfor文で組み合わせ可能です。

(1,3,5) * (8,9) * (3,4,7) の18通りの組み合わせ方(i*j*s)をみてみましょう。
(1,3,5)にあたる部分がi
(8,9)にあたる部分がj
(3,4,7)にあたる部分がs
です。

for(i=1;i<=5;i+=2){
___for(j=8;j<=9;j++){
______for(s=3;s<=5;s++){
_________if(s==5)
____________s=7
_________(処理)
______}
___}
}

i,j,sにマスA,B,Cの条件を適応させれて(処理)で処理させれば組み合わせのプログラムは出来ます。

数独面白そうですね。
よければプログラムも見せてもらいたいです＾＾

お礼

御礼遅れました。
しかし回答の方法ですと、例の場合は前半の(1,3,5),(8,9)が等差数列になっているので
forループで簡潔に実現できますが、これが実際は(1,4,9)だか(1,2,9)だか、そもそも
仮定するマスの数すら未定なのですから(今回の例がたまたま３つだった）forループでやるのは無理ではないでしょうか？
もし私の思い違いであれば教えてください。お願いいたします。

補足

すみません、お礼の追記です。
プログラムソースは（私のアルゴリズムが泥臭すぎるというのも手伝って）
400行を越えてしまっているのでこの場での公開は辞退させてください。
すみません。それとご回答ありがとうございました。

回答No.1

BLUEPIXY

＞回答が１通りでない、
場合は、問題に問題ありで、問題として不適当だと思いますが、
単純に、
＞丹念に各マスに対してそのマスが属するブロック、列、行を調べて最後まで１であるflagを探すようにしたのです。
だと上級問題が解けないですね。
言われるようにトラックバックを実装する必要があると思います。
数独を解くルーチンの独立性を高めて、
"１であるflagを探す手順"で行き詰まった段階で
今考えている９×９のフィールドのコピーを作り、可能性リストの小さいものから
仮にその１つを入れたものを作成してその問題を解かせてみて完成するようならＯＫみたいにすればどうでしょう

お礼

ご解答ありがとうございます！

>>可能性リストの小さいものから
>>仮にその１つを入れたものを作成してその問題を解かせてみて

ここの部分でとまどっています。確かに候補が３つ以下、２つ以下のマスを
見つけることは出来ます。ですが例えばマスＡ，Ｂ，Ｃを仮定するとして、マスＡの候補が1,3,5、マスＢの候補が3,4,7、マスＣの候補が8,9、出会った場合、
全部で3*3*2=18通りの組み合わせがありますが、それらを全て試させるにはどのような
アルゴリズムを組めばよいのでしょうか・・・。