解決済み

数独をとくプログラム

  • 困ってます
  • 質問No.2268308
  • 閲覧数1636
  • ありがとう数12
  • 気になる数0
  • 回答数9
  • コメント数0

お礼率 42% (950/2238)

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

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

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

質問者が選んだベストアンサー

  • 回答No.8

ベストアンサー率 50% (3003/5914)

#7の問題は、私のプログラム(制約によるマス埋めのもの)でも解けませんでした。
結果:
+---+---+---+
|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|
+---+---+---+
#1でも言ってますけど結局上級問題は単なる制約によって埋めていくだけでは解けない問題があると思います(私のプログラムの抜けがあるのかもしれませんが)。
ちなみに
解け残りの左上の正方ブロック
+---+
|200|
|906|
|400|
+---+
の部分で
+---+
|2X0|
|906|
|400|
+---+
+---+
|200|
|906|
|4X0|
+---+
のXの部分で1が見合い(どちらかに1が入る)になっています。
上の方に1を入れたら手詰まりで
下の方に1を入れたら解けました。
+---+---+---+
|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|
+---+---+---+
なので、やはり、そういう仮にどこそこへXを入れたらどうなるという仮の実行をしてみれば解けるということになります。
普通、手詰まりになってからそのような探索を始めれば、
数独自体制約が厳しいパズルなので、全探索する前に解が求まると思います。(なので、それほど深い再帰にはならないと思われます)
解が複数あることを調べる場合には、全探索しないといけないと思われますが、その場合は、見つかった解を見つからなかったとして(バックトラックして)探索を続けるということになろうかと思います。
メモリが豊富に使える昨今では多分大丈夫じゃないでしょうか。
ただ、数独のパズルとしては、解が2つ以上あるというのは、ミスだと思うので、全探索する必要はないと思っています。
Be MORE 7・12 OK-チップでイイコトはじまる

その他の回答 (全8件)

  • 回答No.9

ベストアンサー率 0% (0/3)

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

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

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

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

ご健闘ください
お礼コメント
R-gray

お礼率 42% (950/2238)

わぁ。。。。。

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

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

ちなみに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|
+---+---+---+
投稿日時 - 2006-07-13 23:40:40
  • 回答No.7

ベストアンサー率 50% (3003/5914)

#6>現段階で私の作ったのが理詰め(だけ)でやってくれるやつです。
昔、理詰め(だけ)でやってくれるやつを作ったことがあるのですが、
#6の問題は解けましたよ。
692381547
435627189
187549236
918274653
574936821
263158794
746892315
321465978
859713462
補足コメント
R-gray

お礼率 42% (950/2238)

お礼補足です。一番大事なことが抜けていました。
回答ありがとうございました。長々と付き合っていただけて本当に助かっています。。。
投稿日時 - 2006-07-13 15:30:44
お礼コメント
R-gray

お礼率 42% (950/2238)

昨晩から改良を続けていました。でANO.6の問題が解けました!
BLUEPIXYさんのと全く同じ回答になったのでひと安心です。
…ダメだったところがわかり、それでもう完璧かと思ったのですが
(課題の問題は3問あって、1,2は解けた)
最後の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|
+---+---+---+
本当に申し訳ないのですができればお願いいたします。。。
投稿日時 - 2006-07-13 15:30:34
  • 回答No.6

ベストアンサー率 25% (58/226)

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

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

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

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

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

お礼率 42% (950/2238)

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

そこで何かおかしいところがあると思いテストをしていくと
必須であると思っていた関数の一つを/*.....*/でくくっても
出力に変わりなかったのです。つまりそれがおかしいということです。
もしかしたら+αでうまくいけるかもしれません。
とりあえず今までの自分にとんちんかんなミスがあったことをお詫びいたします。
申し訳ありませんでした。
ただ今回でバックトラックなどについて少し詳しくなったので無駄ではないと思っています。
*****************************************
投稿日時 - 2006-07-13 00:36:03
お礼コメント
R-gray

お礼率 42% (950/2238)

これだとやはり限界がないですか?
自分的にはやはり総当りは不可欠だと思っているのですが。
現段階で私の作ったのが理詰め(だけ)でやってくれるやつです。
例えば
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/
の問題はきちんと完答してくれます。
投稿日時 - 2006-07-13 00:16:42
  • 回答No.5

ベストアンサー率 37% (189/502)

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

私ならバックトラックを自動で行ってくれる Prolog を使います。
補足コメント
R-gray

お礼率 42% (950/2238)

ちなみにこの数独のプログラムは大学のCの課題ですので
やはりCでやらなければいけません。。。
投稿日時 - 2006-07-13 00:03:47
お礼コメント
R-gray

お礼率 42% (950/2238)

なるほど。。。wikiで調べてみました。
確かにProlog(使ったことないです)だと簡単に実現できるそうですね。
もしPrologとやらに触れる機会あれば試して見ます。
ご回答ありがとうございました。
投稿日時 - 2006-07-13 00:03:42
  • 回答No.4

ベストアンサー率 20% (413/2034)

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

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

お礼率 42% (950/2238)

これはもう少し突き止めてみることにします。
ありがとうございました!
投稿日時 - 2006-07-13 00:02:25
  • 回答No.3

ベストアンサー率 50% (3003/5914)

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

お礼率 42% (950/2238)

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

ご解答ありがとうございました。
投稿日時 - 2006-07-12 23:59:12
  • 回答No.2

ベストアンサー率 25% (18/72)

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

>マスAの候補が1,3,5、マスBの候補が3,4,7、マスCの候補が8,9、出会った場合、全部で3*3*2=18・・・

の部分だけお答えしましょう。
3*3*2の18通りの組み合わせの計算は3つの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の条件を適応させれて(処理)で処理させれば組み合わせのプログラムは出来ます。

数独面白そうですね。
よければプログラムも見せてもらいたいです^^
補足コメント
R-gray

お礼率 42% (950/2238)

すみません、お礼の追記です。
プログラムソースは(私のアルゴリズムが泥臭すぎるというのも手伝って)
400行を越えてしまっているのでこの場での公開は辞退させてください。
すみません。それとご回答ありがとうございました。
投稿日時 - 2006-07-12 23:54:03
お礼コメント
R-gray

お礼率 42% (950/2238)

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

ベストアンサー率 50% (3003/5914)

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

お礼率 42% (950/2238)

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

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

ここの部分でとまどっています。確かに候補が3つ以下、2つ以下のマスを
見つけることは出来ます。ですが例えばマスA,B,Cを仮定するとして、マスAの候補が1,3,5、マスBの候補が3,4,7、マスCの候補が8,9、出会った場合、
全部で3*3*2=18通りの組み合わせがありますが、それらを全て試させるにはどのような
アルゴリズムを組めばよいのでしょうか・・・。
投稿日時 - 2006-07-11 02:21:48
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


より良い社会へ。感謝経済プロジェクト始動

ピックアップ

ページ先頭へ