code solves 9*9 sudoku.works for medium level but gives segmentation fault for hard ones due to excessive recursion..where's the problem

Question

# include <stdio.h>

int check(int a,int b);
int check1(int a,int b,int c,int d);
void recursive(int x,int pos[82]);
void scaledown(int pos[82]);

int pos[82];
int q=1; 
long c=0;
int ch[10]={0,1,2,3,4,5,6,7,8,9};
int ar[10][10]=        {{0,0,0,0,0,0,0,0,0,0},
        {0,8,6,0,0,2,0,0,0,0},
        {0,0,0,0,7,0,0,0,5,9},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,6,0,8,0,0},
        {0,0,4,0,0,0,0,0,0,0},
        {0,0,0,5,3,0,0,0,0,7},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,2,0,0,0,0,6,0,0},
        {0,0,0,7,5,0,9,0,0,0}};
int size;

void main()
{
int i,j,k=1,a;
int pos[82];
printf("WELCOME TO THE ULTIMATE SUDOKU SOLVER");
printf("\n\n\n");
for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
            {
                if(ar[i][j]==0)
                    {
                        pos[k]=(10*i)+j;
                        k+=1;
                    }
                printf("%d",ar[i][j]);
                printf(" ");
            }
        printf("\n");
    }
size=k-1;
printf("\n");
scaledown(pos);
k=1;
for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
            {
                if(ar[i][j]==0)
                    {
                        pos[k]=(10*i)+j;
                        k+=1;
                    }
            }
    }
size=k-1;
recursive(q,pos);
for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
            {
                printf("%d",ar[i][j]);
                printf(" ");
            }
        printf("\n");
    }
printf("%d",c);
}

void recursive(int x,int p[82])
{
c++;
printf("%d",c);
printf("\n");   
ar[p[x]/10][p[x]%10]+=1;
if(ar[p[x]/10][p[x]%10]>9&&q<=size)
    {
        ar[p[x]/10][p[x]%10]=0;
        q--;
        recursive(q,p);
    }
if(check(p[x]/10,p[x]%10)==1&&q<size)
    {
        q++;            
        recursive(q,p);
    }
if(check(p[x]/10,p[x]%10)==0&&ar[p[x]/10][p[x]%10]<9&&q<=size)
    {
        recursive(q,p);
    }
if(ar[p[x]/10][p[x]%10]==9&&check(p[x]/10,p[x]%10)==0&&q<=size)
    {
        ar[p[x]/10][p[x]%10]=0;
        q--;
        recursive(q,p);
    }
if(q==size&&check(p[x]/10,p[x]%10)==1){}
}

int check1(int a,int b,int c,int d)
{
int i,j;
for(i=c;i<=(c+2);i++)
    {
        for(j=d;j<=(d+2);j++)
            {
                if(i==a&&j==b){}
                else
                    {
                        if(ar[i][j]==ar[a][b])
                            {
                                return 0;
                            }
                    }
            }
    }
return 1;
}

int check(int a,int b)
{
int i,j;
for(i=1;i<=9;i++)
    {
        if(i!=b)
            {
                if(ar[a][i]==ar[a][b])
                    {
                        return 0;
                    }
            }
        if(i!=a)
            {
                if(ar[i][b]==ar[a][b])
                    {
                        return 0;
                    }
            }
    }

if(a<4&&b<4)
    {
        if(check1(a,b,1,1)==0)
            {
                return 0;
            }
    }

if(a<4&&b>3&&b<7)
    {
        if(check1(a,b,1,4)==0)
            {
                return 0;
            }
    }

if(a<4&&b>6)
    {
        if(check1(a,b,1,7)==0)
            {
                return 0;
            }
    }

if(a>3&&a<7&&b<4)
    {
        if(check1(a,b,4,1)==0)
            {
                return 0;
            }
    }

if(a>3&&a<7&&b>3&&b<7)
    {
        if(check1(a,b,4,4)==0)
            {
                return 0;
            }
    }

if(a>3&&a<7&&b>6)
    {
        if(check1(a,b,4,7)==0)
            {
                return 0;
            }
    }

if(a>6&&b<4)
    {
        if(check1(a,b,7,1)==0)
            {
                return 0;
            }
    }

if(a>6&&b>3&&b<7)
    {
        if(check1(a,b,7,4)==0)
            {
                return 0;
            }
    }

if(a>6&&b>6)
    {
        if(check1(a,b,7,7)==0)
            {
                return 0;
            }
    }

return 1;
}

void scaledown(int p[82])
{
int i,j,w,count=0;
for(i=1;i<=size;i++)
    {
        for(j=1;j<=9;j++)
            {
                ar[p[i]/10][p[i]%10]=ch[j];
                if(check(p[i]/10,p[i]%10)==0)
                    {
                        ch[j]=0;
                        count+=1;
                    }
            }
        if(count==8)
            {
                for(w=1;w<=9;w++)
                    {
                        if(ch[w]!=0)
                            {
                                ar[p[i]/10][p[i]%10]=ch[w];
                            }
                    }
            }
        else
            {
                ar[p[i]/10][p[i]%10]=0;
            }
        for(w=1;w<=9;w++)
            {
                ch[w]=w;
            }
        count=0;
    }
}

See http://stackoverflow.com/questions/204476/what-should-main-return-in-c-c — Francesco, Jun 23 '11 at 06:37

score 1 · Accepted Answer · answered Jun 22 '11 at 05:31

1

probably, max recursively call.

answered Jun 22 '11 at 05:31

mattn

7,571
30
54

i also think the same but how can i lessen the number of calls more the level is hard greater will be the call – atul jha Jun 22 '11 at 05:51
the program stops after approximately 327400 odd call's – atul jha Jun 22 '11 at 05:52
No you can't. You have better to think way without recursive calls. – mattn Jun 22 '11 at 05:54
hmm other than this brute force algorithm – atul jha Jun 22 '11 at 11:14

score 1 · Answer 2 · answered Jun 22 '11 at 13:07

1

You most likely busted the stack. Just a couple unrelated notes: You need to make your code simpler by separating the work into individual functions. You may have been able to keep track of everything in this small program, but if you continue to write code you will have to think about code layout/design/usability.

To solve sudoku puzzles without overflowing the stack, I suggest looking into the solution using constraint solvers. Here's something to get you started.

answered Jun 22 '11 at 13:07

pg1989

1,010
6
13

Ok got it.Brute force algorithm is not so elegant. – atul jha Jun 23 '11 at 06:27
Well, that's not always true. It's important to think about the tradeoff between speed and code complexity, especially when writing something that could be computation-intensive. Sometimes the brute force solution truly is the best way to go about solving a problem, because the alternative is you having to implement a complicated algorithm from scratch, which could take a big chunk of your time. – pg1989 Jun 23 '11 at 12:53

code solves 9*9 sudoku.works for medium level but gives segmentation fault for hard ones due to excessive recursion..where's the problem

2 Answers2