- ベストアンサー
数独をとくプログラム
Qwerty-36の回答
- Qwerty-36
- ベストアンサー率25% (58/226)
数独をとくプログラム、Win32版、作りました。 そこそこ動いています。 9×9をブルートフォースではなく、自分が"1"だと確定したら、「関連するセル」に『僕は"1"になったよ』って、メッセージを飛ばせば良いんです。 で、そのメッセージを受けたセルは、「あ、こいつから"1"だってメッセージ受けたから自分のセルの候補リストから"1"を消そう」、で次に「候補リストを見たら5しか残ってないぞ」、「じゃ自分は"5"だと宣言してしまえ」で上に戻ります。 判るかなぁ。こんな物で(^^;)。 確定したセルがメッセージを出し、受け手がメッセージで自分のリストを見直し、その結果、確定したセルが増えていく。 面白いですよ。問題を入力していると、パラパラとセルの内容が書き込まれていきます。 # メッセージを飛ばすのに、WM_Userを使ったので、上手く動かないときがありますが。
関連するQ&A
- 数独かを判断するプログラム
私が作ろうとしているプログラムは数独を解くものではなく、予めテキストファイルに書かれている横9つ縦9つ、計81個の数字の表が、数独として成り立っているかを判断するものです。 数独についてはこちらで http://ja.wikipedia.org/wiki/数独 or http://sudoku.ara3.net/rule.htm 配列をa[9][9]と用意し、テキストファイルから数字を左上から順に配列に確保していき、その表が数独かどうか判断する段階で躓いています。3×3のマスの中に1～9までの数字が1個ずつあり、かつそのマスが計9つあれば数独なので、まず最初の3×3のマスの中の数字を1～9まで確認し、それを残り8つのマスにも同様に繰り返すだけで良いと思うのですが、その方法がわからず困っています。どなたかお解かりになる方、よろしくお願いします。 例として、テキストファイルの数字の表は以下の様になっています。 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8 ちなみにこの表は数独として成り立っています。
- ベストアンサー
- C・C++・C#
- javaで数独を解くプログラムについて
java初心者です。 学校で数独を解けという問題が出て、問題の意味もまったくわからないのでヒントください。 問題 数独を解くプログラムを作成せよ。ただし、すでに埋まっているマスを入力する時にはi,j,n(改行)でひとつの数字を入力できるものとし、終了条件は、0,0,0を入力するとする。 問題用紙には1問だけ数独が載ってあるのですが、 初歩的な質問で申し訳ありませんが まずこのプログラムは、その1問だけ載っているマスが少し埋まっているプログラムを打ち込んでから解くプログラムを考えるのでしょうか？ 普通、数独を解くプログラムとは、空いているマスにキーボード入力して、解くのでしょうか？それとも自動に動いて解くのでしょうか？ はじめにプログラムをコンパイルしたときにどう言葉が出るようにすればようのでしょうか？ 終了条件0,0,0とは、000を入力したら終わる？ということでしょうか？ マスを作って、クリックすると数字が…というようなjavaは習ってなくコマンドプロントでコンパイルだけなので、数字を打って入力、エンターというだけで解くのだと思うのですが、まったくわからないです。 根本的にわからなくてすいません。 ぜひご回答よろしくおねがいします。
- 締切済み
- Java
- 数独(ナンプレ)の解き方(アルゴリズム)
プログラミングの宿題で、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#
- エクセルＶＢＡで数独
エクセルのＶＢＡを使って、ナンバープレイス（数独？）の問題を創りたいのですが、どうすれば良いでしょう？ 一応、以下の条件で自分で組んでみました。 ○各マス目で、「縦９マス」「横９マス」「３×３マス」中に有る数字を【１～９】内から消去し、残った数字内からランダムで挿入する数字を決定する。 ○処理中に、どうしても決定できないマス目が発生した場合は、決定済みのマス目をある程度チャラにし（処理を戻って）やり直す。 ○上記方法で、１～８１までのマス目を埋めていく。 ○最後に、適当な数のマス目の数字を消去する。 一問作成するのに結構な時間がかかる上、時には完成しない（やり直し続ける）事態が発生します。 何か良い方法（アルゴリズム？）が有ったらご教示願います。 （…アルゴリズムを質問するのは、カテゴリー違いでしょうか？）
- ベストアンサー
- オフィス系ソフト
- 迷路プログラム
迷路プログラムの応用問題なのですが、上手くいかずに困っています。 問題 2次配列を用いて、縦横X,Yマスの迷路を作ります。 マスの数はX,Y共に最大100までの値であれば、任意の数が振れます。 迷路の一番左下がスタートS、一番右上がゴールGになります。 マスへは上下左右にしか移動出来ません。 迷路の中には任意で入力したXマスがあり、Xが入っているマスには移動出来ません。 S,G,Xが入っていないマスには、1～9までの数字を任意に入力します。 それぞれの数字は、そのマスに移動するためにかかるコストを表しています。 スタートからゴールまで、コストがもっとも小さくすむルートのコストを出力するプログラムを作りたいです。 また、Xマスでゴールが不可能な場合は-1を返します。 単純にゴールを目指すのと違い、コストがあると遠回りをしなければならない可能性があるので、そのアルゴリズムが思いつきませんでした。 例 11*7マスの迷路の場合 マスの数：11 7 迷路の値の入力： 7 9 3 3 6 3 X X 7 9 G 1 1 3 2 6 6 8 4 8 4 5 7 2 9 1 3 4 8 4 9 8 9 9 7 4 2 5 X 8 6 9 9 4 4 7 3 8 X 8 X 5 7 X 7 1 7 1 8 5 6 5 9 5 6 2 S 5 5 2 9 4 2 2 9 5 1 出力： 最小コストは59 迷路からゴールに進むだけのプログラムは作れたのですが、応用問題としてコストが入ると急に難しくなりました。 コストが絡むとどういうアルゴリズムで動けばいいのか分かりません。アドバイスをお願いします。
- ベストアンサー
- C・C++・C#
- 数独の問題レベル決定のコツ
９×９マス全てに数独のルール通り、重複無く「１～９」の数字を入れた後、適当数（一般的な問題で有る位）の空白を作り問題を完成させたいのです。 上記のやり方で、回答が１つだけになるようにしたい時、どのようにに空白を作れば難易度の調整が出来るのでしょうか？ 空白場所を決定する『コツ』が有れば、お教えください。
- ベストアンサー
- 数学・算数
- 4×4数独の最少置数
先日数学セミナーの問題で、4×４の数独には最低でも４つの数字が分かってないとだめ、ということを証明する問題が出ていました。 複雑で証明が理解できなかったのですが、 a(11)a(12) b(11)b(12) a(21)a(22) b(21)b(22) c(11)c(12) d(11)d(12) c(21)c(22) d(21)d(22) と、各マスに未知数を振って、（各マスは1,2,3,4のみ） として、 a(11)+a(12)+a(21)+a(22)=1+2+3+4=10 b(11)+b(12)+b(21)+b(22)=10 c(11)+c(12)+c(21)+c(22)=10 d(11)+d(12)+d(21)+d(22)=10 a(11)+a(12)+b(11)+b(12)=10 a(21)a+(22)+b(21)+b(22)=10 c(11)+c(12)+d(11)+d(12)=10 c(21)+c(22)+d(21)+d(22)=10 a(11)+a(21)+c(11)+c(21)=10 a(12)+a(22)+c(12)+c(22)=10 b(11)+b(21)+d(11)+d(21)=10 b(12)+b(22)+d(12)+d(22)=10 「求める未知数が16個にたいして12個しか式がないから、少なくとも4個既知でなければならない」 は解答になっていないででょうか。
- ベストアンサー
- 数学・算数
- 数独のＪａｖａプログラム
数独の解答を一発で出すプログラムを考えています。 自分が考えたプログラムは下記の通りです。 import java.util.Random; public class NumberPlace { public static void main(String[] args) { int i, j, k, l, check=0, count=0, tmp; int a[][] = new int [9][9]; Random rnd = new Random(); int ran; for ( i=0; i<9; i++ ) for ( j=0; j<9; j++) a[i][j] = 0; count = 0; for ( i=0; i<9; i++ ) { for ( j=0; j<9; j++) { ran = rnd.nextInt(9); tmp = ran + 1; check = 0; for ( k=0; k<j; k++ ) if ( a[i][k] == tmp ) check = 1; for ( k=0; k<i; k++ ) if ( a[k][j] == tmp ) check = 1; for ( k=(i/3)*3; k<(i/3)*3+3; k++ ) for ( l=(j/3)*3; l<(j/3)*3+3; l++ ) if ( a[k][l] == tmp ) check = 1; if ( check == 0 ) a[i][j] = tmp; if ( check == 1 ) j--; if ( count > 50000 ) break; count++; } count = 0; } for ( i=0; i<9; i++) { for ( j=0; j<9; j++ ) { if ( a[i][j] < 10 ) { System.out.print(" "); } System.out.print(a[i][j]); } System.out.print("\n"); } } } これを実行すると、正しい数独の解が出来るまでに実行を２０～３０回。多い時は２００回前後実行しないと出来ません。 実行結果（０は数独のルール上数字が入らない所） 9 3 6 5 4 1 7 8 2 1 7 4 2 9 6 5 3 0 5 2 8 7 3 0 0 0 0 2 1 5 3 7 8 4 6 9 8 6 3 4 1 9 2 7 5 4 9 7 6 5 2 1 0 0 7 5 1 8 6 4 9 2 3 3 8 2 9 0 0 0 0 0 6 4 9 1 2 5 8 0 0 これを一発で０がない状態にしたいのです。 因みにＣ言語だと下記のプログラムで一発で出るのですが。（前回質問したプログラム） int main(void) { int i,j,k,l,chk=0,num=0,tmp,count=0; int a[9][9]; srand((unsigned) time(NULL)); start: count=0; for(i = 0; i < 9; i++) for(j = 0; j < 9; j++) a[i][j]=0; for(tmp=1;tmp<10;tmp++){ num=0; while(num<9){ i = rand() % 9; j = rand() % 9; chk=0; for(k=0;k<9;k++) if(a[i][k]==tmp)chk=1; for(k=0;k<9;k++) if(a[k][j]==tmp)chk=1; for(k=(i/3)*3;k<(i/3)*3+3;k++){ for(l=(j/3)*3;l<(j/3)*3+3;l++){ if(a[k][l]==tmp)chk=1; } } if((chk==0)&&(a[i][j]==0)){ a[i][j]=tmp; num++; } if(count%100==99){ count++; for(i = 0; i < 9; i++) for(j = 0; j < 9; j++) if(a[i][j]==tmp)a[i][j]=0; num=0; } if(count>10000) goto start; count++; } } for(i = 0; i < 9; i++){ for(j = 0; j < 9; j++){ printf("%d ",a[i][j]); } printf("\n"); } return 0; } このプログラムを実行すると一発で解答が出ます。 上のＪａｖａプログラムを下のプログラムのようにするにはどうしたら良いでしょうか。
- ベストアンサー
- Java
お礼
これだとやはり限界がないですか？ 自分的にはやはり総当りは不可欠だと思っているのですが。 現段階で私の作ったのが理詰め（だけ）でやってくれるやつです。 例えば 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ファイルにして)再度同じプログラムに 解かせたところなんと一歩前進していました。 そこで何かおかしいところがあると思いテストをしていくと 必須であると思っていた関数の一つを/*.....*/でくくっても 出力に変わりなかったのです。つまりそれがおかしいということです。 もしかしたら＋αでうまくいけるかもしれません。 とりあえず今までの自分にとんちんかんなミスがあったことをお詫びいたします。 申し訳ありませんでした。 ただ今回でバックトラックなどについて少し詳しくなったので無駄ではないと思っています。 *****************************************