37. 解数独

Problem: 37. 解数独

思路

递归回溯

解题过程

1. 找到空格子（用 '.' 表示）。
2. 尝试填入 1–9，每次填之前要检查是否合法：

• 同一行没有重复；
• 同一列没有重复；
• 当前 3×3 宫格没有重复。

3. 如果合法，就递归继续填下一个格子。
4. 如果递归能走到最后（数独解完），就返回 true；
5. 如果不行，就回溯，把格子恢复成 '.'，再尝试下一个数字。

复杂度

• 时间复杂度: $O(9^n)$，n为数独中空格的个数。
• 空间复杂度: 等价于，$O(1)$

Code

class Solution {
public:void solveSudoku(vector<vector<char>>& board) { dfs(board); }bool dfs(vector<vector<char>>& board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] != '.') {continue;}for (int c = '1'; c <= '9'; c++) {if (isValid(board, i, j, c)) {board[i][j] = c;if (dfs(board)) {return true;}board[i][j] = '.';}}return false;}}return true;}bool isValid(vector<vector<char>>& board, int row, int col, char c) {for (int i = 0; i < 9; i++) {if (board[row][i] == c) {return false;}if (board[i][col] == c) {return false;}int r = (row / 3) * 3 + i / 3;int l = (col / 3) * 3 + i % 3;if (board[r][l] == c) {return false;}}return true;}
};