Day 18。
今天两道题分别是 Valid Sudoku 和 Sudoku Solver。
这两题是一组非常经典的“前后呼应题”：

  • 36 是判断一个数独盘面是否合法
  • 37 是在合法基础上把整个数独解出来

所以今天的核心不只是做两题，而是在练一整套思路：

状态记录 + 约束检查 + 回溯搜索

今天的关键词：数独、行列宫、状态表、剪枝、回溯。

🧠 LeetCode 36 – Valid Sudoku

💡 思路总结

这题要求判断一个 9×9 的数独盘面是否合法。
规则很明确：

  • 每一行不能重复
  • 每一列不能重复
  • 每一个 3×3 小宫格不能重复

你的做法非常标准，直接开了三个二维数组：

  • row[9][9]
  • col[9][9]
  • box[9][9]

分别记录某个数字是否已经在某一行、某一列、某个宫格里出现过。

这题的关键其实就在于：

把“数独规则”转成可以 O(1) 检查的状态表

💻 代码实现

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][9] = {0};
        int col[9][9] = {0};
        int box[9][9] = {0};
        for(int i = 0;i<9;i++){
            for (int j = 0 ; j<9 ;j++){
                if(board[i][j]=='.')continue;
                //数字的映射
                int num = board[i][j] - '1';
                int box_index = (i/3)*3 + j/3;
                if(row[i][num] || col[j][num] || box[box_index][num])return false;
                
                row[i][num]= col[j][num] = box[box_index][num]=1;
            }
        }
        return true;

    }
};

📌 知识点总结

1️⃣ 三张状态表很关键

你这里本质上是在做三类约束记录：

  • row[i][num]：第 i 行是否出现过数字 num
  • col[j][num]：第 j 列是否出现过数字 num
  • box[k][num]：第 k 个 3×3 宫格是否出现过数字 num

这样每读到一个数字时，都能立刻判断它是否合法。

2️⃣ 字符到数字下标的映射

这一句很经典：

int num = board[i][j] - '1';

因为字符 '1' ~ '9' 映射到数组下标正好就是 0 ~ 8。
这样状态表访问就会非常方便。

3️⃣ 宫格编号怎么求

这一句是这题最值得记住的小技巧之一：

int box_index = (i/3)*3 + j/3;

意思是：

  • i / 3 确定第几大行宫格
  • j / 3 确定第几大列宫格
  • 两者组合成 0 ~ 8 的宫格编号

这个公式以后做数独题时会一直用到。

4️⃣ 这题的本质是“约束检查”

这题不需要你去填数，也不需要搜索。
它本质就是：

当前给定的数，是否违反了任何行 / 列 / 宫规则

所以重点不在搜索，而在于能不能把规则表达清楚。

🔥 LeetCode 37 – Sudoku Solver

💡 思路总结

这题比上一题更进一步：
不只是判断是否合法，而是要把整个数独解出来。

这题的核心就是经典的：

回溯 + 剪枝

你的整体框架非常清晰：

  1. 先扫描整个棋盘，把已有数字填到 row / col / box 状态表里
  2. 然后递归寻找空格 '.'
  3. 对每个空格尝试填 1 ~ 9
  4. 如果某个数字当前合法，就填进去并更新状态表
  5. 递归做下一步
  6. 如果后面失败，就撤销这一步，继续尝试下一个数字

这就是非常标准的回溯搜索框架。

💻 代码实现

class Solution {
public:
    int row[9][9] = {0};
    int col[9][9] = {0};
    int box[9][9] = {0};
    void solveSudoku(vector<vector<char>>& board) {
        //第一步是要填上 row、col、box这三个表；
        for (int i = 0;i<9;i++){
            for(int j = 0 ;j<9;j++){
                if(board[i][j] == '.')continue;
                int num = board[i][j] - '1';
                int box_index = (i/3)*3 + j/3;
                row[i][num] = col[j][num] = box[box_index][num] = 1;
            }
        }
        dfs(board);
        return ;
    }

