Brute force algorithm implemented for sudoku solver in C [closed]
- by 0cool
This is my code that I have written in C.. It could solve certain level of problems but not the harder one.. I could not locate the error in it, Can you please find that..
# include <stdio.h>
# include "sudoku.h"
extern int sudoku[size][size];
extern int Arr[size][size];
int i, j, n;
int BruteForceAlgorithm (void)
{
int val;
for (i=0; i<size; i++)
{
for (j=0; j<size; j++)
{
if (sudoku[i][j]==0)
{
for (n=1; n<nmax; n++)
{
val = check (i,j,n);
if ( val == 1)
{
sudoku[i][j]=n;
// output();
break;
}
else if ( val == 0 && n == nmax-1 )
get_back();
}
}
}
}
}
int get_back (void)
{
int p,q;
int flag=0;
for ( p=i; p>=0; p-- )
{
for (q=j; q>=0; q-- )
{
flag=0;
if ( Arr[p][q]==0 && !( p==i && q==j) )
{
if ( sudoku[p][q]== nmax-1 )
sudoku[p][q]=0;
else
{
n = sudoku[p][q];
sudoku[p][q]=0;
i = p; j = q;
flag = 1;
break;
}
}
}
if ( flag == 1)
break;
}
}
Code description:
Sudoku.h has definitions related to sudoku solver.
1. size = 9 nmax = 10
2. check(i,j,n) returns 1 if a number "n" can be placed at (i,j) or else "0".
What does this code do ?
The code starts iterating from sudoku[0][0] to the end... if it finds a empty cell ( we take cell having "0" ), it starts checking for n=1 to n=9 which can be put in that.. as soon as a number can be put in that which is checked by check() it assigns it and breaks from loop and starts finding another empty cell.
In case for a particular cell if it doesn't find "n" which can be assigned to sudoku cell.. it goes back to the previous empty cell and start iterating from where it stopped and assigns the next value and continues, Here comes the function get_back(). it iterates back..
