4

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

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

我不是要求逐行解释，这个函数背后的一般概念。对我有很大帮助！

再次感谢<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;
}

编辑 太好了，我现在了解结构了，谢谢李杰的回答。我仍然不明白的是以随机顺序尝试值的部分）。我不明白它如何检查随机值放置是否有效而不调用检查移动是否合法的代码部分，此外，在放置随机数之后是否有必要再次检查网格是否有效？——</p>

4

3 回答 3

3

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

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

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

实际上没有意义，tab2因为tab可以为此目的重复使用，并且该函数会泄漏内存（因为它永远不会是freed，但除此之外，它还可以工作）。

你能理解这个吗？

编辑

检查合法数字的部分中唯一棘手的区域是第三个循环（选中 3x3 框）。的条件j是因为第二个循环已经检查了j < y那些值。j == y

编辑2

我挑剔，但计算n和填充tab2合法值的部分真的应该是

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

因此省略了tab2（后面的代码可以只使用tabandn而不是tab2）的需要。因此消除了内存泄漏。

编辑

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

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

于 2010-11-28T16:49:32.983 回答
1

尝试自己解决数独问题，您会发现在找到解决方案时存在固有的递归。所以，你有一个调用自己的函数，直到整个板子被解决。

至于代码，它可以大大简化，但如果您尝试自己编写一个，那将是最好的。

编辑：

这是来自 java 的一个，也许它与您尝试做的类似。

于 2010-11-28T16:40:25.227 回答
1

原则的快速描述 - 忽略您发布的示例。希望有了这个想法，您可以自己将其与示例联系起来。

基本方法是许多“人工智能”的基础，至少直到 80 年代末才看到。许多谜题的最通用解决方案基本上是尝试所有可能的解决方案。

因此，首先尝试左上角为 1 的所有可能解决方案，然后尝试左上角为 2 的所有可能解决方案，依此类推。您递归尝试第二个位置、第三个位置等选项。这被称为穷举搜索 - 或“蛮力”。

麻烦的是它几乎需要永远 - 但你可以缩短很多毫无意义的搜索。

例如，在左上角放置了一个 1，就递归了。您将 1 放在下一个位置并再次递归 - 但现在您检测到您违反了两条规则（连续两条，3x3 块中的两条），即使没有填写其余的棋盘。所以你“回溯” - 即退出递归到上一个级别并前进到将 2 放在第二个位置。

这避免了很多搜索，并使事情变得实用。如果您跟踪每行、列和块中仍未使用的数字，还有进一步的优化 - 考虑这些集合的交集。

我所描述的实际上是一种解决方案算法（如果您允许某些单元格已经被填充）。生成一个随机解决的数独是同样的事情，但是对于每个数字位置，您必须以随机顺序尝试数字。这也留下了决定哪些单元格留空的问题，同时确保仍然可以解决难题以及（更难）设计具有难度级别设置的难题。但在某种程度上，解决这些问题的基本方法已经在这里 - 您可以通过运行解决方案算法并查找您是否（以及有多少）解决方案来测试一组特定的左空格是否有效，例如，您可以设计搜索一组留空的有效单元格。

难度级别的事情是困难的，因为它取决于人类对难度的感知。嗯——我能不能再把“困难”放在某个地方……

一种方法 - 设计一种更复杂的搜索算法，该算法使用典型的人类经验法则而不是递归搜索，并将难度判断为所需的最深层次的递归。一些经验法则也可能被认为比其他规则更先进，因此使用它们更多地计算难度。显然难度是主观的，所以对于评分应该如何精确没有一个正确的答案。

这为您提供了一个特定难题的难度度量。直接设计一个难度级别的谜题会很困难 - 但是当尝试选择不同的单元格以留空时，您可以尝试多个选项，跟踪所有难度分数，最后选择最接近您的目标难度级别。

于 2010-11-28T17:36:27.277 回答