解数独

编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

#include<iostream>
#include<vector>
using namespace std;
class Solution
{ 
public:vector<vector<bool>>line;//记录数字是否在当前行出现过vector<vector<bool>>cloumn;//记录数字是否在当前列出现过vector<vector<vector<bool>>>block;//记录数字是否在当前块出现过vector<pair<int, int>>spaces;//记录空格的位置，输入时以"."代替空格，即记录"."出现的位置bool valid = false;//记录是否已经遍历完所有空格void solveSoduku(vector<vector<char>>& input){line.resize(9, vector<bool>(9, false));cloumn.resize(9, vector<bool>(9, false));block.resize(9, vector<vector<bool>>(9, vector<bool>(9, false)));            //遍历数独         int n = 9;for(int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){//搜索空格,记录空格的位置if (input[i][j] == '.')spaces.emplace_back(i, j);else{int digit = input[i][j] - '0' - 1;line[i][digit] = true;cloumn[j][digit] = true;block[i / 3][j / 3][digit] = true;}}}dfs(input, 0);}void dfs(vector<vector<char>>& input, int pos)//pos 为开始位置{      //终止条件if (pos == spaces.size()){valid = true;return;}//找到空格，填补空格，修改空格的bool值，路走不通就回溯         int i = spaces[pos].first;int j = spaces[pos].second;for (int digit = 0; digit < 9&&!valid; digit++){                      if (!line[i][digit] && !cloumn[j][digit] && !block[i / 3][j / 3][digit]){input[i][j] = digit + '0' + 1;line[i][digit] = true;cloumn[j][digit] = true;block[i / 3][j / 3][digit] = true;dfs(input, pos + 1);//回溯line[i][digit] = cloumn[j][digit] = block[i / 3][j / 3][digit] = false;}}}void print(vector<vector<char>>const input){for (auto x : input){cout << "------------------------------------" << endl;for (auto y : x){y == '.' ? cout << "  " : cout << " " << y;cout << " |";}cout << endl;}cout << "------------------------------------" << endl;}
};
int main()
{       vector<vector<char>>input= {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},{'6', '.', '.', '1', '9', '5', '.', '.', '.'},{'.', '9', '8', '.', '.', '.', '.', '6', '.'},{'8', '.', '.', '.', '6', '.', '.', '.', '3'},{'4', '.', '.', '8', '.', '3', '.', '.', '1'},{'7', '.', '.', '.', '2', '.', '.', '.', '6'},{'.', '6', '.', '.', '.', '.', '2', '8', '.'},{'.', '.', '.', '4', '1', '9', '.', '.', '5'},{'.', '.', '.', '.', '8', '.', '.', '7', '9'}};  Solution solution;solution.print(input);solution.solveSoduku(input);cout << "解数独如下：" << endl;solution.print(input);cout << endl;return 0;
}

运行结果：