我有这段代码,所以我认为这是我在周末挑战赛中的第一次尝试。如果审核中包含有关如何改进算法的建议,但所有建议都是可以接受的,则我更愿意。

#include <stdio.h>

int isAvailable(int puzzle[][9], int row, int col, int num)
{
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;
    int i, j;

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

int fillSudoku(int puzzle[][9], int row, int col)
{
    int i;
    if(row<9 && col<9)
    {
        if(puzzle[row][col] != 0)
        {
            if((col+1)<9) return fillSudoku(puzzle, row, col+1);
            else if((row+1)<9) return fillSudoku(puzzle, row+1, 0);
            else return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if(isAvailable(puzzle, row, col, i+1))
                {
                    puzzle[row][col] = i+1;
                    if((col+1)<9)
                    {
                        if(fillSudoku(puzzle, row, col +1)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else if((row+1)<9)
                    {
                        if(fillSudoku(puzzle, row+1, 0)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else return 1;
                }
            }
        }
        return 0;
    }
    else return 1;
}

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

    if(fillSudoku(puzzle, 0, 0))
    {
        printf("\n+-----+-----+-----+\n");
        for(i=1; i<10; ++i)
        {
            for(j=1; j<10; ++j) printf("|%d", puzzle[i-1][j-1]);
            printf("|\n");
            if (i%3 == 0) printf("+-----+-----+-----+\n");
        }
    }
    else printf("\n\nNO SOLUTION\n\n");

    return 0;
}


测试运行: br />

#1 楼

您的解决方案简短而有趣。希望我的答案也可以,因为rolfl涵盖了我所看到的大部分内容。 :)


solveSudoku可能会更好地传达它正在解决难题的事实。 fillSudoku听起来像一个函数,用于从文件或字符串或其他内容填充初始位置。

您可以通过降低!= 0的最大C值来缩短“是否已填充单元格”检查: br />
if(puzzle[row][col])



您正在复制使fillSudoku中的单元格索引前进的代码:一次,如果该单元格已被填充,则在下一次猜测时再次出现。您可以删除后者,并只需传递相同的单元格索引,因为首先要设置单元格的值。

if(isAvailable(puzzle, row, col, i+1))
{
    puzzle[row][col] = i+1;

    if(fillSudoku(puzzle, row, col) return 1;
    else puzzle[row][col] = 0;
}




#2 楼

我很乐意浏览并发现此代码不能很好地完成的所有事情……但是,它简短,甜蜜并且可以正常工作,并且它本身在某种程度上说明了它的先进性。该解决方案在除CPU周期以外的所有资源上都是非常轻量级的,并且在堆栈上也不会占用太多资源。总而言之,它整洁且结构良好。

一些小小的批评:在您的isAvailable()方法中,您声明了j,但不要使用它。
用于检查块的奇特的模/除机制(puzzle[rowStart + (i%3)][colStart + (i/3)] == num)真是奇特...可能需要某种注释。我已经完成数学运算,可以看到它是正确的,但是那里的一些帮助还是有用的。避免重复而又不增加复杂性的好方法。根据我的计算,您要双重检查4个值,然后三重检查1个。这就是5/27个检查是多余的...但是,正如我所说,我认为避免这些检查会比冗余更昂贵。 >在您的isAvailable()方法中,您声明fillSudoku并将其用作i。由于在这种情况下,for(i=0; i<9; ++i)实际上不是某个数组的索引或简单的循环限制器,但实际上是一个拼图数字,因此您应该做两件事:

将其重命名为类似i

将循环更改为:digit,然后可以删除在循环内执行的所有冗余for(digit=1; digit<=9; ++digit)操作(例如+1