题目描述
问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。
输入：
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出：
完整的9X9盘面数组
输入描述:
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出描述:
完整的9X9盘面数组
示例1
输入
0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1输出
5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1https://www.nowcoder.com/practice/78a1a4ebe8a34c93aac006c44f6bf8a1?tpId=37&tqId=21267&rp=1&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking&tab=answerKey
注意：/* 如果构造不成功，还原当前位 为什么复位，因为这是一个递归，比如一个位置用1尝试，它会改变后续很多空的位置，这样
就是一个连锁反应，必须全部复位*/
我居然SB般的想了很久，脑子真是锈掉了。
#include<bits/stdc++.h>
using namespace std;
bool isValid(vector<vector<int>> &num,int n,int value)
{int row=n/9,col=n%9;for(int i=0;i<9;i++)//先检查row这一行有没有和value重复的元素{if(num[row][i]==value){return false;}}for(int i=0;i<9;i++)//检查col这一列{if(num[i][col]==value){return false;}}int x=row/3*3,y=col/3*3;//小九空格起始坐标for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(num[x+i][y+j]==value){return false;}}}return true;
}
void DFS(vector<vector<int>> &num,int n,int &flag)
{if(n>80)//元素计数从0开始，到80就已经有81个元素了{flag=1;for(int i=0;i<9;i++){for(int j=0;j<8;j++){cout<<num[i][j]<<" ";}cout<<num[i][8]<<endl;}return ;//这里应该直接结束了，在LeetCode37对比发现这个错误，不然下面的row，col等会越界，81/9=9，下标越界了，我代码里设置的大，//不会出大意外，还是还要严谨可控}int row=n/9,col=n%9;if(num[row][col]!=0){DFS(num,n+1,flag);}else{for(int i=1;i<=9;i++){if(isValid(num,n,i)){num[row][col]=i;DFS(num,n+1,flag);if(flag){return ;}num[row][col]=0;//必须复位操作}}}
}
int main()
{ vector<vector<int>> num(10,vector<int>(10,0));for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++)cin >> num[i][j]; }int flag=0;DFS(num,0,flag);return 0;
}