-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를 사용하고 있습니까? 나중에 디버거를 사용하는 방법을 배워야합니다. 이것은 모든 프로그래머에게 필수적인 도구입니다. –
이전에 재귀가없는 역 추적을 한 번도 해보지 않았습니다. 지금 내가 왜 그런지 알 것 같아. 프로그램 실행을 통해 추적을 시작하십시오. 작은 보드부터 시작하십시오. –
루프의 중간에서'for'의 인덱스를 변경하지 마십시오. 이것은 컴파일러가 코드를 최적화하지 못하게하는 나쁜 습관입니다. – SJuan76