TIOJ 1025 . 數獨問題

原來只要報搜.___.

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
int tab[81];
int sol[100][81];
int solcnt;
int gain(int x, int y){ return tab[9*y + x];}
bool check(int x, int y){
 //printf("check %d %d\n", x, y);
 int cnt[10] = {0};
 for(int lx = 0;lx < 9;lx++){
  //printf("%d\n", gain(x, lx));
  cnt[gain(x, lx)]++;
 }
 //printf("CNT\n");
 for(int lx = 1;lx <= 9;lx++){
  //printf("%d ", cnt[lx]);
  if(cnt[lx] >= 2)
   return false;
 }
 //printf("pass\n");
 memset(cnt, 0, sizeof(cnt));
 for(int lx = 0;lx < 9;lx++)
  cnt[gain(lx, y)]++;
 for(int lx = 1;lx <= 9;lx++)
  if(cnt[lx] >= 2)
   return false;
 memset(cnt, 0, sizeof(cnt));
 int r = x/3*3, c = y/3*3;
 for(int lx = 0;lx < 3;lx++)
  for(int ly = 0;ly < 3;ly++)
   cnt[gain(r+lx, c+ly)]++;
 for(int lx = 1;lx <= 9;lx++)
  if(cnt[lx] >= 2)
   return false;
 return true;
}
void dfs(int x, int y){
 if(x == 9 and y == 8){
  for(int lx = 0;lx < 81;lx++)
   sol[solcnt][lx] = tab[lx];
  solcnt++;
  return;
 }
 if(x == 9){ dfs(0, y+1); return;}
 if(gain(x, y) == 0){
  for(int lx = 1;lx <= 9;lx++){
   tab[9*y + x] = lx;
   if(check(x, y)){
    dfs(x+1, y);
   }
   tab[9*y + x] = 0;
  }
 }else{
  dfs(x+1, y);
 }
 return;
}
int main()
{
 for(int lx = 0;lx < 81;lx++)
  scanf("%d", &tab[lx]);
 dfs(0, 0);
 for(int ls = 0;ls < solcnt;ls++){
  for(int lx = 0;lx < 81;lx++)
   printf("%d%c", sol[ls][lx], (lx%9 == 8) ? '\n' : ' ');
  puts("");
 }
 printf("there are a total of %d solution(s).\n", solcnt);
 return 0;
}