Sudoku

gistfile1.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define loop(ITER,FROM,TO) for(ITER=FROM;ITER<TO;ITER++)

int A[9][9];
bool chk[9];

/* print the current state of the board */
void print() {
     int i,j;
     loop(i,0,9) {
         loop(j,0,9) {
             cout << A[i][j];
         }
         cout << endl;
     }
}

/* get which numbers can be used to fill the given row, col */
vector<int> chkall(int row,int col) {
     int i,j;
     vector<int> ret;
     loop(i,0,9) chk[i]=false;
     // basic exclusion
     loop(i,0,9) {
         loop(j,0,9) {
             // if it's in the same row or column or block
             // and it's filled, exclude it
             if(A[i][j]!=0 && (i==row || j==col
                 ||(i/3==row/3 && j/3==col/3))) 
                 chk[A[i][j]-1]=true;
         }
     }
     loop(i,1,10)
         if(!chk[i-1]) ret.push_back(i);
     return ret;
}

/* fill in everything possible using pigeon-hole principle */
void pigeon_hole() {
     int i,j;
     bool found(true);
     while(found) {
         found=false;
         loop(i,0,9) { 
             loop(j,0,9) {
                 if(A[i][j]==0) {
                     vector<int> go=chkall(i,j);
                     // fill in definites
                     if(go.size()==1) { 
                         A[i][j]=go[0];
                         found=true;
                     }
                 }
             }
         }
     }
}
bool process() {
     // i=row,j=col,k=branching factor
     unsigned int i,j,k;
     loop(k,2,10) {
         loop(i,0,9) {
             loop(j,0,9) {
                 if(A[i][j]==0) {
                     vector<int> go=chkall(i,j);
                     // if branching factor > k
                     if(go.size()>k) break;
                     // recurse for each possibility
                     unsigned int n;
                     loop(n,0,go.size()){
                         A[i][j]=go[n];
                         // if found solution stop checking
                         if(process()) return true;
                     }
                     // exhausted possibilities, clear it
                     A[i][j]=0;
                     return false;
                 }                
             }
         }
     }
     // if there are no zeros, we found a solution
     return true;
}    

int main() {
     int i,j,n;
     string buf;
     for(cin>>n;n>0;n--) {
         cin >> ws;
         loop(i,0,9) {
             getline(cin,buf);
             loop(j,0,9)
                 A[i][j]=buf[j]-'0';
         }
         // we may be able to get a unique solution 
         // or close to one by just repeatedly matching the constraints
         pigeon_hole();
         // fill in the rest using a backtracking algorithm
         process();
         // print out solution 
         print();
     } 
     return 0;
}