我的数独在 c 中生成代码有什么问题？

Question

这是我的作业，制作数独游戏。我已经完成了我的算法，但它正在进入无限循环。我不明白为什么。

我正在尝试创建一个随机数并控制它以找到真实数字。检查所有列和行以找到与我们的随机数相同的数字，如果是，它正在更改测试编号，如果测试已更改，则尝试找到另一个数字作为真实数字。简单的数独逻辑。

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

int main() {
  srand(time(NULL));
  int num, col, row, row2, col2, test = 0;
  int sudo[9][9] = {{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}};

  for (row = 0; row <= 8; row++) {
    for (col = 0; col <= 8; col++) {
      do {
        test = 0;
        num = rand() % 9 + 1;
        //control
        for (col2 = 0; col2 <= 8; col2++) {
          if (num == sudo[col2][row]) {
            test++;
          }
        }
        for (row2 = 0; row2 <= 8; row2++) {
          if (num == sudo[col][row2]) {
            test++;
          }
        }
      } while (test > 0);
      sudo[col][row] = num;
    }
  }
//print
  for (row = 0; row <= 8; row++) {
    for (col = 0; col <= 8; col++) {
      printf(" %d ", sudo[col][row]);
      if (col == 2 || col == 5) {
        printf(" | ");
      }
    }
    if (row == 2 || row == 5) {
      printf("\n---------------------------------");
    }
    printf("\n");
  }
}

Answer 1

你的算法坏了，我可以证明原因。如果可以用这种方式填写数独谜题，那么用这种方式解决数独谜题也是微不足道的，但事实并非如此。

基本上您的代码归结为以下内容。我已经在内部 for 循环中添加了早期退出，以便在我们找到当前行或列中已有的数字后停止搜索（并且实际上理解了世界上 99.9% 的人对 "rows" 和 "columns" 在 NxN 矩阵中）：

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

#define NSIZE 9

void print_matrix(int const ar[][NSIZE])
{
    for (size_t i=0; i<NSIZE; ++i)
    {
        for (size_t j=0; j<NSIZE; ++j)
        {
            fputc('0' + ar[i][j], stdout);
            fputc(' ', stdout);
        }
        fputc('\n', stdout);
    }
}

int main()
{
    srand((unsigned)time(NULL));
    int sudo[NSIZE][NSIZE] = {{0}};
    int row, col;

    for(row=0;row<NSIZE;++row)
    {
        for(col=0;col<NSIZE;++col)
        {
            int row2 = 0, col2 = 0, num;
            printf("Trying ");
            do
            {
                num = rand()%9+1;
                printf("%d ", num);
                for(row2=0; row2<NSIZE && num!=sudo[row2][col]; ++row2);
                for(col2=0; col2<NSIZE && num!=sudo[row][col2]; ++col2);
            }
            while (row2 < NSIZE || col2 < NSIZE);
            fputc('\n', stdout);

            sudo[row][col] = num;
            printf("sudo[%d][%d] = %d\n", row, col, num);
            print_matrix(sudo);
        }
    }
}

随着循环的进行，我们会报告我们正在尝试的数字，以及放置守门员后矩阵的样子。例如，上面的测试运行最初可能如下所示：

Trying 8 
sudo[0][0] = 8
8 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 1 
sudo[0][1] = 1
8 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 9 
sudo[0][2] = 9
8 1 9 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 6 
sudo[0][3] = 6
8 1 9 6 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 3 
sudo[0][4] = 3
8 1 9 6 3 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 4 
sudo[0][5] = 4
8 1 9 6 3 4 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 4 6 7 
sudo[0][6] = 7
8 1 9 6 3 4 7 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
Trying 1 3 1 3 4 1 3 8 4 9 3 8 1 4 7 9 3 8 8 8 4 9 6 5 
sudo[0][7] = 5
8 1 9 6 3 4 7 5 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0

这可能会持续一段时间。但最终，除非你非常幸运，否则一定会发生以下情况（在轮子掉下来之前这个已经很深了）：

Trying 1 6 3 4 
sudo[6][6] = 4
8 1 9 6 3 4 7 5 2 
1 3 5 4 8 6 2 7 9 
3 6 4 8 7 9 5 2 1 
7 9 1 2 4 5 3 8 6 
4 7 3 9 2 8 6 1 5 
5 4 2 3 6 1 8 9 7 
6 8 7 1 9 3 4 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0

请注意，我们将尝试填充 sudo[6][7]。为此，我们必须找到一个既不在 sudo[r][7] 列中也不在 sudo[6][c] 行中的数字。但是看看已经在这些位置上的数字。

sudo[r][7] : {5,7,2,8,1,9}
sudo[6][c] : {6,8,7,1,9,3,4}

因此我们正在寻找 1..9 中不在 {1,2,3,4,5,6,7,8,9} 中的数字，我们永远不会找到它。

算法坏了。回溯被用于这样的任务是有原因的。

我的数独在 c 中生成代码有什么问题？

What is wrong with my sudoku generate code in c?

c

sudoku