Bloccato nel risolutore di backtracking di Sudoku (Java)
Ho cercato di capire il mio errore nel risolutore di backtracking di Sudoku per tre giorni. Il problema è da leetcode Sudoku Solver .
Il mio risolutore si basa sulla deduzione nell'immagine allegata. Il problema è che la mia scheda viene modificata anche se un percorso dalla radice alla foglia non è valido.
In altre parole, dopo aver attraversato un percorso non valido, i valori tentati sono corretti nella mia scheda originale. Tuttavia, aggiorno solo la mia scheda originale quando i suoi figli restituisce true (vedere la parte nel metodo helper: // mettere un numero e generare figli).
Fondamentalmente, per ogni '.', Io generare tutte le possibilità da 1 a 9, costruire una scheda di temperatura che riempie la corrente'.'con una possibilità, poi chiamare helper del prossimo'.'con temp bordo. So che non è bene memorizzare una stessa dimensione boardTemp per ogni possibile bambino a causa del costo dello spazio, ma la mia preoccupazione principale ora è risolvere il problema prima di ottimizzare il costo.
Tutto sommato, perché la mia tavola cambia anche se tutti i bambini non sono validi?
Ad esempio, basarsi sulla scheda iniziale
..9748...; 7........; .2.1.9...;
..7...24.; .64.1.59.; .98...3..;
...8.3.2.; ........6; ...2759..;
Ho ottenuto il risultato finale dopo aver eseguito:
139748652; 745326189; 826159437;
35769.24.; .64.1.59.; .98...3..;
...8.3.2.; ........6; ...2759..;
public void sudokuSolver(char[][] board) {
for (int i = 0 ; i < board.length ; i++) {
for (int j = 0 ; j < board.length ; j++) {
if (board[i][j] == '.') {
// find the first '.' as root
helper(i, j, board);
return;
}
}
}
}
private boolean helper(int row, int col, char[][] board) {
// case 2. check if it has following '.' and store its position
boolean hasNext = false;
boolean nextSearching = false;
int nextRow = row;
int nextCol = col;
for (int i = 0 ; i < board.length ; i++) {
for (int j = 0; j < board.length ; j++) {
if (nextSearching && !hasNext && board[i][j] == '.') {
hasNext = true; // there is next!
nextRow = i;
nextCol = j;
}
if (i == row && j == col) {
nextSearching = true;
}
}
}
// exit condition: last '.'
if (!hasNext) {
for (char put = '1' ; put <= '9' ; put ++) {
if (isValid(row, col, board, put)) {
return true;
}
}
return false;
}
// put a number and generate children
for (char put = '1' ; put <= '9' ; put ++) {
if (isValid(row, col, board, put)) {
char[][] boardTemp = board;
boardTemp[row][col] = put;
boolean valid = helper(nextRow, nextCol, boardTemp);
if (valid) {
// board is supposed to change only when valid is true.
board[row][col] = put;
return true;
}
}
}
return false;
}
private boolean isValid(int row, int col, char[][] board, char c) {
// go through each row, column, and subblock to determine if c is a valid choice based on current board.
for (int jCol = 0 ; jCol < 9 ; jCol ++) {
if (board[row][jCol] == c) {
return false;
}
}
for (int iRow = 0 ; iRow < 9 ; iRow ++) {
if (board[iRow][col] == c) {
return false;
}
}
for (int i = row/3*3 ; i < row/3*3 + 3 ; i++) {
for (int j = col/3*3 ; j < col/3*3 + 3 ; j++) {
if (board[i][j] == c) {
return false;
}
}
}
return true;
}
1 answers
Non c'è differenza tra l'uso di boardTemp
e board
. char[][] boardTemp = board
significa che puntano alla stessa memoria... Quello che ti sei perso nel tuo codice originale è la parte else
dopo aver inserito un numero non valido:
for (char put = '1' ; put <= '9' ; put ++) {
if (isValid(row, col, board, put)) {
char[][] boardTemp = board; // board and boardTemp are essentially the same thing
boardTemp[row][col] = put;
boolean valid = helper(nextRow, nextCol, boardTemp);
if (valid) {
// board is supposed to change only when valid is true.
board[row][col] = put;
return true;
}
// THIS IS WHAT YOU MISSED!!
// if you don't reset the '.' back, your later backtrack will not work
// because you put an invalid number on your board and you will never find a solution
boardTemp[row][col] = '.';
}
}