数独求解程序

今晚上帮同学写了个求解数独的小程序，发出来记录下。

标准数独是9*9的，规则是行、列、每个小九宫都填入不重复的19，我们可以把这个经典游戏扩展到N阶，行和列的规则不变，可以加入对角线限制，即对角线也需要唯一的填入1N。对于N为完全平方的情况，可以加入分块，即类似经典数独那样，每一个小块也要唯一的填入1~N。

程序逻辑很简单，就是基本的回溯算法，和N皇后问题基本完全一样，下面给出求解程序的核心框架：

void Solve() {
    int i = 0, j = -1;
    if (!FindNextBlank(i, j))
        return;

    while (true) {
        Number[i][j]++;
        // Recall
        if (Number[i][j] > order) {
            // Clear this positon first
            Number[i][j] = 0;
            if (!FindPreviousBlank(i, j)) {
                // Stop
                return;
            }
            continue;
        }

        if (!CheckValid(i, j))
            continue;

        // Valid!!

        // Found a solution
        if (!FindNextBlank(i, j)) {
            NofSolutions++;
            if (printSolution) {
                PrintSudoku();
            }
            
            // Find next solution
            i = order - 1, j = order;
            FindPreviousBlank(i, j);
        }
        // else find next blank positon
    }
}

CheckValid()是与规则有关的判断填入数字合法性的函数，FindNextBlank()和FindPreviousBlank()两个函数用于寻找下一个及上一个空位置，参数使用引用的方式传递，返回结果直接修改了传入值。

程序中先从第一个空位置开始，依次尝试所有取值，找到一个合法值后，开始填下一个空位置；若达到最后一个空位置，则说明找到了一个解，输出后继续循环；若当前位置尝试完所有取值后，依然没有合法值，说明之前填的有误，需要回溯，清除当前位置的值后会退到上一个空位置继续循环即可。

完整的程序代码见GitHub。

---

参考资料：
SudokuPuzzle
总共有多少个数独？