-1
我正在研究一個生成數獨謎題的程序。我試圖使用回溯算法來做到這一點，但我的程序無法正常工作。該程序運行無限，永遠不會返回解決方案。我不知道它只是一個小問題，或者我誤解了如何編寫回溯算法。我的回溯算法有什麼問題？
package sudoku;
import java.util.Random;
public class Puzzle {
// 9x9 puzzle
private int puzzle[][] = new int[9][9];
// generate a completely solved sudoku board
public int[][] generate() {
Random gen = new Random();
// add each number to the board square by square
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x++) {
// generate random number 1-9
int num = gen.nextInt(9) + 1;
int count = 0;
boolean valid = false;
while (valid == false) {
// check if number is valid
if (checkRow(num, x) && checkCol(num, y)
&& checkSection(num, x, y)) {
// add number to the board
puzzle[x][y] = num;
// exit loop, move on to next square
valid = true;
} else {
// try next number
if (num == 9) {
num = 1;
} else {
num++;
}
// increase counter.
count++;
// if counter reached 9, then all numbers were tried and
// none were valid, begin backtracking
if (count == 9) {
// go back 1 square
if (x == 0) {
x = 8;
y--;
} else {
x--;
}
// empty square
puzzle[x][y] = 0;
//reset count
count = 0;
}
}
}
}
}
return puzzle;
}
// check each element of the row for num, if num is found return false
private boolean checkRow(int num, int row) {
for (int i = 0; i < 9; i++) {
if (puzzle[row][i] == num) {
return false;
}
}
return true;
}
// check each element of the column for num, if num is found return false
private boolean checkCol(int num, int col) {
for (int i = 0; i < 9; i++) {
if (puzzle[i][col] == num) {
return false;
}
}
return true;
}
// check each element of the section for num, if num is found return false
private boolean checkSection(int num, int xPos, int yPos) {
int[][] section = new int[3][3];
section = getSection(xPos, yPos);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (section[i][j] == num)
return false;
}
}
return true;
}
// return the 3x3 section the given coordinates are in
private int[][] getSection(int xPos, int yPos) {
int[][] section = new int[3][3];
int xIndex = 3 * (xPos/3);
int yIndex = 3 * (yPos/3);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
section[i][j] = puzzle[xIndex + i][yIndex + j];
}
}
return section;
}
}
你用什麼來編寫你的程序？您是使用文本編輯器還是NetBeans或Eclipse等IDE？如果以後，你應該學習如何使用調試器。這對任何程序員來說都是一個重要的工具。 –
我從來沒有做過回溯無w/o遞歸;現在我想我知道爲什麼。通過程序執行開始跟蹤。從較小的電路板開始。 –
不要在循環中更改'for'的索引，這是妨礙編譯器優化代碼的錯誤做法。 – SJuan76