数独回溯算法中的递归(Java)
三天来,我一直在努力找出我在数独回溯求解中的错误。问题来自leetcode Sudoku Solver
我的解算器基于附件中的推论。问题是,即使从根到叶的路径无效,我的电路板也会被更改
换句话说,在它通过一条无效路径后,它尝试的值在我的原始电路板中被固定。但是,我只在其子项返回true时更新原始板(请参阅helper method://put a number and generate children中的部分)
基本上,对于每个“.”,我生成从1到9的所有可能性,构造一个临时板,填充当前的“.”如果有一种可能性,请致电下一个的助手用临时板。我知道,由于空间成本的原因,为每个可能的孩子存储相同大小的boardTemp是不好的,但我现在主要关心的是在优化成本之前先解决问题
总而言之,为什么我的董事会在所有孩子都无效的情况下仍在变动
例如,基于初始板
。。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;
}
# 1 楼答案
使用
boardTemp
和board
之间没有区别char[][] boardTemp = board
意味着它们指向同一个内存。。。您在原始代码中漏掉的是输入无效数字后的else
部分: