Cpp recursive solution


#1

int count=0,found=0;
bool safe(int val,int r,int c,vector<vector > sudoku){
int i,j;
if(sudoku[r][c]!=’.’)
return false;
for(i=0;i<9;i++){
if(sudoku[r][i]==(val+48))
return false;
}
for(i=0;i<9;i++){
if(sudoku[i][c]==val+48)
return false;
}
if((r%3)!=0){
r-=(r%3);
}
if((c%3)!=0){
c-=(c%3);
}
for(i=r;i<r+3;i++){
for(j=c;j<c+3;j++){
if(sudoku[i][j]==val+48){
// cout<<“qwe”<<endl;
return false;
}
}
}
return true;
}
bool solve(vector<vector > &sudoku,int r,int c,int counter){
// cout<<"called r is "<<r<<"c is "<<c<<endl;
if(found)
return true;
int i,j;
// cout<<"counter is "<<counter<<endl;
if(counter==::count){
found=1;
return true;
}
while(sudoku[r][c]!=’.’){
c++;
if(c>=9){
r++;
c=0;
}
}
for(i=1;i<=9;i++){
if(safe(i,r,c,sudoku)){
sudoku[r][c]=(i+48);
// cout<<"val is "<<sudoku[r][c]<<endl;
// cout<<"r is "<<r<<"c is “<<c<<” val is "<<i<<endl;
// counter++;
int p=r;
int q=c;
if(c==8){
p=r+1;
q=0;
}
else
q++;
if(solve(sudoku,p,q,counter+1))
return true;
sudoku[r][c]=’.’;
}
}
return false;
}
void Solution::solveSudoku(vector<vector > &sudoku) {
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(sudoku[i][j]==’.’){
::count++;
}
}
}
if(solve(sudoku,0,0,0));
::count=0;
::found=0;
}