37. Sudoku Solver **

description:

数独

Note:

Example:

Example 1:Input: [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"] ] Output: trueExample 2:Input: [["8","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"] ] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

answer:

class Solution { public:void solveSudoku(vector<vector<char>>& board) {if (board.empty() || board.size() != 9 || board[0].size() != 9) return;solveDFS(board, 0, 0); //从阵列的左上角开始逐行逐列的递归填入检查}bool solveDFS(vector<vector<char>> &board, int i, int j) {if (i == 9) return true; // 如果行号到了9， 就证明已经全部遍历完毕if (j >= 9) return solveDFS(board, i + 1, 0); // 如果列号大于等于9了，就证明这一行已经ok了，可以进行下一行的递归了。if (board[i][j] == '.') { // 如果是需要填入的空，那就从1到9挨个试，看看哪个填入是合法的for (int k = 1; k <= 9; k++){board[i][j] = (char)(k + '0');if (isValid(board, i, j)) { // 如果是合法的，就继续递归，跳出递归之后就结束了也，这里必须要写return ，这样才能跳出循环，同时满足函数返回值类型if (solveDFS(board, i, j + 1)) return true;}board[i][j] = '.'; // 这个是只有九个数都试过了但是都不行，就恢复原状，然后就跳到最后那个 return false 上去了，这样它前面一列那个数就相当于要换个k重新试试，这样不断往前改，总是能保证当前数之前填过的数都是正确的。}} else {return solveDFS(board, i, j + 1); // 如果不是需要去填的空，就跳过现在这个数继续递归，这里一定要写return}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;} };

relative point get√：

hint :

转载于:https://www.cnblogs.com/forPrometheus-jun/p/11123306.html

总结

以上是生活随笔为你收集整理的37. Sudoku Solver **的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。