Valid Sudoku & Sudoku Solver

Medium & Hard

嵌套9格 检查

Valid Sudoku

Check Subbox Index

S1

依次检查每一行、每一列以及每一个九宫格的数字元素是否在1-9之间，并且是否没有重复。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        if(board.size()!=9 || board[0].size()!=9) return false;

        // check row
        for(int i=0; i<9; i++) {
            vector<bool> used(9,false);
            for(int j=0; j<9; j++) {
                if(!isdigit(board[i][j])) continue; 
                int k = board[i][j]-'0';
                if(k==0 || used[k-1]) return false;
                used[k-1] = true;
            }
        }

        //check col
        for(int j=0; j<9; j++) {
            vector<bool> used(9,false);
            for(int i=0; i<9; i++) {
                if(!isdigit(board[i][j])) continue;
                int k = board[i][j]-'0';
                if(k==0 || used[k-1]) return false;
                used[k-1] = true;
            }
        }

        // check subbox
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                int row = 3*i;
                int col = 3*j;
                vector<bool> used(9,false);
                for(int m=row; m<row+3; m++) {
                    for(int n=col; n<col+3; n++) {
                        if(!isdigit(board[m][n])) continue;
                        int k = board[m][n]-'0';
                        if(k==0 || used[k-1]) return false;
                        used[k-1]=true;
                    }
                }
            }
        }

        return true;
    }
};

Ref: https://www.youtube.com/watch?v=4-SF0-p98NM&t=288s

Sudoku Solver

和N-Queen思路基本一样。对每个需要填充的位置枚举1-9，对每个枚举判断是否符合所在行、列、九宫格。如果符合则进行下一层递归。终止条件为填写完了整个棋盘。

这道求解数独的题是在之前那道 Valid Sudoku 验证数独 的基础上的延伸，之前那道题让我们验证给定的数组是否为数独数组，这道让我们求解数独数组，跟此题类似的有 Permutations 全排列，Combinations 组合项 ，N-Queens N皇后问题等等，其中尤其是跟 N-Queens N皇后问题的解题思路及其相似.

对于每个需要填数字的格子带入1到9，每代入一个数字都判定其是否合法，如果合法就继续下一次递归，结束时把数字设回'.'，判断新加入的数字是否合法时，只需要判定当前数字是否合法，不需要判定这个数组是否为数独数组，因为之前加进的数字都是合法的，这样可以使程序更加高效一些，具体实现如代码所示：

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        if (board.empty() || board.size() != 9 || board[0].size() != 9) return;
        solveSudokuDFS(board, 0, 0);
    }
    bool solveSudokuDFS(vector<vector<char> > &board, int i, int j) {
        if (i == 9) return true;
        if (j >= 9) return solveSudokuDFS(board, i + 1, 0);
        if (board[i][j] == '.') {
            for (int k = 1; k <= 9; ++k) {
                board[i][j] = (char)(k + '0');
                if (isValid(board, i , j)) {
                    if (solveSudokuDFS(board, i, j + 1)) return true;
                }
                board[i][j] = '.';
            }
        } else {
            return solveSudokuDFS(board, i, j + 1);
        }
        return false;
    }
    bool isValid(vector<vector<char> > &board, int i, int j) {
        for (int col = 0; col < 9; ++col) {
            if (col != j && board[i][j] == board[i][col]) return false;
        }
        for (int row = 0; row < 9; ++row) {
            if (row != i && board[i][j] == board[row][j]) return false;
        }
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; ++row) {
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; ++col) {
                if ((row != i || col != j) && board[i][j] == board[row][col]) return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        if(board.size()<9 || board[0].size()<9) return;
        bool findSol = solSudoku(board, 0, 0);
    }

    bool solSudoku(vector<vector<char>> &board, int irow, int icol) {
        if(irow==9) return true;

        int irow2, icol2;
        if(icol==8) {
            irow2 = irow+1;
            icol2 = 0;
        }
        else {
            irow2 = irow;
            icol2 = icol+1;
        }

        if(board[irow][icol]!='.') {
            if(!isValid(board, irow, icol)) return false;
            return solSudoku(board, irow2, icol2);
        }

        for(int i=1; i<=9; i++) {
            board[irow][icol] = '0'+i;
            if(isValid(board, irow, icol) && solSudoku(board, irow2, icol2)) return true;
        }

        // reset grid 
        board[irow][icol] = '.';
        return false;
    }

    bool isValid(vector<vector<char>> &board, int irow, int icol) {
        char val = board[irow][icol];
        if(val-'0'<1 || val-'0'>9) return false;

        // check row & col
        for(int i=0; i<9; i++) {
            if(board[irow][i]==val && i!=icol) return false;
            if(board[i][icol]==val && i!=irow) return false;
        }

        //check 3x3 box
        int irow0 = irow/3*3;
        int icol0 = icol/3*3;
        for(int i=irow0; i<irow0+3; i++) {
            for(int j=icol0; j<icol0+3; j++) {
                if(board[i][j]==val && (i!=irow || j!=icol)) return false;
            }
        }

        return true;
    }
};