以前、数独を解くプログラムに関する質問をさせていただいたものです。数独を解くプログラムを作っております。理由としましては、前回のプログラムはバックトラック法を使用した力技であり、本来の目的である人工知能とは遠くかけ離れていてからです。そのため改めて人間に近いアルゴリズムに沿って解くプログラムを作成することにしました。現在、非常に簡単な問題であれば解ける具合です。6;4、5を満たすのであれば実際に代入7:1へもどるといった具合になっております。(むしろ、これだけです)ですが、難しい問題になってくると5番を満たすことができず、無限ループのようになってしまいます。ここからどういったやり方で難しい問題を解けるようにできるのでしょうか?たくさんの意見お待ちしております。難しい問題になってくると5番を満たすことができず、無限ループのようになってしまいます。数独の仕様だと思います。次のように作りました。1.問題読み込み2.取り合えす空白部分にすべての数字のフラグを立てる3.空白マスを上から順に見ていき、縦、横、同じブロック(3×3)にある数字をフラグから消去4.フラグが1つしかないマスは確定5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定6.3.に戻る7.埋まらない場合はバックトラックで解く7.は難しい問題のときに起こりますので、そこも理詰めで解きたい場合は高度な解法を実装することになります。詳しくは検索してみてください。4年前たいちうさん、みけCATさん、yokoさん回答ありがとうございます。自身の解き方を忠実に再現するのも、無限ループが仕様なのもおっしゃるとおりだと思います。具体的なアルゴリズムを教えていただきありがとうございます。yokoさんの書き方だと2次元配列ではなく3次元配列を使うのでしょうか?どの程度の難易度の問題を解くことができるのでしょうか?空白の数などで難易度を教えていただきたいです。皆さんは人間に近いと思いますか?それとも大きく離れていると思いますか?あくまで率直な意見で構いませんので回答お願いします。プログラムは自分で考えたい気持ちの方が強いので、できればある程度プログラムが完成してからアップして欲しいです。率直な意見で構いませんので回答お願いします。バックトラックの部分が人間らしくないと思います。プログラミングは簡単なのですが。人間が難問を解くための定石が他にもあるので、それを実装すると人間らしいのではないでしょうか。反復深化のような方法を取ると人間らしくなるかも。そこの辺はどっちでもいいか。4年前>プログラムは自分で考えたい気持ちの方が強いので、>できればある程度プログラムが完成してからアップして欲しいです。ご要望あり次第アップいたしますので、その際はご連絡ください。私のプログラムのアルゴリズムは下記の本を参考にしています。DXライブラリでの作成となります。ナンバープレース・お絵かきパズル・ナンバークロスワードのアルゴリズムたいちろうさんが書かれている通り、バックトラックの部分は人間らしくないのはその通りです。そのために>7.は難しい問題のときに起こりますので、そこも理詰めで解きたい場合は>高度な解法を実装することになります。詳しくは検索してみてください。解法まとめに高度な解法が記載されていましたので、バックトラックの部分をこちらに変更すれば人間らしい(理詰めで解ける)となりそうです。次のように作りました。1.問題読み込み2.取り合えす空白部分にすべての数字のフラグを立てる3.空白マスを上から順に見ていき、縦、横、同じブロック(3×3)にある数字をフラグから消去4.フラグが1つしかないマスは確定5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定6.3.に戻る7.埋まらない場合はバックトラックで解くとりあえず、上の1~4までができるプログラムを自分なりに書いてみました。実際に実行すると1マスすら埋めることができません。どこが悪いのでしょうか?突っ込みどころ満載だと思いますがご指摘、ご教授よろしくお願いします。数独プログラムとしてのご指摘はもちろん、変数名や{}の数などどんなことでもご指摘ください。具体的な回答を頂けると助かります。1];//[Line][Column][0]が実際の盤,[1]以降は1で可能性あり。4年前とりあえずコンパイル用stdafx.hです。数独プログラムとしてのご指摘はもちろん、変数名や{}の数などどんなことでもご指摘ください。具体的な回答を頂けると助かります。4年前たくさんのご指摘ありがとうございます。ご指摘を受けてどうするか、またご指摘に対する自分の解釈を載せておきました。引き続き回答お願いします。202行目のmodeが使用されていない→入力の仕方を2種類(ファイル、座標指定入力)に分けていました。ファイル読み込みしか使用しておらず、202行目を削除を忘れていました。217行目、222行目、223行目で、0を入力すると次に進まない仕様にしている意味がよくわからない→数字を埋めているところを定期的に表示したかったからです。0でなければいけない理由がありませんでした。「何か」入力すると次に進むよう修正したいと思います。174行目ではban[Line][Column][Num]ではなく、ban[Line][Column][0]に代入するべきである→表示が全く変わらなかった原因ですね。162行目の前でpossibleNumCountを0に初期化していないので、例えばコード:023456780456789123780123456234567891567891234891234567345678912678912345012345678という問題が解けない→すみません。自分の読解力ではなぜなのか、また、この問題がどういった問題なのかわかりません。引き続き解説お願いします。簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである→これは、data.txtに限らず、ファイル名を入力するとそのファイルを読み込むように変更せよということでしょうか?C++なので、定数は#defineよりconstを使ったほうがよさそう→もともと、C言語で書いておりました。visualstudioを使うことになり半強制的にC++になったがためにこういったミスが(今後も)あると思います。ご指摘なさった点についてはご指摘通り修正したいと思います。縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう→なるほど。<ctime>と書いたほうがよさそう→再びC++ならではミスが出てきました。ご指摘通り修正します。修正次第コードをアップしたいと思います。162行目の前でpossibleNumCountを0に初期化していないので、例えばコード:023456780456789123780123456234567891567891234891234567345678912678912345012345678という問題が解けない→すみません。自分の読解力ではなぜなのか、また、この問題がどういった問題なのかわかりません。引き続き解説お願いします。この盤面で、真っ先にチェックされる一番左上のマスに入る可能性のある数字は、1と9の2個あるため、possibleNumCountは2になり、マスを埋めることはできません。他のマスも埋めることはできません。よって、全くマスを埋めることができないので、このプログラムでは(正しくフラグではなく盤面にNumを代入したとしても)この問題を解くことはできません。簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである→これは、data.txtに限らず、ファイル名を入力するとそのファイルを読み込むように変更せよということでしょうか?いいえ、ファイル名を入力するとそのファイルを読み込むように変更するか、ファイルシステム上のファイルではなく標準入力から読み込むように変更せよということです。縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう→なるほど。for文ですべてチェックするのではなく、見つけたものからフラグを折っていくということであっていますか?確信は持てませんが、多分あっています。以下のように書き換えたところ数独を解くプログラムとして動くようにはなりました。ありがとうございます。1];//[Line][Column][0]が実際の盤,[1]以降は1で可能性あり。0;}ですが以前に指摘されたリストに関して一部実装、変更できていませんので、その点については以下のとおりです。0を入力すると次に進まない仕様にしている意味がよくわからない→数字を埋めているところを定期的に(1回のsolveにつき1回)表示したかったからであり、入力されるものや条件はなんでも良いのですが、何かよい方法ありますか?簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである→実装したつもりなのですが、あっていますか??解釈間違ってますか?C++なので、定数は#defineよりconstを使ったほうがよさそう→すみません。縦、横、3x3をチェックして、そこに書かれている数字が1以上9以下のとき、それをNumberとしてフラグを折るようにすると、計算量が減ってよさそう→すみません。時間ができ次第変更します。<ctime>と書いたほうがよさそう→変更します。難度の高い問題はまだ解けないです。yokoさんの「縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定」は明日には実装しようと思います。上のコードにおいて間隔・隙間が少ないのは気しないでください^^;わざとではなく、今使っているPCとコードを書いているPCが異なり、メールでコードを送ってしまったからです。今後はこのようなことのないようにしたいと思います。見にくくてすみません。簡単に入力を変えられるよう、入力ファイル名をコマンドライン引数で指定できるか、ファイルシステム上のファイルではなく標準入力から読み込める方が好きである→実装したつもりなのですが、あっていますか??解釈間違ってますか?だいたいあっていると思います。input関数のエラーチェックが甘く、例えば100と入力すると強制終了しました。C++なので、定数は#defineよりconstを使ったほうがよさそう→すみません。変更すべきですか?どっちでもいいと思います。1.問題読み込み2.取り合えす空白部分にすべての数字のフラグを立てる3.空白マスを上から順に見ていき、縦、横、同じブロック(3×3)にある数字をフラグから消去4.フラグが1つしかないマスは確定5.縦、横、同じブロックでフラグが1つしかない数字はその箇所を確定6.3.に戻る上のyokoさんの5番を実装したつもりなのですが、以前よりも解けなくなってしまいました。具体的にはボックス・列・行に2つ以上同じ数字を入れてしまうなどです。今は解くことを一番にご指摘いただきたいです。自分のプログラム(特にsolve2とretLineColumn)が間違っているのは事実です。具体的な指摘をいただけると幸いです。回答よろしくお願いします。ポイントを定義します。1];//[Line][Column][0]が実際の盤,[1]以降は1で可能性あり。上手くまとめることができません。上のyokoさんの5番を実装したつもりなのですが、以前よりも解けなくなってしまいました。具体的にはボックス・列・行に2つ以上同じ数字を入れてしまうなどです。