当前位置：首页 > ops >正文

LeetCode 37.解数独

ops 2025/9/1 11:53:12

在这里插入图片描述

对于这题，首先考虑数独的解的条件是什么：每行、每列、每个九宫格中没有重复的数字。
那么在对每个空格进行填数时如何考虑其有效性？检查其所在行列及九宫格。
那么我们可以利用回溯，遍历所有空格，在其中填入可能的数字并检查有效性，递归调用解决下一个空格，如果后续路径失败，就将格子恢复原状。
代码如下：

class Solution {
public:bool isvalid(int r, int c, char k, const vector<vector<char>>& board){for(int i = 0;i<board[0].size();i++){if(board[r][i] == k) return false;}for(int i = 0;i<board.size();i++){if(board[i][c] == k) return false;}int ro = r/3, co = c/3;for(int i = ro*3;i<(ro+1)*3;i++){for(int j = co*3;j<(co+1)*3;j++){if(board[i][j] == k) return false;}}return true;}bool check(vector<vector<char>>& board){for(int i = 0;i<board.size();i++){for(int j = 0;j<board[0].size();j++){if(board[i][j] != '.') continue;for(char k = '1';k<='9';k++){if(isvalid(i, j, k, board)){board[i][j] = k;if(check(board)) return true;board[i][j] = '.';}}return false;}}return true;}void solveSudoku(vector<vector<char>>& board) {check(board);}
};