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.

No comments:

Post a Comment