c - C 中的数独解算器无法正常工作

Question

我用 C 语言编写了这个数独解算器。但它无法正常工作，有什么帮助吗？

使用示例输入，例如

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

它给出输出

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

知道出了什么问题吗？

#include<stdio.h>

int sudoku[9][9];

int check(int sudoku[][9], int row, int col, int sol)
{
    //checking in the grid
    int row_grid = (row/3) * 3;
    int col_grid = (col/3) * 3;

    int i, j;
    for(i=0; i<9; ++i)
    {
        if (sudoku[row][i] == sol)                             
            return 0;
        if (sudoku[i][col] == sol)                             
            return 0;
        if (sudoku[row_grid + (i%3)][col_grid + (i/3)] == sol) 
            return 0;
    }
    return 1;
}  


int main(void)
{
    int i,j,k;
    printf("enter the sudoku and enter 0 for unknown entries \n");
    for(i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            scanf("%d",&sudoku[i][j]);
        }
    }    
    for(i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            if(sudoku[i][j]==0)
            {
                for (k=1;k<=9;k++)
                {
                    if(check(sudoku,i,j,k)==1)
                    {
                        sudoku[i][j] = k;                   
                    }
                }               
            }
        }
    }

    printf("solved sudoku \n");
    for(i=0;i<9;i++)
    {
        for (j=0;j<9;j++)
        {
            printf("%d ", sudoku[i][j]);
        }
        printf("\n");       
    }
    return 0;
}

Answer 1

你不会用这种方式解决数独。您只需循环遍历所有单元格，并为每个空单元格选择可能存在的最大值。显然，这是不正确的，因为一个单元格中可能存在多个变体。而且您总是选择最大的(因为 for (k=...) 循环中没有 break)。有时您选择了错误的数字，这会导致数独不一致。

更新:您所做的不是蛮力，因为您没有迭代所有可能的解决方案。而不是

if(check(sudoku,i,j,k)==1)
{
    sudoku[i][j] = k;                   
}

一定有类似的东西

if(check(sudoku,i,j,k)==1)
{
    tempSudoku = copy(sudoku); //pseudocode
    tempSudoku[i][j] = k;
    tryToSolveRecursively(tempSudoku);              
}

如果 check() 返回 0，则存在不一致(对于某些空单元格，我们无法找到单个可能的解决方案)。因此，我们应该放弃这个解决方案，返回并尝试其他方法(递归万岁:))。这不是唯一的选择，但我只是希望它能为您指明正确的方向。

附注仅基于基本数独规则的强力解决方案将非常慢。相信我。您需要额外的启发式方法来减少搜索空间。