質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

1回答

892閲覧

数独を解くプログラムを作っています。バックトラックで詰まってしまいます。

sechi

総合スコア4

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2018/08/03 03:32

javaで数独をバックトラックでとくプログラムを作ろうとしています。

ここに質問の内容を詳しく書いてください。
(例)javaで数独を解くプログラムを作っています。
バックトラックを再帰で作っていると、解いている途中で止まってしまいます
プログラミング初心者です。とても困っているので教えていただければ幸いです。

発生している問題・エラーメッセージ

少し解いただけで停止してしまう。一列二列で解くのをやめてしまう。

該当のソースコード

java

1private boolean bruteForceSolve(int row, int col) { 2 //全てのセルへの入力が終了している場合にメソッドを閉じていく 3 if (row == 9) 4 return true; 5 6 7 // 注目したセルへ既に数字が入力されている場合に処理を次のセルへ移動する 8 if (!(checkEmptyCell(row,col))) { // 9 if (bruteForceSolve(col == 8 ? (row + 1): row, (col + 1)%9)) 10 return true; 11 } else { 12 Integer[] randoms = generateRandomNumbers(); 13 for (int i = 1; i <= 9; i++) { 14 // 行、列、3x3ボックス内に数字が重複しない場合に値を代入し、次のセルへ進む 15 if (!isContainedInRowColumn(row, col,randoms[i]) && 16 !isContainedIn3x3Box(row, col,randoms[i])) { 17 setCellValues(row, col,randoms[i]); 18 19 //次のマス(左から右へ、上から下へという順)に進む 20 if (cellValues[row][col] != 0) { 21 if ( bruteForceSolve(col == 8 ? (row + 1): row, (col + 1) % 9)) 22 return true; 23 } 24 //再帰 25 bruteForceSolve(row,col); 26 setCellValues(row,col,0); 27 } 28 } 29 } 30 return false; 31 }

試したこと

いろいろ調べたり、再帰について考えたりしましたが、初心者なのでなぜ問題が出るのかわからなかったです。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

torisan

2018/08/03 03:48

止まってしまうとは処理が終了していまうという意味ですか?それとも無限ループなどで固まってしまうという意味ですか?
sechi

2018/08/03 03:49

処理が終了するという意味です。
sechi

2018/08/03 03:49

言葉足らずですみません。
guest

回答1

0

コード,拝見いたしました.
間違えておられる部分はたったの2点です.
以下,修正版を回答いたします.

Java

1 private boolean bruteForceSolve(int row, int col) { 2 //全てのセルへの入力が終了している場合にメソッドを閉じていく 3 if (row == 9) 4 return true; 5 6 7 // 注目したセルへ既に数字が入力されている場合に処理を次のセルへ移動する 8 if (!(checkEmptyCell(row,col))) { // 9 if (bruteForceSolve(col == 8 ? (row + 1): row, (col + 1)%9)) 10 return true; 11 } else { 12 //Integer[] randoms = generateRandomNumbers(); // 1.そもそも再帰に乱数は無用 13 for (int i = 1; i <= 9; i++) { 14 // 行、列、3x3ボックス内に数字が重複しない場合に値を代入し、次のセルへ進む 15 if (!isContainedInRowColumn(row, col, i/*randoms[i]*/) && 16 !isContainedIn3x3Box(row, col, i/*randoms[i]*/)) { 17 setCellValues(row, col, i/*randoms[i]*/); 18 19 //次のマス(左から右へ、上から下へという順)に進む 20 if (cellValues [row][col] != 0) { 21 if ( bruteForceSolve(col == 8 ? (row + 1): row, (col + 1) % 9)) 22 return true; 23 } 24 //再帰 25 //bruteForceSolve(row,col); // 2.延々と同じマスを探索し続ける無意味な再起 26 setCellValues(row,col,0); 27 } 28 } 29 } 30 return false; 31 }

解説いたします.
0. そもそも再帰に乱数は無用(一般的に意味がない & 今回の場合はバグ)
再帰とは,いわば「コンピュータのチカラによってすべてのパターンを試す」という行為です.なので,for 文を回し,1~9までの数字全て試す必要があります.おそらく,
generateRandomNumbers();
という関数は,0~9までの値がランダムな順番で格納されている大きさ10の配列が帰ってくるものだと思います.そして今回の場合,
randoms[0];
この値を使っていませんね.この値がもし正解だったら...?あとは想像がつきますね(^^

  1. 延々と同じマスを探索し続ける無意味な再起

これ,終わりません.いつまでも,

Java

1if (row == 9) 2 return true;

この条件式に当てはまらないので.これは,スタックオーバーフローというエラーにつながる大きなミスです.再帰関数を使用する上ではもっとも注意すべき点といえるでしょう.

以上,もっとコードを短く読みやすくすることもできますが,今回はこれだけにとどめておきます.

投稿2018/08/04 04:06

編集2018/08/04 04:09
chankane

総合スコア139

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問