在 C 中使用反向跟踪算法解决数独问题

Question

十月初的时候我就有了用C编程解数独的感觉，很快我就知道这不是一件容易的事。目前，我确实编写了代码来完成所有功能，但似乎某处存在错误，导致无法打印甚至评估所需结果。

我使用here提供的算法作为参考来开发我的代码，

这是我编写的代码，如有错误，将不胜感激

#include <stdio.h>

int row(int i,int j,int a[9][9]);
int column(int i,int j,int a[9][9]);  //function declaration's
int grid(int i,int j,int a[9][9]);


int main()
{
    int a[9][9];
    int i,j,x;
    for (i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            a[i][j]=0;/*for making all the array values = 0*/
            /*So that the stored garbage values will be removed*/

        }
    }
    /*Entering known elements*/
    printf("Enter the elements of known elements leaving the unknown as 0\n");
    for (i=0;i<9;i++)
    {
        for(j=0;j<9;j++)
        {
            scanf("%d",&a[i][j]);
        }

    }

    //If a given grid is '0', lets assign a value 1 and if 1 exists in the same row or column or in ints correspond 3x3 box, increment the value upto 9

    i=0,j=0,x=1;
incr:
    if ( a[i][j] == 0)
    {
        a[i][j] = x;
        if( row(i,j,a) && column(i,j,a) && grid(i,j,a) )
        {
            a[i][j] = x;
        }
        else
        {
            x++;
            if ( x>9)
                x = 1;
        }
    }
    else
    {
        while(i < 9)
        {
            i++;
            goto incr;
        }
        if (i == 9)
        {
            i =1;
            j++;
            goto incr;
        }
        if (j == 9)
        {
            for(i=0;i<9;i++)
            {
                for(j=0;j<9;j++)
                {
                    printf("%d ",a[i][j]);
                }
                printf("\n");
            }
        }
    }

}

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

int column(int i,int j, int a[9][9])
{
    int m;
    printf("%d%d",i,j);
    for(m=0;m<9;m++)
    {
        if ( m != i)
        {
            if(a[i][j] == a[m][j])
            {
                return 0;
            }
        }
    }
    return 1;
}

int grid(int i,int j, int a[9][9])
{
    int m,n;

    if( i>=0 && i<=2 && j>=0 && j<=2) /* grid 1*/
    {
        for(m=0;m<=2;m++)
        {
            for(n=0;n<=2;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=0 && i<=2 && j>=3 && j<=5) /* grid 2*/
    {
        for(m=0;m<=2;m++)
        {
            for(n=3;n<=5;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=0 && i<=2 && j>=6 && j<=8) /* grid 3*/
    {
        for(m=0;m<=2;m++)
        {
            for(n=6;n<=8;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=3 && i<=5 && j>=0 && j<=2) /* grid 4*/
    {
        for(m=3;m<=5;m++)
        {
            for(n=0;n<=2;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=3 && i<=5 && j>=3 && j<=5) /* grid 5*/
    {
        for(m=3;m<=5;m++)
        {
            for(n=3;n<=5;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=3 && i<=5 && j>=6 && j<=8) /* grid 6*/
    {
        for(m=3;m<=5;m++)
        {
            for(n=6;n<=8;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=6 && i<=8 && j>=0 && j<=2) /* grid 7*/
    {
        for(m=6;m<=8;m++)
        {
            for(n=0;n<=2;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=6 && i<=8 && j>=3 && j<=5) /* grid 8*/
    {
        for(m=6;m<=8;m++)
        {
            for(n=3;n<=5;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    if( i>=6 && i<=8 && j>=6 && j<=8) /* grid 9*/
    {
        for(m=6;m<=8;m++)
        {
            for(n=6;n<=8;n++)
            {
                if(i != m && j != n)
                {
                    if(a[i][j] == a[m][n])
                    {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    return 0;
}

Answer 1

您的程序在矩阵中插入一个值后退出。在第 41 行设置位置值后：a[i][j] = x;，您需要相应地增加 i 或 j 然后调用 goto incr;.

PS.: 学习使用简单的 printf() 语句，它们是很好的调试器。

在 C 中使用反向跟踪算法解决数独问题

Solve Sudoku using Back tracking Algorithm in C

c

algorithm

sudoku