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
相似问题