leetcode 37问题
来源:8-8 回溯法是经典人工智能的基础 N Queens
讲武德的年轻人
2022-04-23
bobo老师,我借鉴您在github的思路,修改了我的代码,唯一的区别就是dfs函数没有返回值,我debug了很久,还是没有发现问题所在。能否请问简单看下,问题可能出在哪里?我继续debug..谢谢!
class Solution {
private boolean[][] row;
private boolean[][] col;
private boolean[][] block;
private char[][] board;
public void solveSudoku(char[][] board) {
this.board = board;
row = new boolean[9][10];
col = new boolean[9][10];
block = new boolean[9][10];
for (int i = 0; i < 9; i ++) {
for (int j = 0; j < 9; j ++) {
if (board[i][j] != '.'){
int num = board[i][j] - '0';
row[i][num] = true;
col[j][num] = true;
block[3 * (i / 3) + j / 3][num] = true;
}
}
}
for (int k = 0; k < 81; k ++) {
if (board[k / 9][k % 9] == '.'){
dfs(k);
}
}
}
private void dfs(int k) {
if (k == 81) {
return;
}
int next = k + 1;
for(; next < 81; next ++)
if(board[next / 9][next % 9] == '.')
break;
int x = k / 9, y = k % 9;
for (int i = 1; i <= 9; i ++) {
if (row[x][i] || col[y][i] || block[3 * (x / 3) + y / 3][i])
continue;
row[x][i] = true;
col[y][i] = true;
block[3 * (x / 3) + y / 3][i] = true;
board[x][y] = (char) (i + '0');
dfs(next);
row[x][i] = false;
col[y][i] = false;
block[3 * (x / 3) + y / 3][i] = false;
board[x][y] = '.';
}
}
}写回答
3回答
-
我没有看你的代码的具体逻辑,但是你当前的代码肯定有问题的地方在于,对于已经找到的解,在回溯的过程中,会不断把解抹掉(你的 62 行做的事情)。
我的代码中:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0037-Sudoku-Solver/java-0037/src/Solution.java 47 行做的事情,就是在有解的时候返回, 而不去执行下面的 board[x][y] = '.';
继续加油!:)
012022-05-11 -
liuyubobobo
2022-04-23
测试一下是否可以回答问题。
00 -
liuyubobobo
2022-04-23
我没有看你的代码的具体逻辑,但是你当前的代码肯定有问题的地方在于,对于已经找到的解,在回溯的过程中,会不断把解抹掉(你的 62 行做的事情)。
我的代码中:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0037-Sudoku-Solver/java-0037/src/Solution.java 47 行做的事情,就是在有解的时候返回, 而不去执行下面的
board[x][y] ='.';继续加油!:)
00
相似问题
leetcode 337号问题
回答 2
个人刷题疑问
回答 1