链接：https://ac.nowcoder.com/acm/problem/24911 来源：牛客网
数独是一种填数字游戏，英文名叫 Sudoku，起源于瑞士，上世纪 70 年代由美国一家数学逻辑游戏杂志首先发表，名为 Number Place，后在日本流行，1984 年将 Sudoku 命名为数独，即 “独立的数字” 的缩写，意思是 “在每一格只有一个数字”。
2004 年，曾任中国香港高等法院法官的高乐德 (Wayne Gould) 把这款游戏带到英国，成为英国流行的数学智力拼图游戏。
玩家需要根据 9×9 盘面上的已知数字，推理出所有剩余位置的数字，并满足每一行、每一列、每一个粗线九宫格内的数字包含有 1-9 的数字，且不重复。 现在给你一个数独，请你解答出来。每个数独保证有且只有一个解。
输入描述: 输入仅一组数据，共 9 行 9 列，表示初始数独（其中 0 表示数独中的空位）。 输出描述: 输出共 9 行 9 列，表示数独的解。
注意⾏末没有空格。 示例1 输入 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 输出 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9
开三个二维数组分别标记当前行、列、宫已有哪些数字，再开一个vector<pair<int,int>>存储0的坐标。读入数据时，读入0就存入vector，不是0就标记行列宫已有该数字。开一个ind=0作为dfs的参数，ind是vector的下标。 开始dfs，对于当前ind表示的坐标，从1到9遍历一遍，如果某个数字没有被行列宫标记过，就选上，然后标记行列宫，深搜ind+1。如果该数字是错误的，那么dfs到不了终点就会返回，此时再舍弃该数字，还原行列宫，for循环继续。
```for(int k=1;k<=9;k++){
if(hang_used[i][k]||lie_used[j][k]||gong_used[ind_gong(i,j)][k])continue;
hang_used[i][k]=1;
lie_used[j][k]=1;
gong_used[ind_gong(i,j)][k]=1;
num[i][j]=k;
dfs(cnt+1);
num[i][j]=0;
hang_used[i][k]=0;
lie_used[j][k]=0;
gong_used[ind_gong(i,j)][k]=0;
}
ac代码：
``` #include<bits/stdc++.h>
#include<iomanip>
#include<cmath>
using namespace std;
#define ll long long
#define lf double
#define MAX_NUM 500
vector<vector<int>>num(11,vector<int>(11,0));
vector<vector<int>>hang_used(11,vector<int>(11,0));
vector<vector<int>>lie_used(11,vector<int>(11,0));
vector<vector<int>>gong_used(11,vector<int>(11,0));
vector<pair<int,int>>poision_0;
int cnt=0;
int ind_gong(int x,int y){
if(x>=1&&x<=3){
if(y>=1&&y<=3)return 1;
else if(y>=4&&y<=6)return 2;
else if(y>=7&&y<=9)return 3;
}else if(x>=4&&x<=6){
if(y>=1&&y<=3)return 4;
else if(y>=4&&y<=6)return 5;
else if(y>=7&&y<=9)return 6;
}else if(x>=7&&x<=9){
if(y>=1&&y<=3)return 7;
else if(y>=4&&y<=6)return 8;
else if(y>=7&&y<=9)return 9;
}
return -1;
}
void dfs(int cnt){
if(cnt==(int)poision_0.size()){
// printf("--------------------\n");
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cout<<num[i][j]<<" ";
}
cout<<endl;
}
return ;
}
int i=poision_0[cnt].first;
int j=poision_0[cnt].second;
for(int k=1;k<=9;k++){
if(hang_used[i][k]||lie_used[j][k]||gong_used[ind_gong(i,j)][k])continue;
hang_used[i][k]=1;
lie_used[j][k]=1;
gong_used[ind_gong(i,j)][k]=1;
num[i][j]=k;
dfs(cnt+1);
num[i][j]=0;
hang_used[i][k]=0;
lie_used[j][k]=0;
gong_used[ind_gong(i,j)][k]=0;
}
}
void solve(){
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cin>>num[i][j];
if(num[i][j]){
hang_used[i][num[i][j]]=1;//第i行有了num[i][j]
hang_used[i][0]+=1;//i行有一个数
lie_used[j][num[i][j]]=1;
lie_used[j][0]+=1;
gong_used[ind_gong(i,j)][num[i][j]]=1;
gong_used[ind_gong(i,j)][0]+=1;
}else {
poision_0.push_back(pair<int,int>(i,j));
}
}
}
dfs(0);
}
int main(){
int T;
T=1;
// cin>>T;
// getchar();
while(T--){
solve();
}
return 0;
}
京公网安备 11010502036488号