## Thursday, July 17, 2008

### Sudoku Solver

`#include <stdio.h>int row[9],col[9],box[3][3];int g[9][9];bool test(int & x,int j) { return (x & (1<<j)) >0 ;}void set(int & x,int j) { x |= (1<<j) ;}void unset(int & x,int j) { x &= (~(1<<j)); }bool doit(int x,int y){ if(x==9) return true; if(g[x][y]) return doit(x+(y==8),(y+1)%9); for(int i=0; i<9; i++) {  if(!test(row[x],i) && !test(col[y],i) && !test(box[x/3][y/3],i)){   set(row[x],i);   set(col[y],i);   set(box[x/3][y/3],i);   if(doit(x+(y==8),(y+1)%9)) {    g[x][y] = i+1;    return true;   }   unset(row[x],i); unset(col[y],i); unset(box[x/3][y/3],i);  } } return false;}main(){ for(int i=0; i<9; i++) {  for(int j=0; j<9; j++){   int k;   scanf("%d",&k);   if(k--){    g[i][j] = k+1;    row[i] |= (1<<k);    col[j] |= (1<<k);    box[i/3][j/3] |= (1<<k);   }  } } if(doit(0,0)){  for(int i=0; i<9; i++) {   for(int j=0; j<9; j++)     printf("%d%s", g[i][j], (j==8?"\n":(j%3==2?" | ":" ")));   if(i != 8 && i%3==2){    printf("---------------------\n");;   }  } } else{  printf("No Solution!\n"); }}`

Thanks to Lakshmi Subrahmanyam for providing the solution.