POJ 2676 : Sudoku

問題リンク：2676 -- Sudoku

問題概要：
数独

解法：
DFSで全探索
各行、列、3x3のセルでどの数字を使ったかをビットでもっておく

コード：

#include<cstdio>
#include<algorithm>
#include<cmath>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

char c[9][9];
int row[9],col[9],sub[9];

inline int getIndex(int x,int y){
  x /= 3, y /= 3;
  return x + y * 3;
}

inline void print(){
  rep(i,9){
    rep(j,9) printf("%c",c[i][j]);
    puts("");
  }
}

bool dfs(int cur){

  if( cur >= 81 ) {
    print();
    return true;
  }

  int x = cur % 9, y = cur / 9;

  if( c[y][x] != '0' ) return dfs(cur+1);

  rep(i,9){
    if( ( row[y] >> i ) & 1 ) continue;
    if( ( col[x] >> i ) & 1 ) continue;
    if( ( sub[getIndex(x,y)] >> i ) & 1 ) continue;
    c[y][x] = (char)('0'+i+1);
    int tmp_r = row[y], tmp_c = col[x], tmp_s = sub[getIndex(x,y)];
    row[y] |= (1<<i), col[x] |= (1<<i), sub[getIndex(x,y)] |= (1<<i);
    if( dfs(cur+1) ) return true;
    c[y][x] = '0';
    row[y] = tmp_r, col[x] = tmp_c, sub[getIndex(x,y)] = tmp_s;
  }
  return false;
}

int main(){
  int T;
  scanf("%d",&T);
  while( T-- ){
    rep(i,9)rep(j,9)scanf(" %c",&c[i][j]);
    rep(i,9) row[i] = col[i] = sub[i] = 0;

    rep(i,9)rep(j,9){
      if( c[i][j] != '0' ) row[i] |= (1<<( c[i][j] - '0' - 1 ));
      if( c[j][i] != '0' ) col[i] |= (1<<( c[j][i] - '0' - 1 ));
      if( c[i][j] != '0' )sub[getIndex(j,i)] |= (1<<( c[i][j] - '0' - 1 ));
    }

    dfs(0);

  }
  return 0;
}