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

回溯算法专题(十)：二维递归的完全体——暴力破解「解数独」

news 2026/6/30 5:21:08

哈喽各位，我是前端小L。

欢迎来到我们的回溯算法专题第十篇！数独游戏大家应该都玩过，规则极其“简单粗暴”：

数字 1-9在每一行只能出现一次。
数字 1-9在每一列只能出现一次。
数字 1-9在每一个以粗实线分隔的3x3 宫内只能出现一次。

我们现在的任务是：写一个程序，把一个残缺的数独填完。这道题和之前最大的不同在于：我们要找的不是“所有解”，而是“一个解”。一旦找到，立刻停止！这意味着我们的递归函数要有返回值 (bool)，用来告诉上一层：“搞定了，别试了，快撤！”

力扣 37. 解数独

https://leetcode.cn/problems/sudoku-solver/

题目分析：

输入：9x9的二维字符数组board。空位用'.'表示。
目标：原地修改board，填入唯一的一个可行解。

核心思维：如何遍历二维空格？

在 N 皇后中，我们通过backtrack(row + 1)来控制递归深度。但在数独中，空格是散落在棋盘各处的。我们通常采用双重循环 + 递归的策略：

递归逻辑（伪代码）：

Plaintext

function backtrack(board): for i from 0 to 8: for j from 0 to 8: if board[i][j] is Empty: // 发现一个坑！尝试填 1-9 for k from '1' to '9': if isValid(i, j, k): 填入 k if backtrack(board) is True: return True // 找到了！一路绿灯返回 撤销 k (回溯) return False // 1-9 都试过了都不行，说明前面的步骤填错了，无解 return True // 遍历完所有格子没返回 False，说明填满了！

注意到了吗？这个递归结构和之前的很不一样。它在函数内部就开启了对整个棋盘的扫描。一旦发现空格，就通过递归去填下一个空格。

`isValid`的九宫格判定

判断行和列很简单。难点在于判断3x3 九宫格。对于任意坐标(r, c)，它所属的 3x3 宫的左上角坐标是：

startRow = (r / 3) * 3
startCol = (c / 3) * 3通过这两个基准点，我们可以遍历该宫内的 9 个格子。

代码实现 (C++)

C++

#include <vector> using namespace std; class Solution { private: // 判断在 board[row][col] 填入 val 是否合法 bool isValid(int row, int col, char val, vector<vector<char>>& board) { // 1. 检查行 for (int j = 0; j < 9; j++) { if (board[row][j] == val) return false; } // 2. 检查列 for (int i = 0; i < 9; i++) { if (board[i][col] == val) return false; } // 3. 检查 3x3 九宫格 int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int i = startRow; i < startRow + 3; i++) { for (int j = startCol; j < startCol + 3; j++) { if (board[i][j] == val) return false; } } return true; } // 返回值 bool：表示是否找到了一组解 // 如果找到，立即停止后续搜索 bool backtrack(vector<vector<char>>& board) { // 遍历整个棋盘寻找空格 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { // 如果发现空格 if (board[i][j] == '.') { // 尝试填入 '1' 到 '9' for (char k = '1'; k <= '9'; k++) { if (isValid(i, j, k, board)) { // 做选择 board[i][j] = k; // 递归：如果后续的填充成功了，那我也直接返回 true if (backtrack(board)) return true; // 撤销选择 (回溯) board[i][j] = '.'; } } // 9个数字都试完了还不行，说明这个空格在这个局面下无解 // 或者是前面的步骤填错了，需要回溯 return false; } } } // 如果两个循环跑完都没有返回 false，说明没有空格了（填满了） return true; } public: void solveSudoku(vector<vector<char>>& board) { backtrack(board); } };