算法1
直接dfs即可
对于当前位置 如果是初始状态已经填了数字那么继续搜当前这行的下一个点
如果当前是行的最后一个 那么就搜下一行的起点
如果是.的话,开个vis标记当前行、列、九宫格已有的数字
对于当前位置就是暴力填没被标记的数字即可
找到答案及时return
时间复杂度
dfs复杂度始终是个谜
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=15;
char mp[N][N];
int flag;
void dfs(int x,int y){
if(flag) return ;
if(x==9){
flag=1;
return ;
}
if(mp[x][y]!='.'){
if(y+1<9) dfs(x,y+1);
else dfs(x+1,0);
return ;
}
int vis[15]={};
for(int i=0;i<9;i++){
if(mp[x][i]!='.') vis[mp[x][i]-'0']++;
if(mp[i][y]!='.') vis[mp[i][y]-'0']++;
}
int r=x/3*3,c=y/3*3;
for(int i=r;i<r+3;i++){
for(int j=c;j<c+3;j++){
if(mp[i][j]!='.') vis[mp[i][j]-'0']++;
}
}
for(int i=1;i<=9;i++){
if(!vis[i]){
mp[x][y]=i+'0';
if(y+1<9) dfs(x,y+1);
else dfs(x+1,0);
if(flag) return ;
mp[x][y]='.';
}
}
}
int main(){
for(int i=0;i<9;i++) cin>>mp[i];
dfs(0,0);
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cout<<mp[i][j];
}
cout<<endl;
}
return 0;
}