数独をとくプログラム

Question

Ｃ初心者です。大学生です。
タイトルの通り、Ｃで数独を解くプログラムを考えています。
数独については
http://www.nikoli.co.jp/puzzles/1/
をご参照ください。

で、数独にも難易度があり、初めからある程度数字が埋まっている（簡単な）
問題を解くプログラムは作ることが出来ました。
単純に、各マスの構造体Cellに対してsign[1],sign[2],,,,,sign[9]を定義し、
それが１なら可能性あり、０なら可能性なし、として
（例えばsign2]==1,sign[5]==0ならそのマスは２になる可能性はあるが５になることはない）
丹念に各マスに対してそのマスが属するブロック、列、行を調べて最後まで１であるflagを探すようにしたのです。

しかし初めから埋まっている数字が少ないと（難しいと）そもそも回答が１通りでない、
などの理由から上記のアルゴリズムでは解くことが出来ません。
あきらかにどこかをあてずっぽに仮定する作業（バックトラック？）
が必要になりそうです。
・・・が、それをどうやって実現したらいいかで行き詰っています。
どうか知恵を貸してください。よろしくお願いいたします。。。

BLUEPIXY · Accepted Answer

＃７の問題は、私のプログラム（制約によるマス埋めのもの）でも解けませんでした。
結果：
+---+---+---+
|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|
+---+---+---+
なので、やはり、そういう仮にどこそこへＸを入れたらどうなるという仮の実行をしてみれば解けるということになります。
普通、手詰まりになってからそのような探索を始めれば、
数独自体制約が厳しいパズルなので、全探索する前に解が求まると思います。（なので、それほど深い再帰にはならないと思われます）
解が複数あることを調べる場合には、全探索しないといけないと思われますが、その場合は、見つかった解を見つからなかったとして（バックトラックして）探索を続けるということになろうかと思います。
メモリが豊富に使える昨今では多分大丈夫じゃないでしょうか。
ただ、数独のパズルとしては、解が２つ以上あるというのは、ミスだと思うので、全探索する必要はないと思っています。

swimeye · Answer

＃７の問題は、手作業ですが理詰めだけでとけました。
また、＃４さん回答にあるサイトにJava Appletがあり、
そちらでも解けるようです。
このサイトは仮定（背理法）を使う機能もあるようですが、
この機能なしでも解けました。

素人作成の問題はともかく、プロの作った問題は理詰めで解けることが
特徴のひとつです。
手元にニコリ社の数独の問題集（難問ばかり）がありますが、
理詰めで解けることが明記されています。
中には上記のサイトでも理詰めだけでは解けないものがありますが、
何とか自力では理詰めで解けたので、"仮定を入れないと解けない"
という発想は捨てたほうがよいでしょう。

課題の趣旨がコーディング技術だけならいいですが、
アルゴリズム考案を含むなら、減点対象にもなりかねませんので。

考え方がまったくわからなくて、他人に聞くことが反則に
ならないなら、＃４さんのサイトを見るのが早いですが、
その内容の説明なり、もう少し軽いヒントなり、
多少のアドバイスはできます。

ご健闘ください

参考URL：http://puzzle.lavot.com/java/numberplace/index.html

BLUEPIXY · Answer

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

Qwerty-36 · Answer

数独をとくプログラム、Win32版、作りました。
そこそこ動いています。
9×9をブルートフォースではなく、自分が"1"だと確定したら、「関連するセル」に『僕は"1"になったよ』って、メッセージを飛ばせば良いんです。
で、そのメッセージを受けたセルは、「あ、こいつから"1"だってメッセージ受けたから自分のセルの候補リストから"1"を消そう」、で次に「候補リストを見たら5しか残ってないぞ」、「じゃ自分は"5"だと宣言してしまえ」で上に戻ります。

判るかなぁ。こんな物で(^^;)。

確定したセルがメッセージを出し、受け手がメッセージで自分のリストを見直し、その結果、確定したセルが増えていく。

面白いですよ。問題を入力していると、パラパラとセルの内容が書き込まれていきます。

# メッセージを飛ばすのに、WM_Userを使ったので、上手く動かないときがありますが。

chirubou · Answer

多分答えには全くなっていないとは思うのですが。

私ならバックトラックを自動で行ってくれる Prolog を使います。

Trick--o-- · Answer

注意：ナンバープレースの解き方に触れています。読みたくない方はご注意ください。
http://puzzle.lavot.com/java/numberplace/algorithm.html

仮定したものを覚えておけばいいじゃない。
理詰めで解けなくなった時点で、問題が成立していないと思うが。

BLUEPIXY · Answer

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

dra2jp · Answer

数独ですかぁ、ひゃ～難しそうですねぇ。
解き方がわからないのでプログラムかけませんけど

＞マスＡの候補が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の条件を適応させれて(処理)で処理させれば組み合わせのプログラムは出来ます。

数独面白そうですね。
よければプログラムも見せてもらいたいです＾＾

BLUEPIXY · Answer

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

数独をとくプログラム

＃７の問題は、私のプログラム（制約によるマス埋めのもの）でも解けませんでした。

＃７の問題は、手作業ですが理詰めだけでとけました。

#6>現段階で私の作ったのが理詰め（だけ）でやってくれるやつです。

この回答への補足