My Weblog

Blog about programming and math

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;
	}
Advertisements

August 8, 2010 - Posted by | Programming

4 Comments »

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: