# My Weblog

## Project Euler 96 [Sudoku Solver]

Project Euler 96 is sudoku problem. There are many ways to solve it . Using backtracking or Knuth’s dancing link list. The second one is bit difficult but efficient and backtracking is easy but not efficient. Here is my recursive solution. First i tried some simple iterative search to fill the sudoku. If i find a solution for any block then again i started from beginning.

```while(f)
{
f=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(M[i][j]==0)
{
bool t[10];memset(t,0,sizeof t);
for(int k=0;k<9;k++) t[M[i][k]]=t[M[k][j]]=1;
int m=(i/3)*3,n=(j/3)*3;
for(int k=0;k<3;k++) for(int l=0;l<3;l++) t[M[m+k][n+l]]=1;
int cnt_t=0,sol;
for(int k=1;k<10;k++) if(!t[k]) cnt_t++,sol=k;
if(cnt_t==1) {M[i][j]=sol;f=1;}
}
}
```

I counted how many blocks are still there which contains zero and i stored all. I started DFS algorithm by putting a number from 1 to 9 in the block [which contains 0] and simply test if it violate the rule of sudoku[ row, column and block ].

```bool check(int r,int c,int k)
{
//find out if element k is more than one in grid
for(int i=0;i<9;i++)
{
if(i==c) continue;
if(M[r][i]==k) return 0;
}
for(int i=0;i<9;i++)
{
if(i==r) continue;
if(M[i][c]==k)return 0;
}
int m=(r/3)*3,n=(c/3)*3;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if((m+i)==r && (n+j)==c) continue;
if(M[m+i][n+j]==k) return 0;
}

return 1;
}
```

Complete source code is Here.

```#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
typedef pair<int,int> PI;
vector<PI> v;
int M[9][9],N;
bool fg;
bool check(int r,int c,int k)
{
//find out if element k is more than one in grid
for(int i=0;i<9;i++)
{
if(i==c) continue;
if(M[r][i]==k) return 0;
}
for(int i=0;i<9;i++)
{
if(i==r) continue;
if(M[i][c]==k)return 0;
}
int m=(r/3)*3,n=(c/3)*3;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if((m+i)==r && (n+j)==c) continue;
if(M[m+i][n+j]==k) return 0;
}

return 1;
}
bool  dfs(int lev)
{
if(lev==N) //we reached last level
{

int cnt=0;
for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(M[i][j]) cnt++;//printf("%d%c",M[i][j],(j==8)?'\n':' ');
if(cnt==81) return 1;
return 0;
}
for(int k=1;k<=9 && !fg ;k++)
{

M[v[lev].first][v[lev].second]=k;
if(check(v[lev].first,v[lev].second,k)==0) {M[v[lev].first][v[lev].second]=0;continue;}
if(dfs(lev+1)) return 1;
M[v[lev].first][v[lev].second]=0;
}
return 0;

}
int main()
{
int u,sum=0;
for(int c=0;c<50;c++)
{
cin>>u;
cout<<u<<endl;
memset(M,0,sizeof M);
v.clear();
for(int i=0;i<9;i++)  for(int j=0;j<9;j++) scanf("%d",&M[i][j]);
//first try some simple filling without recursion
bool f=1;
while(f)
{
f=0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(M[i][j]==0)
{
bool t[10];memset(t,0,sizeof t);
for(int k=0;k<9;k++) t[M[i][k]]=t[M[k][j]]=1;
int m=(i/3)*3,n=(j/3)*3;
for(int k=0;k<3;k++) for(int l=0;l<3;l++) t[M[m+k][n+l]]=1;
int cnt_t=0,sol;
for(int k=1;k<10;k++) if(!t[k]) cnt_t++,sol=k;
if(cnt_t==1) {M[i][j]=sol;f=1;}
}
}
for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(M[i][j]==0)v.push_back(PI(i,j));//get all 0 index
N=v.size();
if(dfs(0)) for(int i=0;i<9;i++) for(int j=0;j<9;j++) printf("%d%c",M[i][j],(j==8)?'\n':' ');
else cout<<"no solution\n";

sum+=M[0][0]*100+M[0][1]*10+M[0][2];
cout<<endl;
}
cout<<sum<<endl;
}
```

August 8, 2010 - Posted by | Programming

1. Comment by Vinny Diehl | March 23, 2012 | Reply

2. whats the input for the program?

Comment by John Doe | April 10, 2012 | Reply

• The input file from project Euler. I think I modified the file bit ( probably comma was replace by space ). Hope it helps

Comment by tiwari_mukesh | April 11, 2012 | Reply

3. kk thats cool.
but whats the input if i just want it 2 solve a single sudoku puzzle?

Comment by John Doe | April 11, 2012 | Reply