leetcode 37问题

Question

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] = '.';
            
        }    
    }
}

Answer 1

liuyubobobo 2022-04-23 03:50:59

我没有看你的代码的具体逻辑，但是你当前的代码肯定有问题的地方在于，对于已经找到的解，在回溯的过程中，会不断把解抹掉（你的 62 行做的事情）。

我的代码中：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0037-Sudoku-Solver/java-0037/src/Solution.java 47 行做的事情，就是在有解的时候返回， 而不去执行下面的 board[x][y] = '.';

继续加油！：）

• 提问者 讲武德的年轻人 #1

  谢谢老师! 不好意思，刚刚看到您的回复。我没有收到慕课的自动提醒

Answer 2

liuyubobobo 2022-04-23 03:23:37

测试一下是否可以回答问题。

Answer 3

liuyubobobo 2022-04-23 03:23:22

我没有看你的代码的具体逻辑，但是你当前的代码肯定有问题的地方在于，对于已经找到的解，在回溯的过程中，会不断把解抹掉（你的 62 行做的事情）。

我的代码中：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0037-Sudoku-Solver/java-0037/src/Solution.java 47 行做的事情，就是在有解的时候返回， 而不去执行下面的 board[x][y] = '.';

继续加油！：）