0
Your rating: None

CodeChef submission 130299 (C++ 4.0.0-8)

CodeChef submission 130299 (C++ 4.0.0-8) plaintext list. Status: AC, problem J1, contest NOV09. By syco (Varun Jalan), 2009-11-11 04:48:07.
  1. #include<iostream>
  2. using namespace std ;
  3. char in[10][10] ;
  4. int bit[1<<9],d1,d2,mrow[9],mcol[9],mbox[3][3] ;
  5.  
  6. bool solve()
  7. {
  8.  int i,j,k,x = -1,y = -1,p = 10,mask ;
  9.  for(i=0;i<9;i++)
  10.   for(j=0;j<9;j++) if(in[i][j] == '.')
  11.   {
  12.    mask = mrow[i] | mcol[j] | mbox[i/3][j/3] | (i == j ? d1 : 0) | (i == 8 - j ? d2 : 0) ;
  13.    int rem = 9 - bit[mask] ;
  14.    if(rem < p) p = rem,x = i,y = j ;
  15.   }
  16.  if(p == 0) return false ;
  17.  if(p == 10) return true ;
  18.  
  19.  mask = mrow[x] | mcol[y] | mbox[x/3][y/3] | (x == y ? d1 : 0) | (x == 8 - y ? d2 : 0) ;
  20.  for(i=0;i<9;i++) if(!(mask&1<<i))
  21.  {
  22.   if(x == y) d1 ^= 1 << i ;
  23.   if(x == 8 - y) d2 ^= 1 << i ;
  24.   mrow[x] |= 1 << i ;
  25.   mcol[y] |= 1 << i ;
  26.   mbox[x/3][y/3] |= 1 << i ;
  27.   in[x][y] = '1' + i ;
  28.   if(solve()) return true ;
  29.   if(x == y) d1 ^= 1 << i ;
  30.   if(x == 8 - y) d2 ^= 1 << i ;
  31.   mrow[x] ^= 1 << i ;
  32.   mcol[y] ^= 1 << i ;
  33.   mbox[x/3][y/3] ^= 1 << i ;
  34.   in[x][y] = '.' ;
  35.  }
  36.  return false ;
  37. }
  38.  
  39.  
  40. main()
  41. {
  42.  int i,j,k,runs ;
  43.  
  44.  for(i=1;i<1<<9;i++) bit[i] = bit[i>>1] + (i&1) ;
  45.  
  46. // freopen("in.txt","r",stdin) ;
  47.  scanf("%d",&runs) ;
  48.  while(runs--)
  49.  {
  50.   d1 = d2 = 0 ;
  51.   memset(mbox,0,sizeof mbox) ;
  52.   memset(mcol,0,sizeof mcol) ;
  53.   memset(mrow,0,sizeof mrow) ;
  54.   for(i=0;i<9;i++) scanf("%s",in[i]) ;
  55.   for(i=0;i<9;i++)
  56.    for(j=0;j<9;j++)
  57.     if(in[i][j] != '.')
  58.     {
  59.      if(i == j) d1 |= 1 << (in[i][j] - '1') ;
  60.      if(i == 8 - j) d2 |= 1 << (in[i][j] - '1') ;
  61.      mrow[i] |= 1 << (in[i][j] - '1') ;
  62.      mcol[j] |= 1 << (in[i][j] - '1') ;
  63.      mbox[i/3][j/3] |= 1 << (in[i][j] - '1') ;                      
  64.     }
  65.   solve() ;
  66.   for(i=0;i<9;i++) printf("%s\n",in[i]) ;
  67.   if(runs) printf("\n") ;
  68.  }
  69. // while(1) ;
  70. }
  71.

Comments