c - 理解这个 C 函数

Question

我试图理解这个函数是如何工作的，我研究了几种生成数独谜题的算法并找到了这个。

测试了该函数，它确实生成了一个有效的 9x9 拉丁方(数独)网格。 我的问题是我不明白这个函数是如何工作的，我知道这个结构是由整数、p 和 b 组成的，p 将保存表格中单元格的数字，但在那之后我不明白为什么它创建了更多数组(选项卡 1 和 tab2)以及它如何检查拉丁方 block =/等，总而言之，我完全迷路了。

我不是要求逐行解释此功能背后的一般概念。 会对我有很大帮助!

再次感谢<3

int sudoku(struct sudoku tabla[9][9],int x,int y)
{
int tab[9] = {1,1,1,1,1,1,1,1,1};
        int i,j;
  for(i=0;i<y;++i)
  {
        tab[tabla[x][i].p-1]=0; 

  for(i=0;i<x;++i)
  { 
        tab[tabla[i][y].p-1]=0;
  }
  for(i=(3*(x/3));i<(3*(x/3)+3);++i)
  { 
        for(j=(3*(y/3));j<y;++j)
        {
         tab[tabla[i][j].p-1]=0; 
        }
  }
    int n=0;
   for(i=0;i<9;++i)
   {
    n=n+tab[i];
   }

    int *tab2; 
    tab2=(int*)malloc(sizeof(int)*n);

    j=0; 
    for(i=0;i<9;++i)
    { if(tab[i]==1)
      {
       tab2[j]=i+1;
            j++;
      }
    }
    int ny, nx;
    if(x==8)
    {
        ny=y+1; 
        nx=0;   
    }
    else
    {
        ny=y; 
        nx=x+1;
    }

    while(n>0)
    {
        int los=rand()%n;
        tabla[x][y].p=tab2[los];

        tab2[los]=tab2[n-1]; 

        n--;

        if(x==8 && y==8)
        {
            return 1;
        }

        if (sudoku(tabla,nx,ny)==1)
        {
           return 1;
        } 

    }
    return 0;
}

编辑 太好了，我现在明白结构了，谢谢lijie的回答。我仍然不明白的是以随机顺序尝试值的部分)。我不明白它如何在不调用检查移动是否合法的代码部分的情况下检查随机值放置是否有效，另外，在放置随机数之后是否有必要再次检查网格是否有效？ –

Answer 1

基本上，函数的一次调用填充了 (x, y) 处和“之后”的位置。在表中tabla ，并且该函数假定位置“先于” (x, y)已填充，并返回值的合法“填充”是否可能。

通过先增加 x，然后增加 y，电路板被线性化。

函数的第一部分找出(x, y) 处的合法值。 ，第二部分以随机顺序尝试这些值，并尝试通过递归调用填充棋盘的其余部分。

tab2 实际上没有意义因为tab可以为此目的重复使用，并且该函数会泄漏内存(因为它永远不会是 free d，但除此之外，它仍然有效)。

这对你来说有意义吗？

编辑

检查合法数字部分中唯一棘手的区域是第三个循环(检查 3x3 框)。 j 的条件是j < y因为这些值在哪里 j == y已经被第二个循环检查过。

EDIT2

我挑剔，但重要的部分 n并填充 tab2具有合法的值(value)应该真的是

int n = 0;
for (i = 0; i < 9; ++i) if (tab[i]) tab[n++] = i+1;

因此省略了 tab2 的需要(后面的代码可以只使用 tab 和 n 而不是 tab2 )。从而消除了内存泄漏。

编辑

请注意，随机性仅适用于有效值(尝试值的顺序是随机的，而不是值本身)。

代码遵循标准的穷举搜索模式:尝试每个可能的候选值，如果搜索成功则立即返回，如果所有候选值都失败则返回失败。