所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析：本题也是一道困难题，难点在于如何构建数独棋盘，如何检查棋盘的合法性，再一个难点在于如何对棋盘进行遍历并放置数字。数组棋盘的构建笔者采用了一个最朴素的方法，将已知的‘.’和数字依次push_back进棋盘数组中；然后根据数独的规则，每行每列，每个九空格内不能有重复的元素，构建isValid函数；然后利用两层嵌套循环遍历棋盘，棋盘的每个点用1-9的数组依次带入，如果合法则进行下一步的递归。最终得到一个数独的解，这个解就是整个棋盘数组，将其输出。
程序如下：
class Solution {
private:
bool isValid(vector<vector<char>>& board, char num, int row, int col) {
// 检查棋盘是否合法
// 检查行列，九空格内是否有重复元素
for (int i = 0; i < board.size(); i++) {
// 检查列
if (board[i][col] == num) return false;
}
for (int j = 0; j < board[0].size(); j++) {
// 检查行
if (board[row][j] == num) return false;
}
// 检查九空格，找到board[row][col]所在的九空格， 然后用二层循环遍历
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] == num) return false;
}
}
return true;
}
bool backtracking(vector<vector<char>>& board) {
for (int row = 0; row < board.size(); row++) {
for (int col = 0; col < board[0].size(); col++) {
if (board[row][col] != '.') continue;
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, num, row, col)) {
board[row][col] = num; // 放置数字，处理节点;
if(backtracking(board)) return true; // 递归
board[row][col] = '.'; // 回溯，撤销处理结果
}
}
return false; // 九个数字都不行，说明数独无解
}
}
return true;
}
public:
vector<vector<char>> solveSudoku(vector<vector<char>>& board) {
backtracking(board);
return board;
}
};
复杂度分析：
- 时间复杂度： O ( n ! ) O(n!) O(n!)。
- 空间复杂度： O ( n ) O(n) O(n)。
三、完整代码
# include <iostream>
# include <vector>
# include <string>
using namespace std;
class Solution {
private:
bool isValid(vector<vector<char>>& board, char num, int row, int col) {
// 检查棋盘是否合法
// 检查行列，九空格内是否有重复元素
for (int i = 0; i < board.size(); i++) {
// 检查列
if (board[i][col] == num) return false;
}
for (int j = 0; j < board[0].size(); j++) {
// 检查行
if (board[row][j] == num) return false;
}
// 检查九空格，找到board[row][col]所在的九空格， 然后用二层循环遍历
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] == num) return false;
}
}
return true;
}
bool backtracking(vector<vector<char>>& board) {
for (int row = 0; row < board.size(); row++) {
for (int col = 0; col < board[0].size(); col++) {
if (board[row][col] != '.') continue;
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, num, row, col)) {
board[row][col] = num; // 放置数字，处理节点;
if(backtracking(board)) return true; // 递归
board[row][col] = '.'; // 回溯，撤销处理结果
}
}
return false; // 九个数字都不行，说明数独无解
}
}
return true;
}
public:
vector<vector<char>> solveSudoku(vector<vector<char>>& board) {
backtracking(board);
return board;
}
};
int main() {
vector<vector<char>> board;
board.push_back({
'5', '3', '.', '.', '7', '.', '.', '.', '.' });
board.push_back({
'6', '.', '.', '1', '9', '5', '.', '.', '.' });
board.push_back({
'.', '9', '8', '.', '.', '.', '.', '6', '.' });
board.push_back({
'8', '.', '.', '.', '6', '.', '.', '.', '3' });
board.push_back({
'4', '.', '.', '8', '.', '3', '.', '.', '1' });
board.push_back({
'7', '.', '.', '.', '2', '.', '.', '.', '6' });
board.push_back({
'.', '6', '.', '.', '.', '.', '2', '8', '.' });
board.push_back({
'.', '.', '.', '4', '1', '9', '.', '.', '5' });
board.push_back({
'.', '.', '.', '.', '8', '.', '.', '7', '9' });
Solution s1;
vector<vector<char>> result = s1.solveSudoku(board);
for (vector<vector<char>>::iterator it = result.begin(); it != result.end(); it++) {
for (vector<char>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {
cout << *jt << " ";
}
cout << endl;
}
system("pause");
return 0;
}
end
