код решает 9 * 9 sudoku.works для среднего уровня, но дает ошибку сегментации для сложных из-за чрезмерной рекурсии .. где проблема

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

Answer 1

Вы, скорее всего, разорили стек. Всего пара замечаний: вам нужно упростить код, разделив работу на отдельные функции. Возможно, вам удавалось отслеживать все в этой маленькой программе, но если вы продолжите писать код, вам придется подумать о макете / дизайне / удобстве использования кода.

Чтобы решать головоломки судоку без переполнения стека, я предлагаю изучить решение с помощью решателей ограничений. Вот кое-что, с чего можно начать .

Answer 2

вероятно, макс рекурсивный вызов.