PKU 2918 Tudoku

PKU

http://poj.org/problem?id=2918
数独を解く。

前に書いたやつ(PKU2676)をコピー。

char in[9][10];
bool ver[9][9],hor[9][9],sq[9][9];

bool dfs(int ne){
  if(ne>80)return true;
  int x=ne/9,y=ne%9;
  if(in[x][y]!='0')return dfs(ne+1);

  int tx=x-x%3,ty=y-y%3;
  int sn=tx/3*3+ty/3;
  
  rep(i,9){
    if(ver[y][i] || hor[x][i] || sq[sn][i])continue;
    in[x][y]=i+'1';
    ver[y][i]=hor[x][i]=sq[sn][i]=true;
    if(dfs(ne+1))return true;
    ver[y][i]=hor[x][i]=sq[sn][i]=false;
  }
  in[x][y]='0';
  return false;
}

main(){
  int t;
  cin>>t;
  rep(ca,t){
    memset(ver,0,sizeof(ver));
    memset(hor,0,sizeof(hor));
    memset(sq,0,sizeof(sq));
    
    rep(i,9)scanf("%s",in[i]);
    rep(i,9){
      rep(j,9){
	if(in[i][j]=='0')continue;
	int nn=in[i][j]-'1';
	ver[j][nn]=true;
	hor[i][nn]=true;
	int tx=i-i%3,ty=j-j%3;
	int sn=tx/3*3+ty/3;
	sq[sn][nn]=true;
      }
    }

    dfs(0);
    cout<<"Scenario #"<<ca+1<<':'<<endl;
    rep(i,9)puts(in[i]);
    puts("");
  }
}