C中的数独求解器无法正常工作

我已经用C编写了这个数独求解器，但它不能正常工作，有什么帮助吗？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; 
}

来源

2013-11-28 goromlagche

您是否试图自己调试代码？ – alex

是的，找不到线索。这就是为什么我在这里发布 – goromlagche

显示你的意图，逻辑和你期望的输出。 – moeCake

你不打算用这种方式解决数独。您只需循环遍历所有单元格，并为每个空单元格选择可以在那里存在的最大值。显然，这是不正确的，因为在一个单元中可能有几个变体。你总是选择最大的（因为在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);    
}

如果检查（）返回0，则有一个不一致（对于某些空白单元格，我们无法找到一个可能的解决方案）。所以我们应该放弃这个解决方案，回去尝试一些其他的东西（viva la recursion :)）。这不是唯一的选择，但我只是希望它会指出你在一个正确的方向。

P.S.仅基于数独规则的蛮力解决方案将是极其缓慢。相信我。您需要额外的启发式方法来减少搜索空间。

来源

2013-11-28 06:47:36 FreeNickname

感谢男人，任何更好的方式来做到这一点，以摆脱不一致？ – goromlagche

@goromlagche，我更新了一个答案。不幸的是，我无法提供关于解决数独的链接，因为我拥有的所有链接都是在俄罗斯:)但我想你可以谷歌几种技术。 – FreeNickname

不客气:)我希望它会帮助:) – FreeNickname

C中的数独求解器无法正常工作

回答

相关问题