C 数独求解器通过回溯陷入困境

Question

我正在尝试使用回溯在 C 中编写数独求解器，但它在某些时候陷入困境。所有其他功能都运行良好，所以我似乎找不到问题。该函数应该使用下一个数字作为参数来调用自身。返回值之一有效，无效时返回零。这反过来又应该触发回溯。它应该像这样工作，直到没有更多的行为止。

输入:

5 3 X X 7 X X X X
6 X X 1 9 5 X X X
X 9 8 X X X X 6 X
8 X X X 6 X X X 3
4××8×3××1
7 X X X 2 X X X 6
X 6 X X X X 2 8 X
X X X 4 1 9 X X 5
X X X X 8 X X 7 9

预期输出:

5 3 4 | 6 7 8 | 6 7 8 9 1 2
6 7 2 | 1 9 5 | 1 9 5 3 4 8
1 9 8 | 1 9 8 3 4 2 | 3 4 2 5 6 7
- - - - - - - - - -
8 5 9 | 8 5 9 7 6 1 | 7 6 1 4 2 3
4 2 6 | 8 5 3 | 8 5 3 7 9 1
7 1 3 | 7 1 3 9 2 4 | 9 2 4 8 5 6
- - - - - - - - - -
9 6 1 | 9 6 1 5 3 7 | 5 3 7 2 8 4
2 8 7 | 2 8 7 4 1 9 | 4 1 9 6 3 5
3 4 5 | 3 4 5 2 8 6 | 1 7 9

我最终得到的是:

5 3 1 | 2 7 6 | 4 9 8
6 2 4 | 6 2 4 1 9 5 | 1 9 5 7 3 0
0 9 8 | 0 0 0 | 0 0 0 0 6 0
- - - - - - - - - -
8 0 0 | 8 0 0 0 6 0 | 0 6 0 0 0 3
4 0 0 | 4 0 0 8 0 3 | 8 0 3 0 0 1
7 0 0 | 7 0 0 0 2 0 | 0 2 0 0 0 6
- - - - - - - - - -
0 6 0 | 0 6 0 0 0 0 | 0 0 0 2 8 0
0 0 0 | 0 0 0 4 1 9 | 4 1 9 0 0 5
0 0 0 | 0 0 0 0 8 0 | 0 7 9

这是回溯函数:

int solve(slot sudoku[9][9],int line, int column){
    int num=1;  
    while(sudoku[line][column].fix==1){
        column++;
    }
    if(line==9){
        return 1;
    }
    for(num=1;num<10;num++){
        if(Valid(line,column,num)){
            sudoku[line][column].value=num;
            if(column<8){
                if(solve(sudoku,line,column+1)){
                    return 1;
                }
            }
            else if(column==8){
                if(solve(sudoku,line+1,0)){
                    return 1;
                }
            }
        }
    }
    return 0;


}

这就是我定义“slot”结构的方式。它的目的是“固定”谜题的原始值，这样它就不会覆盖它们。它的工作原理是将“0”分配给可以由函数更改的插槽，并将“1”分配给保持固定的插槽。

typedef struct slot{
    int value;
    int fix;
}slot;

如果有人能帮我找到问题，我将不胜感激。

Answer 1

当列溢出数组大小时，在此循环中或循环后您会做什么？

  while(sudoku[line][column].fix==1)
  {
        column++;
  }

当列溢出时，函数的其余部分将使用该值，并将其作为参数传递给 Valid() 等。

如果数字是固定的，您是否应该将其视为有效解决方案并返回 0？

我在您的函数中没有看到任何将 sudoku->value 设置为零的代码。

[edit] 但是当列溢出时，你的函数返回 0，而没有找到解决方案。我们看到的零是未初始化的值。