用回溯法求解Sudoku

Question

这是一个解决数独使用回溯。我怎样才能使它更加优化和干净？

#include <stdio.h>

int isAvailable(int sudoku[][9], int row, int col, int num)
{
    int i, j;
    for(i=0; i<9; ++i)
        if( (sudoku[row][i] == num) || ( sudoku[i][col] == num )  )//checking in row and col
            return 0;

     //checking in the grid
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;

    for(i=rowStart; i<(rowStart+3); ++i)
    {
        for(j=colStart; j<(colStart+3); ++j)
        {
            if( sudoku[i][j] == num )
                return 0;
        }
    }    

    return 1;
}    

int fillsudoku(int sudoku[][9], int row, int col)
{
    int i;
    if( row<9 && col<9 )
    {
        if( sudoku[row][col] != 0 )//pre filled 
        {
            if( (col+1)<9 )
                return fillsudoku(sudoku, row, col+1);
            else if( (row+1)<9 )
                return fillsudoku(sudoku, row+1, 0);
            else
                return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if( isAvailable(sudoku, row, col, i+1) )
                {
                    sudoku[row][col] = i+1;

                    if( (col+1)<9 )
                    {
                       if( fillsudoku(sudoku, row, col +1) )
                           return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else if( (row+1)<9 )
                    {
                        if( fillsudoku(sudoku, row+1, 0) )    
                            return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else
                        return 1;
                }
            }
        }
        return 0;
    }
    else
    {
        return 1;
    }
} 

int main()
{
   int i, j;
    int sudoku[9][9]={{3, 0, 6, 5, 0, 8, 4, 0, 0},
                      {5, 2, 0, 0, 0, 0, 0, 0, 0},
                      {0, 8, 7, 0, 0, 0, 0, 3, 1},
                      {0, 0, 3, 0, 1, 0, 0, 8, 0},
                      {9, 0, 0, 8, 6, 3, 0, 0, 5},
                      {0, 5, 0, 0, 9, 0, 6, 0, 0},
                      {1, 3, 0, 0, 0, 0, 2, 5, 0},
                      {0, 0, 0, 0, 0, 0, 0, 7, 4},
                      {0, 0, 5, 2, 0, 6, 3, 0, 0}};

    if( fillsudoku(sudoku, 0, 0) )
    {

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

    return 0;
}

Answer 1

非常好：

我很少会做一些小的改变。

在isAvailable()中，我将同时检查行/col/box。

int isAvailable(int sudoku[][9], int row, int col, int num)
{
    //checking in the grid
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;

    int i, j;
    for(i=0; i<9; ++i)
    {
        if (sudoku[row][i] == num)                             return 0;
        if (sudoku[i][col] == num)                             return 0;
        if (sudoku[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
    }

    return 1;
}    

这就引出了我的第一个评论：

我更喜欢在块引号中使用while/for/if的子状态。

if( sudoku[i][j] == num )
            return 0;

// I prefer this:
if( sudoku[i][j] == num )
{   return 0;
}

这样，就不可能意外地放置一个扩展且并非全部执行的宏。

移动到下一个方块的代码位于代码中的多个位置：

        if( (col+1)<9 )
           STUFF(row, col+1);
        else if( (row+1)<9 )
            STUFF(row+1, 0);
        else
            WIN

因为它是多个地方，你有冗余。我会把这张支票移到一个地方。最简单的方法是将它移到函数中的前几行代码中。然后，您总是进行类似于这个fillsudoku(sudoku, row, col+1)的递归调用。

int fillsudoku(int sudoku[][9], int row, int col)
{
    if (col >= 9)
    {
         col = 0;
         ++row;
         if (row >= 9)
         {
             return 1;
         }
    }

    // Original code.
    // When doing a recursive call use ` fillsudoku(sudoku, row, col+1)`
    // You know the start of the code will test it.

接下来，我将提前退出，而不是使用嵌套代码。

这是一个值得商榷的风格点，但我不认为必须向下滚动很长的方式来看到一个失败线有助于可读性。既然你已经提前退出了，那就不是问题了。

        if( sudoku[row][col] != 0) //pre filled 
        {
            return fillsudoku(sudoku, row, col+1);
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if( isAvailable(sudoku, row, col, i+1) )
                {
                    sudoku[row][col] = i+1;

                    int good = fillsudoku(sudoku, row, col +1);
                    if (good)
                    {   return 1;
                    }
                    sudoku[row][col] = 0;
                }
            }
        }
        return 0;
}