- ベストアンサー
数独をとくプログラム
BLUEPIXYの回答
- BLUEPIXY
- ベストアンサー率50% (3003/5914)
#1>全部で3*3*2=18通りの組み合わせがありますが、それらを全て試させるには 例えば、 Ａマスで２通り、Ｂマスで３通りある場合、 Ａの状態で（仮に）１つ決定して問題を解かせると、 ・問題が解けた ・問題が解けずに行き詰まった という状態になります。 問題を解く手順として、問題が解けずに行き詰まった場合の手順として、決定していないマスの手を１つ選んで仮に進めるという手法を組み込み済みなので、Ａが埋まった状態でＢのマスの状態を調べる状態になります。 そのように再帰的に手順が呼び出されて（メモリがオーバーフローしないで正解があるなら）いつか結果が求まります。 その場合、 最初のＡマスの１つの探索が終わったとき次の（残りの）１つの手を調べるようになっていれば、 結果的に、全ての組み合わせを調べることになります。（樹形図を描いたような感じで、プログラムが再帰的に木を深さ優先でたどる）
関連する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
お礼
再帰を使えば確かにうまくできそうです。。。が正直いまいち再帰がわかっていない私。。。 でも特に不確定マスの個数が状況による、となると再帰を頼らずにはいられなさそうです。 もしくはwhile(1)で永遠ループを作って、あるifの元でbreakさせるか。。。 http://www.pro.or.jp/~fuji/puzzlestudy/sudoku.html のサイトのbakadoku.cというファイルだと再帰を使ってシンプルに 実現しているようなのですが正直ソースを見てもよく仕組みがわかっていません。。。 ご解答ありがとうございました。