    bool dfs(vector<vector<char>>& board){
        for(int i = 0; i < 9;i++){
            for(int j = 0;j<9;j++){
                int box_index = (i/3)*3 + j/3;
                if(board[i][j] == '.'){
                    //尝试填入数字
                    for(int num = 1;num<10;num++){
                        if(!row[i][num-1]  && !col[j][num-1]  && !box[box_index][num-1] ){
                            board[i][j] = num + '0';
                            row[i][num-1] = col[j][num-1] = box[box_index][num-1] = 1;
                            if(dfs(board))return true;
                            row[i][num-1] = col[j][num-1] = box[box_index][num-1] = 0;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }

            }
        }
        return true;
    }
};

📌 知识点总结

1️⃣ 这是非常标准的回溯题

这题和前面的括号生成、组合题有相同的味道，但更复杂一点。
它的核心流程就是：

  • 找一个待决策的位置
  • 枚举所有可能选择
  • 尝试
  • 递归
  • 失败就撤销

也就是：

选择 → 递归 → 回退

2️⃣ 先建状态表非常重要

如果每次填数字都重新扫描整行、整列、整个宫格，那会很慢。
你这里先把已有数字全部记进状态表里，后面判断合法性就能直接做到 O(1)。

这说明你已经不是在“纯暴力搜索”了，而是在做：

搜索 + 状态优化

这很重要。

3️⃣ 为什么 dfs 返回 bool

你这里的 dfs 不是求所有解，而是：

找到一个可行解就立刻停止

所以返回 bool 很合理：

  • true：说明已经成功解出，整层递归一路返回
  • false：说明当前尝试失败，需要回溯

这种写法是求“是否存在解”的典型方式。

4️⃣ 回溯的标准四步

你在这题里其实完整地写出了回溯模板：

第一步：判断当前能不能选

if(!row[i][num-1] && !col[j][num-1] && !box[box_index][num-1])

第二步：做选择

board[i][j] = num + '0';
row[i][num-1] = col[j][num-1] = box[box_index][num-1] = 1;

第三步：递归

if(dfs(board)) return true;

第四步：撤销选择

row[i][num-1] = col[j][num-1] = box[box_index][num-1] = 0;
board[i][j] = '.';

这四步非常值得记住，因为几乎所有回溯题都绕不开这个结构。

5️⃣ 为什么找到空格后要立刻 return false

你这里写得很对：

  • 一旦找到一个空格，就只处理这个空格
  • 尝试 1 ~ 9
  • 如果都不行，直接返回 false

原因是：

当前这个位置都填不出来，后面的位置根本没必要继续看

这是很典型的深度优先搜索思路。

🧩 两题放在一起看

今天这两题其实是一条主线上的前后题：

题目核心区别
LeetCode 36只检查是否合法
LeetCode 37在合法检查基础上继续搜索求解

也就是说，37 的基础其实就是 36：

  • 先会判断一个数能不能放
  • 再把这个判断嵌入回溯搜索里

这就是很典型的“前一题是后一题基础”的题组。

🧠 今日收获

今天最值得记住的两个模型：

1. 约束记录模型

如果题目规则固定，而且会频繁检查“某个元素能不能放”，就要想到：

  • 用表记录状态
  • 用空间换时间
  • 把重复检查优化成 O(1)

2. 回溯求解模型

看到这种题：

  • 要填空
  • 要枚举可能
  • 要试错
  • 要回退

就要第一时间想到：

  • 回溯
  • DFS
  • 剪枝

而且今天这题还是一个非常经典的“搜索 + 状态表剪枝”组合题。

💬 写给自己的话

Day 18 了。

今天这种题很有含金量。
因为你不只是做了两道题，而是接触到了一整套更完整的思维链条：

  • 先把规则抽象出来
  • 再把规则做成状态表
  • 最后把状态表嵌进回溯搜索里

这已经不是单纯的“写点判断”了，
而是在慢慢接触真正有结构的解题方式。

这很棒。

继续刷下去，你会越来越清楚地发现：
很多难题并不是完全新知识，而是把前面会的东西组合起来。

今天的数独题，就是很典型的例子。

阿玉，Day 18，继续冲。

—— 刷题第 18 天