🤯37 solve sudoku

https://leetcode.com/problems/sudoku-solver/

做这道题属实有点自残，答案摘自评论区，我的思路时对的，但是这个in place修改很难写对的感觉，因为backtrack不能固定结果

大概要注意的就是

1. 在注意遍历的cell不重复的前提下不需要visited，比如这里就是先遍历行，到最右边再去下一行，这样返回条件也很简单了，走到最最底下了就表示找到解了

2. board如果不safe还是要重置成 '.'，主要是这里isSafe的写法决定了上一次尝试的结果会影响下次的判读

3. 不需要单独的rows，cols和blocks来记录数值，用board足矣，不然的参数长度以光年计算

class Solution {
    public boolean helper(char[][] board, int row, int col){
        if(row == board.length){
            return true;
        }
        int nrow = 0;
        int ncol = 0;
        if(col != board.length -1) {
            nrow = row;
            ncol = col+1;
        }else{
            nrow = row+1;
            ncol = 0;
        }

        if(board[row][col] != '.'){
            if(helper(board, nrow, ncol)){
                return true;
            }
        }else{
            for(int i=1; i<=9; i++){
                if(isSafe(board, row, col, i)){
                    board[row][col] = (char)(i + '0');
                    if(helper(board, nrow, ncol)){
                        return true;
                    }else{
                        board[row][col] = '.';
                    }
                }
            }
        }
        return false;

    }
    public boolean isSafe(char[][] board, int row, int col, int number){
        for(int i=0; i<board.length; i++){
            if(board[i][col] == (char)(number + '0')){
                return false;
            }
            if(board[row][i] == (char)(number +'0')){
                return false;
            }
        }
        //grid
        int sr = (row/3) *3;
        int sc = (col/3) *3;
        for(int i = sr; i<sr+3; i++){
            for(int j=sc; j< sc+3; j++){
                if(board[i][j] == (char)(number + '0')){
                    return false;
                }
            }
        }
        return true;
    }
    public void solveSudoku(char[][] board) {
        helper(board, 0, 0);
        
    }
}

下面是我自己写的版本: 好吧其实也不是很难，关键点是遍历的顺序

class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board, 0, 0);
    }
    private boolean dfs(char[][] board, int i, int j) {
        if (i == 9) return true;
        int x, y;
        if (j != 8) {
            x = i;
            y = j + 1;
        } else {
            x = i + 1;
            y = 0;
        }
        
        if (board[i][j] != '.') {
            if (dfs(board, x, y)) return true;
            return false;
        }
        for (char num = '1'; num <= '9'; num++) {
            if (isValid(board, i, j, num)) {
                board[i][j] = num;
                if (dfs(board, x, y)) {
                    return true;
                } else {
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }
    private boolean isValid(char[][] board, int i, int j, char num) {
        for (int col = 0; col < 9; col++) {
            if (board[i][col] == num) return false;
        }
        for (int row = 0; row < 9; row++) {
            if (board[row][j] == num) return false;
        }
        int rs = i / 3 * 3;
        int cs = j / 3 * 3;
        for (int row = rs; row < rs + 3; row++) {
            for (int col = cs; col < cs + 3; col++) {
                if (board[row][col] == num) return false;
            }
        }
        return true;
    }
}