- 締切済み
数独を解くアルゴリズム
Foxtrot_OWの回答
- Foxtrot_OW
- ベストアンサー率38% (19/49)
>同じアルゴリズムが作りたいんです 提示されたサイトに書かれているとおり、SourceForgeでソースコードが公開されているそうですよ？まったく同じアルゴリズムにするなら、そのソースコードを読むしかありません。 https://sourceforge.net/projects/judoku >再帰呼び出しなしで なぜでしょうか？ >undoメソッドがあるので、これを使って前のセルに戻る 前のセルに戻るのはどのようなものでしょうか？それとも、解答を探す手順を一手手前に戻るということでしょうか？ このようなundo/redoを実現するもっとも単純でどんな場合にも使える方法は、すべての手順の状態を保存しておくことです。そうすればどの段階にでも戻れますから。 また、n手目のm手前に戻りたければ、また最初から実行しなおして(n-m)手目で停止するという方法もあるかと思います。 >色々ためして見ましたが、 どのような手段を試したのでしょうか？ >うまくいくいきません どううまくいかなかったのでしょうか？
関連するQ&A
- 数独(ナンプレ)の解き方(アルゴリズム)
プログラミングの宿題で、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
- ベストアンサー
- 数学・算数
- 数独の３国同盟のアルゴリズム教えて下さい
はじめまして！ C言語を勉強して３ヶ月になります、現在、勉強のつもりで数独の解法プログラムを作っています が、解法プログラムを基本から順に実装しようと基本から２国同盟まではわかったのですが３国 同盟以上（まずは自明のNaked Tripleからお願いします<(_ _)>）のアルゴリズムがどうしても 解らずプログラムが書けません。マスの絞り込み方です。例えば横ラインのマスで候補数が２、 ３個のマスに絞って・・・次ですが３個のマスには３種類しか入らない。・が解りません！目 で見ればわかりますがそれをプログラムする方法）NAKED（見える）Tripleだけで良いので考え方 を教えて下さい。２日間詰まってます(>< ) どうぞ宜しくお願いします<(_ _)> （例） Ｒ３横一行だけを考えたときにR3Ｃ1(６，８）、Ｒ３Ｃ２（１，６）、Ｒ３Ｃ３（2,3,4）、Ｒ３ Ｃ４（1,8）、Ｒ３Ｃ５（1,2,4,5,6）・・・で（）内は候補数です。これはＣ１、Ｃ２、Ｃ４で （１，６，８）の３国同盟ができています。Ｒ３Ｃ５の（１，６）は削除され候補数（２，４， ５）となる。悩んでいるのはＣ１、Ｃ２、Ｃ４を同盟決定のアルゴリズムです。 「異なる3つのマスを選んだときに、それら3マスに入れられる候補の種類が3種類であること」を プログラム上でどう表現したら良いかずっと詰まってます(>< ) どう考えたらこの３つのマスを決定（同盟関係）できるのでしょうか？宜しくお願い致します<(_ _)>
- ベストアンサー
- C・C++・C#
- 「世界で一番むつかしい数独の問題」・・・
東大の渡辺氏のサイトに「世界で一番むつかしい数独の問題」というのが載っているのを見つけました。フィンランドの数学者、Inkara氏が２０１０年、２０１２年に発表したものだそうです。 http://apollon.issp.u-tokyo.ac.jp/~watanabe/sample/sudoku/index_j.html （A）２０１０年 （B)２０１２年 ００５ ３００ ０００ ８００ ０００ ０００ ８００ ０００ ０２０ ００３ ６００ ０００ ０７０ ０１０ ５００ ０７０ ０９０ ２００ ４００ ００５ ３００ ０５０ ００７ ０００ ０１０ ０７０ ００６ ０００ ０４５ ７００ ００３ ２００ ０８０ ０００ １００ ０３０ ０００ ５００ ００９ ００１ ０００ ０６８ ００４ ０００ ０３０ ００８ ５００ ０１０ ０００ ００９ ７００ ０９０ ０００ ４００ ※空白には「０」を入れています。 渡辺氏はこれよりもむつかしい問題を作ろうと考えたようです。ス＾パーコンピュータを動かして作ったのが次の問題です。 （C)２０１３年３月 ０６１ ００７ ００３ ０９２ ００３ ０００ ０００ ０００ ０００ ００８ ５３０ ０００ ０００ ０００ ５０４ ５００ ００８ ０００ ０４０ ０００ ００１ ０００ １６０ ８００ ６００ ０００ ０００ しかしこれは市販の問題集に載っている上級レベルの問題です。これを「世界で一番むつかしい問題」だと判断して発表したのですから計算機を動かすアルゴリズムに初歩的なミスがあった、または渡辺氏の数独の理解の程度に致命的な欠陥があったということになりそうです。（渡辺氏は自分では数独の問題を解こうとはしていないようです。コンピュータの出した数値だけをそのまま判断材料にしているのです。普通に解けば簡単にわかる不具合が見つからないままになっています。） （C)が簡単に解くことができる問題だったということが分かったので作り直したというものが追記の形で発表されています。 （D)３／２２付け 追記 ０８０ ０００ １５０ ４０６ ５０９ ０８０ ０００ ００８ ０００ ０００ ０００ ０００ ００２ ０７０ ００３ ３００ ８０１ ０００ ９００ １７０ ０００ ６００ ０００ ００４ １５０ ０００ ０９０ Inkara氏の（A)(B)に比べると格段にやさしいです。 「世界で一番むつかしい問題」を作ろうとしている意味とはどういうものでしょう。 数独というゲームとどういう関係があるのかもよくわかりません。 「むつかしい」ということがどういうことかも十分に吟味されているとは思えません。 解くのに必要な時間にはかなりの違いがあります。（B)>(A)>(D）です。でも解くのに必要な時間の違いがむつかしさの違いでしょうか。（B)を解くのには時間がかかります。でもむつかしくはありません。面倒なだけです。同じ論理をただ繰り返し使っているだけです。仮定の段数が多いので場合の数が多くなり、可能性のチェックに時間がかかるのです。ゲームとしての面白さ、むつかしさは時間だけではないはずです。（面倒くさいと思いながらも意地になって解きました。） ゲームとしての面白さは別にして、人の手で解くことのできるギリギリのところはどこらあたりにあるのかを探ることを目的にしているのかもしれません。でも渡辺氏の初めの問題（問題C）は「どうだ人の手では解けないだろう！」という形で発表されているのですから「人の手では解けない問題を作る」ことを目指しているようにも見えます。そうであればもはや数独ではありません。数独から派生した数学の問題だということになります。 そうであれば「むつかしい」の概念規定が重要になります。「むつかしい」というのは解く立場があってのことです。 たとえば初期設定の数字の数Noについて、「唯一解の存在する最低のNoは？」という問題は数学的に設定することは可能でしょう。でも数独の問題として解くときにNoが小さいことはそのままむつかしいにはつながりません。市販の難問問題集の中にNoが１７，１８というような問題ばかり集めているものがあります。でも別の問題集に載っているNoが２２，２３のものよりも易しいのです。 数独、ナンプレの本を出版している人たちはどういう風に考えているのでしょうか。 ２０１０年に発表された問題であれば知れ渡っているはずです。 ゲームとしての数独、ナンプレとは関係がないとして無視しているのでしょうか。 でも数独、ナンプレの内部の話としても「むつかしい」というのは全然吟味されていないように思います。「超難問」とか「究極の難問」、「激辛の難問」とかのタイトルの本がたくさん売られています。むつかしさのレベルはまちまちです。中には鉛筆を縦横に置くだけで解けてしまうような問題まで含まれています。 参考 （B)を解いてみた結果 ８１２ ７５３ ６４９ ９４３ ６８２ １５７ ６７５ ４９１ ２８３ １５４ ２３７ ８９６ ３６９ ８４５ ７２１ ２８７ １６９ ５３４ ５２１ ９７４ ３６８ ４３８ ５２６ ９１７ ７９６ ２１８ ４５２ たぶん間違っていないと思います。 使ったのは紙と鉛筆とマーカーペンだけです。 Ａ４の用紙に書いていけるところまで行きます。 場合分けに入るところからあとはコピーした用紙をたくさん使いました。 どの問題を解くのでも場合分けと仮定が必要です。（Ａ）、（Ｂ）では仮定の積み重ねが必要ですが（Ｄ）では並立的な仮定しか使いません。 一般解法とと言われているものも仮定を使っています。ただ並立的にしか使いません。 「この本の問題を解くのに仮定法は使わない。すべて理詰めで解くことができる」と書いてある本がありますが誤りです。数独、ナンプレの問題の解法は「仮定法」なしでは成り立ちません。
- ベストアンサー
- 数学・算数
- 深さ優先探索（再帰なし＆あり）
深さ優先探索で再帰呼び出しを用いないのと用いるプログラムを書く課題がありまして、まだC言語かけだしの自分にはあまりよくわかりません・・・ どこかにわかりやすいサイトとかってありますでしょうか？アルゴリズムとデータ構造という授業をとっているんですが、教授が妙な関西弁でしかも教え方も上手とはいえない感じなので全然理解が深まらず困っています。周りも１４０人中５０人くらい単位落としてるカンジなんです。周りは「あんなんんじゃ取れない」といってあきらめていってるのが大半なんですが自分は興味もありますし、１度落としているだけに今年は絶対単位を取りたいと意気込んでます。 オーダー、マージソート、リスト、スタック、深さ優先探索などアルゴリズム（Cのプログラムでよく書かされます）についてわかりやすいサイトや書籍がありましたら是非おしえてください。
- ベストアンサー
- C・C++・C#
- 数独を解くアルゴリズム
バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。 コンパイルエラーはありません。 表示の関数は省いてあります。 よろしくお願いします。 #include <stdio.h> #define M 3 //小さいブロックのサイズ #define N M*M //全体のサイズ #define MTX N*N //全体のマス数 int sudoku[N][N]={ {0,2,4,5,0,0,6,0,0}, {0,0,6,3,2,0,0,0,4}, {0,0,5,0,9,0,0,8,3}, {0,0,8,4,0,3,0,0,1}, {0,6,1,9,0,0,4,3,0}, {7,0,0,1,0,0,5,0,0}, {8,3,0,0,4,0,9,0,0}, {4,0,0,0,3,5,8,0,0}, {0,0,7,0,0,9,3,4,0} }; /* 候補がOKかどうかチェック */ int OKkouho(int x, int y, int k) { int i,j; int p,q; for(i=0; i < N; i++){ //その行に候補は入るか if(sudoku[y][i] == k) return 0; } for(j=0; j < N; j++){ //その列に候補は入るか if(sudoku[j][x] == k) return 0; } p = x/M*M; q = y/M*M; //そのブロックに候補は入るか for(j = q; j < q+M; j++){ for(i = p; i < p+M; i++){ if(sudoku[j][i] == k) return 0; } } return 1; } void Solve(int level) { int k; int x,y; if(level >= MTX){ printf("OK"); return; } x = level%N; y = level/N; if(sudoku[y][x]) Solve(level+1); else{ for(k = 1; k <= N; k++){ if(OKkouho(x,y,k)){ sudoku[y][x] = k; Solve(level+1); sudoku[y][x] = 0; } } } } int main(void) { Solve(0); return 0; }
- 締切済み
- C・C++・C#
- アルゴリズムについての質問です
アルゴリズムについての質問です。 以下のようなプログラムを考えています。 プログラムの目的 ある建物で各部屋同士の机の移動を行うため、その労力を最小にする組み合わせを求める。 ※このシステムは他の人が使用することを考え、わかりやすいExcel（VBA）を使用しています。 画像に関して ＜図１＞は「No（部屋）」の距離（数字が小さい方が労力が少ない）を表しています。 ※プログラムでこの表は出力されています ＜図２＞のようにA群とB群があり、A群からB群に移動する（複数移動も含む）場合について考えます。 ＜図３＞のような最小の組み合わせを探します。 正しい結果は出るのですが、1件増えるだけで何倍何十倍と時間がかかってしまいます。 多少結果は妥協して(最小に近い値)でも処理を早くしたいと思っていますが、そのアルゴリズムが思いつきません。 作成したプログラムを下記にありますので、アドバイスをお願いいたします。 作成したプログラムで処理を遅くしている原因があれば指摘もお願いします。 ---現在作成したプログラムです。（すべてのパターンを検証）----------------- Dim 重みtab As Variant Dim t01(100) As Integer '←A群が、「t01(1)」から順に入っています。 Dim t02(100) As Integer '←B群が、「t02(1)」から順に入っています。 Dim ttt(100) As Integer '←B群を並び替えた結果が入ります。 Sub 計算(移動数 As Integer) '「移動数」は「t01」「t02」の要素の数 Dim t03(100) As Integer Dim a As Integer 重みtab = Range("重み表") 'Range("重み表") は ＜図１＞の「No」を含まないセル '仮の最小の計算-------- min = 0 For a = 1 To 移動数 min = min + 重みtab(t01(a), t02(a)) ttt(a) = a Next '---------------------- Call 再帰関数(移動数, t03, 1) 'Sheet2に出力---------- For a = 1 To 移動数 Sheets("Sheet2").Cells(a, 1) = t01(a) Sheets("Sheet2").Cells(a, 2) = t02(ttt(a)) Next '---------------------- End Sub Sub 再帰関数(移動数 As Integer, t03() As Integer, cnt1 As Integer) Dim cnt2 As Integer Dim flg As Boolean For a = 1 To 移動数 flg = True For b = 1 To cnt1 - 1 If t03(b) = a Then flg = False End If Next If flg Then t03(cnt1) = a If cnt1 < 移動数 Then cnt2 = cnt1 cnt1 = cnt1 + 1 Call 再帰関数(移動数, t03, cnt1) cnt1 = cnt2 Else Call 処理(移動数, t03) End If t03(cnt1) = 0 End If Next End Sub Sub 処理(移動数 As Integer, t03() As Integer) ’最小であるか確認 Dim a As Integer Dim b As Integer For a = 1 To 移動数 b = b + 重みtab(t01(a), t02(t03(a))) Next If min > b Then min = b For a = 1 To 移動数 ttt(a) = t03(a) Next End If End Sub
- ベストアンサー
- Visual Basic
- エクセルのVBAでリストに値をセット
Office２００３ エクセルのVBAのプログラムで入力規則のリストを 生成できるような関数、方法はありませんか？ このセルで選択された値に紐づいたデータ郡を次の(横の）セルで プルダウンリスト（入力規則のリスト）を自動生成するというものです。 今回フォームの機能（コンボボックスなど）は使用しません。 よろしくお願いいたします。
- ベストアンサー
- オフィス系ソフト
- 再帰的(リカーシブ)プログラムの説明について。
以下は、再帰的(リカーシブ)プログラムの説明を記載しました。 この説明文でおかしい箇所の添削をお願い出来ないでしょうか？ 宜しくお願い致します。 以下からになります。 再帰的(リカーシブ)プログラムとは、プログラムの中から自分自身を呼び出して実行することを再帰的(リカーシブ)アルゴリズムといい、この形式で再帰呼び出しを行うプログラムのこと。 まずは、再帰的アルゴリズムについて、例を使って説明を行いたい。 主プログラムとサブルーチンaがある。 主プログラムは、文字通り、主(メイン)となるプログラム。 サブルーチンは、主プログラムが呼び出して利用する処理をひとまとめにしたもの。 文字通り、サブとなる処理を行う。 主プログラムには、CALL aという命令が記述されている。 これはサブルーチンaを読み出すという命令。 この再帰的プログラムは、処理が終わったら、読み出された場所に帰っていく。 このため、戻り場所を記憶しておかないと帰る事が出来ない。 この戻り場所を記憶するのが、LIFO方式による記憶領域になる。 LIFO方式の記憶領域だから、スタック領域になる。 スタック領域だから、後入れ先出しで戻り場所を記憶していく。 まずは、1回目の呼び出しとして、主プログラムがサブルーチンaを呼び出している。 1回目の戻り場所を記憶しておく。 次にサブルーチンaを見ると、CALL a、つまり自分自身を読み出している。 これが2回目の読み出し。 このように自分自身を呼び出すことを再帰呼び出しという。 同じプログラムの中で自分自身を読み出しているのだが、コンピューターは、あたかも別のサブルーチンがあるように処理が行われている。 この場合、それぞれの処理で、別の変数を用意しながら処理を行う。 このサブルーチンで処理が終わった場合にも、もとに戻る必要がある。 これは2回目の呼び出しになるため、2回目の戻り場所を記憶しておく。 更に、3回目として再びサブルーチンaを呼び出す。 3回目の戻り場所を記憶し、また別の変数を用意しながら処理を行う。 ここで最後のサブルーチンで処理が終わったとする。 処理が終わったら、呼び出された場所に戻る。 戻り場所の記憶を見てみると、上から戻る順番に記録されていることがわかる。 戻り場所はLIFO方式、後入先出しで記録されているから、最後に呼び出した3回目の戻り場所が1番上に記録され、次に2、最後に1が記録されている。 最初は戻り場所を記憶した記憶領域を参照して、3回目に呼び出された場所に戻る。 ここで3の戻り場所が消える。 そして引き続き処理が行われる。 次に、2回目に呼び出した処理が終わり、2回目に呼び出された場所に戻り、2の戻り場所が消える。 また引き続き処理が行われ、1回目に呼び出した処理が終わり、1回目に呼び出された場所(主プログラム)に戻り、1の戻り場所が消える。 そして処理が行われ、プログラム全体が終了する。 このように、プログラムの中で自分自身を呼び出し、戻り場所を記憶しながら実行するようなプログラムを再帰的(リカーシブ)プログラムという。
- ベストアンサー
- その他（プログラミング・開発）
- Excel！ リストから選択！
Excelの「リストから選択」で質問です。 次のようにA1～B5セルにデータが入っています。 Ａ Ｂ 1 大変よい (1) 2 良い (2) 3 普通 (3) 4 もう少し (4) 5 悪い (5) これらを別のセルにて「リストから選択」をするとＡ列が表示され、 選択するとセルにはＢ列が表示されるという設定はできるのでしょうか。 この例の場合、リスト表示をさせると 大変よい 良い 普通 もう少し 悪い が表示され、「大変よい」を選択すると、「(1)」が表示されるような仕組みです。 どなたか教えていただけませんでしょうか。よろしくお願いいたします。
- ベストアンサー
- オフィス系ソフト
- Excel 入力規則と手入力の差の怪
入力規則を使用したセルがあります（型は「h:mm」です）。 次のような15分単位の時間のリストです（型は「h:mm」です）。 「18:00」「18:15」「18:30」 リスト以外の入力もできるように、エラーメッセージタブのチェックははずしてあります。 ここでリストより「18:15」と選択し、セルの型を「数値」に変更した場合、 セルの表示は「0.76041666666666800・・・・」となります。 別途同様のセルを使用し、リストからは選択せず「18:15」を直接手入力し、セルの型をセルの型を「数値」に変更した場合、 セルの表示は「0.76041666666666700・・・・」となります。 リストから選択した場合、手入力した場合で値が変わってしまうのはなぜでしょうか。 この後、別の式でこの値を利用したいのですが結果が変わってしまい困っています。 何か方法はないでしょうか。
- ベストアンサー
- その他([技術者向] コンピューター)