AcWing 1613. 数独简单版
原题链接
简单
作者:
sy123
,
2021-01-30 21:28:44
,
所有人可见
,
阅读 508
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
char g[N][N];
int row[N][1000],col[N][1000],cell[4][4][100];//每行每列每个9宫格这个数填过没
bool dfs(int x, int y)//一行一行的填
{
if(x==9){
for (int i = 0; i < 9; i ++ ) {
for (int j = 0; j < 9; j ++ ){
cout<<g[i][j];
}
cout<<endl;
}
return true;
}
if(y==9){
if(dfs(x+1,0))return true;
}
if(g[x][y]!='.'){ //已经填过
if(dfs(x,y+1))return true;
}
else{
for(char i='1';i<='9';i++){
if(!col[y][i]&&!row[x][i]&&!cell[x/3][y/3][i]){
g[x][y]=i;
row[x][i]=1;
col[y][i]=1;
cell[x/3][y/3][i]=1;
if(dfs(x,y+1))return true;
g[x][y]='.';
row[x][i]=0;
col[y][i]=0;
cell[x/3][y/3][i]=0;
}
}
}
return false;
}
int main()
{
for (int i = 0; i < 9; i ++ )
for (int j = 0; j < 9; j ++ ){
cin>>g[i][j];
if(g[i][j]!='.'){
row[i][g[i][j]]=1;
col[j][g[i][j]]=1;
cell[i/3][j/3][g[i][j]]=1;
}
}
dfs(0,0);
return 0;
}