我一直在尝试找出Sudoku回溯求解器中的错误三天。问题出在leetcode Sudoku Solver上。
我的求解器基于所附图片中的推导。问题是即使从根到叶的路径无效，我的电路板也要更换。
换句话说，经过无效路径后，尝试的值在我的原始板上固定。但是，我只会在其原始子板返回true时更新原始板(请参阅helper方法中的部分://放入数字并生成子板)。
基本上，对于每个“。”，我生成从1到9的所有可能性，构造一个临时模板以填充当前的“。”。一种可能性，然后调用下一个“的”助手。与临时委员会。我知道，由于空间成本，为每个可能的 child 存储相同大小的boardTemp不好，但是我现在主要关心的是在优化成本之前先解决问题。
总而言之，即使所有 child 都无效，为什么我的董事会也要更换？
例如，基于初始板
..9748 ...; 7 ........; .2.1.9 ...;
..7 ... 24 .; .64.1.59 .; .98 ... 3 ..;
... 8.3.2 .; ........ 6; ... 2759 ..;
运行后，我得到了最终结果:
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;
}
最佳答案
使用boardTemp和board没有什么区别。 char[][] boardTemp = board表示它们指向相同的内存...您在原始代码中缺少的是在您输入了无效数字之后输入的else部分:
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] = '.';
}
}