SUDOKU Solver

Submitted by bOtskOOl on Fri, 11/13/2009 - 14:53

 

Almost everyone of you might have one or the other time stuck upon a SUDOKU

 

Here’s a simple program that solves the hardest of the Sudoku puzzles  in fraction of a second.

 

SUDOKU – THE GAME

A Sudoku in the most common form consists of a 9 x 9 grid of numbers

The grid is subdivided into 9 blocks of  3 x 3  size.

Initially the grid is partially filled (with numbers from 1-9), your task is to complete the grid using numbers from 1-9 such that

  • -no row/column contains a repeating digit
  • -no sub block contains repeating digit

In short the digits 1-9 must occur in each row/column/sub block.

 

Now for the program

 

The program makes use of BACKTRACKING.

 

Input format

 

You are required to enter the partially filled Sudoku in the following format

  • -Each row represents a line.
  • -Empty cells are denoted by a “.”
  • -Non-empty cells are denoted by the digit they are  filled with

 

Sample input

....41...

...6....5

.....7.9.

....1.3..

.5......1

.2.......

..18...76

.7......2

........3

 

Program explained

 

Input loop

 

for(i=0,K=0;i<N2;i++)
{
    scanf("%s",input[i]);
        for(k=0;k<N2;k++)
            {
            if(input[i][k]>47&&input[i][k]<58)
                {
                xy[K][0]=i;
                xy[K][1]=k;
                //d=input[i][k]-48;
                game[i][k]=input[i][k]-48;;
                K++;
                }
            }
}

The above code is self explanatory . Only thing worth noting here is the arrary game[9][9] which represents the puzzle and the array xy[][] which stores the x and y coordinates of the positions which are are already filled.

 

 

Solving the puzzle

The heart of the  program is the solve() function

The function is first called as

solve(game,0,0,xy,K,N)

 

0,0 indicate that we start with the top leftmost cell .

 

Algorithm

First an array of possible values (not present in row, column or sub-grid) for a cell is generated. Then we  fill the cell with one of the possible values from the array and  subsequently call the function recursively for for next cell. This procedure is repeated till either the puzzle is solved or the list of possible values for a particular cell is exhausted. In the latter scenario (indicated a return value of -1) the content of the preceeding cell is changed to the next possible value and the procedure is repeated again for the remaining cells.

 

Condition for successful completion

if(i==N2||j==N2)    
      return 0;

this condition when true indicates that puzzle has been solved , returns success code ie. 0

 

Seeding the possible values’ array

int temp[9]={1,2,3,4,5,6,7,8,9};
 
J=j==N2-1?0:j+1;
I=j==N2-1?i+1:i;
 
if(in_array(i,j,xy,K))
    return solve(game,I,J,xy,K,N);
 
//this loop checks  the horizontal rows
for(l=0;l<N2;l++)
    {
            if(game[i][l]!=0)
            temp[game[i][l]-1]=0;
    }
//this loop checks  the vertical rows
for(l=0;l<N2;l++)
    {
            if(game[l][j]!=0)
            temp[game[l][j]-1]=0;
    }
 
//this loop checks in the boxes
int A=N*(i/N),B=N*(i/N)+N;
int C=N*(j/N),D=N*(j/N)+N;
for(k=A;k<B;k++)
    {
    for(l=C;l<D;l++)
            if(game[k][l]!=0)
            temp[game[k][l]-1]=0;
    }

 

The above snippet creates a list of possible values in that particular cell. The temp array is initialized with numbers 1-9 and then the row , column and sub-grid containing the cell is checked . All numbers already present are zeroed out and thus only the possible values for that cell remain.

 

Moving ahead

 

while(1)
{
        for(;level<N2&&temp[level]==0;level++);
        if(level==N2)
        {game[i][j]=0;
        return -1;
        }
            game[i][j]=temp[level++];
    if(solve(game,I,J,xy,K,N)==0)
        return 0;
}

Finally we assign one value from the array to the cell and call the solve function for the next cell in sequence. The next cell coordinates are determined by the values  I,J calculated earlier. A return value of -1 indicates incorrectly filled value and thus the content of the current cell are changed to the next possible value are the process repeated.

 

Here is the complete code

 

#include<iostream>
#include<cstdio>
using namespace std;
 
int solve(int game[][9],int i ,int j,int xy[][2],int K,int N);
int in_array(int x,int y, int arr[][2],int n);
 
int main()
{
 
 
 
int N=3,N2,K,xy[81][2]={-1},d,i,j,k;
int game[9][9]={0};
 
N2=N*N;
 
char input[81][9];
for(i=0,K=0;i<N2;i++)
{
    scanf("%s",input[i]);
        for(k=0;k<N2;k++)
            {
            if(input[i][k]>47&&input[i][k]<58)
                {
                xy[K][0]=i;
                xy[K][1]=k;
                //d=input[i][k]-48;
                game[i][k]=input[i][k]-48;;
                K++;
                }
            }
}
 
 
 
cout<<endl<<"Solving....."<<endl;
 
if(solve(game,0,0,xy,K,N)!=0)
cout<<endl<<"No Solution";
else
    {
    for(i=0;i<N2;i++)
        {for(j=0;j<N2;j++)
         printf("%d",game[i][j]);
        printf("\n");
        }
        printf("\n");
    }
 
return 0;
}
 
 
int solve(int game[][9],int i ,int j,int xy[][2],int K,int N)
{
int N2=N*N,J,I,k,l,level;
 
//puzzle has been solved , return success code ie. 0
if(i==N2||j==N2)
    return 0;
 
int temp[9]={1,2,3,4,5,6,7,8,9};
 
J=j==N2-1?0:j+1;
I=j==N2-1?i+1:i;
 
if(in_array(i,j,xy,K))
    return solve(game,I,J,xy,K,N);
 
//this loop checks  the horizontal rows
for(l=0;l<N2;l++)
    {
            if(game[i][l]!=0)
            temp[game[i][l]-1]=0;
    }
//this loop checks  the vertical rows
for(l=0;l<N2;l++)
    {
            if(game[l][j]!=0)
            temp[game[l][j]-1]=0;
    }
 
//this loop checks in the boxes
int A=N*(i/N),B=N*(i/N)+N;
int C=N*(j/N),D=N*(j/N)+N;
for(k=A;k<B;k++)
    {
    for(l=C;l<D;l++)
            if(game[k][l]!=0)
            temp[game[k][l]-1]=0;
    }
//uncomment these two loops if you dont want repeating elements along the elements
/*
if(i==j)
for(l=0;l<N2;l++)
    {
            if(game[l][l]!=0)
            temp[game[l][l]-1]=0;
    }
if(i+j==N2-1)
for(l=0;l<N2;l++)
    {
            if(game[l][N2-l-1]!=0)
            temp[game[l][N2-l-1]-1]=0;
    }
 
*/
level=0;
while(1)
{
 
    for(;level<N2&&temp[level]==0;level++);
        if(level==N2)
        {game[i][j]=0;
        return -1;
        }
 
        game[i][j]=temp[level++];
    if(solve(game,I,J,xy,K,N)==0)
        return 0;
}
}
 
int in_array(int x, int y, int arr[][2],int n)
{
for(int i=0;i<n;i++)
{
 
if(arr[i][0]==x&&arr[i][1]==y)
return 1;
}
return 0;
}

 

Your rating: None Average: 5 (3 votes)
Tags: