4x4 Sudoku解算器性能

Question

该代码用于4x4 Sudoku解算器。当有少量未填充的空间( 0's )时，它工作得很好，但是当我将整个矩阵输入为0‘S左右时，求解者需要很长的时间。我需要它只给出第一个有效的输出，不需要计算其余的输出。

我输入一个从0到4的矩阵。如果它们是从1到4，那么它们是预先填充的，它们不能被更改。但是如果值为0，那么我们可以将任何值从1修改为4，这样一旦有效地填充了Sudoku，我们就得到输出，否则程序就会打印"No“。

矩阵A包含输入。矩阵B包含1's或0's，如果该值在矩阵B中的位置x和y为0，则表示该值不是预先填充的。

#include<stdio.h>
#include<stdlib.h>

void printd(int A[4][4])
{
  int i,j;
  for(i=0;i<4;i++)
  {
    for(j=0;j<4;j++)
    {
      printf("%d", A[i][j]);
    }
    printf("\n");
  }
  printf("\n");
  return;
}

int check(int A[4][4])
{
    int i,j,k,a,b,c,state=1,temp=1;
        for(i=0;i<4;i++)
        {
          for(j=0;j<4;j++)
          {
            if(A[i][j]==0)
              temp=2;
          }
        }
        if(temp==1)
        {
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            for(a=0;a<4;a++)
            {
                if(a!=i && A[i][j]==A[a][j])
                    state=0;
                if(a!=j && A[i][j]==A[i][a])
                    state=0;
                if(i<2 && j<2)
                {
                    for(b=0;b<2;b++)
                    {
                        for(c=0;c<2;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
                else if(i<2 && j<4)
                {
                    for(b=0;b<2;b++)
                    {
                        for(c=2;c<4;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
                else if(i<4 && j<2)
                {
                    for(b=2;b<4;b++)
                    {
                        for(c=0;c<2;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
                else if(i<4 && j<4)
                {
                    for(b=2;b<4;b++)
                    {
                        for(c=2;c<4;c++)
                        {
                            if((b!=i || c!=j) && A[i][j]==A[b][c])
                                state=0;
                        }
                    }
                }
            }
        }
    }
    return state;
        }
        return 0;
}

int fill(int A[4][4],int B[4][4],int x,int y)
{
    int val,i,j,a,b,p;
    int C[4][4];
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            C[i][j]=A[i][j];
        }
    }
        val=check(A);
    if(val==1)
    {
        printf("Yes");
                printd(A);
        exit(0);
    }
    /*else if(val==0 && x==3 && y==3)
    {
        printf("N6o");
        return;
    }*/
    else if(x<4)
    {
                if(B[x][y]==0)
                {
                    for(p=1;p<5;p++)
                    {
                        C[x][y]=p;
                                                //printd(C);
                        //printf("%d %d %d\n", C[0][0], C[0][1], C[0][2]);
                        if(y<3)
                            fill(C,B,x,y+1);
                        else if(x<4)
                            fill(C,B,x+1,0);
                    }
                }
                                else
                                {
                                        if(y<3)
                                          fill(C,B,x,y+1);
                                        else if(x<4)
                                          fill(C,B,x+1,0);
                                }
    }
}

int main()
{
    int n,i,j,k,a,b,c,d;
    int A[4][4];
    int B[4][4]={0};
        //printd(B);
    scanf("%d", &n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d", &A[i][j]);
            if(A[i][j]!=0)
            {
                B[i][j]=1;      
            }
        }
    }
    fill(A,B,0,0);
    printf("No");
    return 0;
}

Answer 1

格式是混乱的：

• 许多出乎意料的缩进块和线条。通过清楚地识别嵌套代码块，很好地使用缩进来提高可读性。
• 在变量列表和参数列表中的逗号后面放置空格，例如：
  • 而不是int n,i,j,k,a,b,c,d更喜欢int n, i, j, k, a, b, c, d
  • 而不是fill(A,B,0,0)更喜欢fill(A, B, 0, 0)

• 在操作符周围放置一个空格，例如：
  • 而不是for(i=0;i<n;i++)更喜欢for(i = 0; i < n; i++)
  • 而不是if(A[i][j]!=0)更喜欢if (A[i][j] != 0)

在这个代码中，数字4是神奇的。到处都是。如果您将实现扩展到5x5矩阵或其他矩阵，则必须在任何地方替换它。最好为此定义一个宏，例如：

#define DIM 4

当然，当前实现中的一些函数不能与任何其他矩阵一起工作。在这些函数中，保留数字4，以提醒您应该改进实现以支持任意维度。在其他可以处理任何矩阵的函数中，例如main和fill，用DIM替换数字4。

Answer 2

，...but，当我把整个矩阵输入为0's时，求解者需要很长的时间。

这是因为您的代码非常残酷，您只需尝试每一种可能性，始终检查所有插槽并继续循环，即使您已经知道解决方案是错误的：

for(i=0;i<4;i++)
{
    for(j=0;j<4;j++)
    {
        if(A[i][j]==0)
            temp=2;
    }
}

上面的循环显然可以在if中终止：

for(i=0;i<4;i++)
{
    for(j=0;j<4;j++)
    {
        if(A[i][j]==0)
        {
            temp=2;
            goto not_filled;
        }
    }
}
not_filled:

与state类似的优化机会：

for(i=0;i<4;i++)
{
    for(j=0;j<4;j++)
    {
        for(a=0;a<4;a++)
        {
            if(a!=i && A[i][j]==A[a][j])
                state=0;

看起来，只要更改state=0，就可以终止循环。goto不错，使用它;) (break不能终止所有嵌套循环，goto可以)

但这才刚刚开始，试想一下算法，还能改进吗？首先检查填充的槽(连同所有子行和子列)如何？试着找出你所做的所有不必要的计算，并消除它(以加速它)。