从语法到算法：一起来解9×9数独

前言

本文适用于：

程序设计语言初学者
闲得没事想看的神犇

欢迎神犇批评指正。

C++语言程序设计第一学期的课程已经结束了。语法上的东西讲得并不多，只是到指针而已，但是缺乏必要的练习显然是没有效果的——尤其是对于实验课上的一些毒瘤题，确实令人手足无措。

今天我们就通过一个经典的数独问题来介绍回溯搜索，把学到的语法知识转化为算法。

什么是数独

数字 (すうじ) は独身 (どくしん) に限 (かぎ) る。

┌───────┬───────┬───────┐
│ 2 6 3 │ 4 1 8 │ 5 7 9 │
│ 7 8 4 │ 3 5 9 │ 6 2 1 │
│ 9 5 1 │ 6 7 2 │ 4 8 3 │
├───────┼───────┼───────┤
│ 3 9 2 │ 1 4 6 │ 8 5 7 │
│ 6 4 5 │ 8 9 7 │ 3 1 2 │
│ 8 1 7 │ 2 3 5 │ 9 6 4 │
├───────┼───────┼───────┤
│ 5 3 8 │ 7 2 4 │ 1 9 6 │
│ 1 7 9 │ 5 6 3 │ 2 4 8 │
│ 4 2 6 │ 9 8 1 │ 7 3 5 │
└───────┴───────┴───────┘

上图是一个9×9方阵。在这个方阵里，每一行、每一列中都有1~9，每一个3×3的小方阵中也含有不重复的1~9。将这个方阵里面的部分数字挖去，就得到了一个谜题。

为了便于编写程序求解，我们规定被挖去的数字由0表示。那么由上面方阵挖去部分数字而得到的一个数独可能是这样的：

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

接下来我们就一起来编程解决这个问题。

一起来想想解法

从人的角度来思考如何解一个数独，和设计一个通用的算法相比来说还是不大一样的。针对不同的数独题面我们解决时可以使用不同的方法，然而设计一个算法就不能这样了。我们现在以最朴素的角度来思考这个问题。

很容易可以想到这样的方法：

从整个方阵中从上至下、从左至右地找到一个尚未填上的数。
将这个位置从1一直填到9，并检查是否满足数独的规则。
若满足规则，就将这个位置填为符合条件的数，并继续从步骤1开始填下一个数。

是时候开始写一点代码了

一、找到一个未被填上的数

这很简单对吧，直接找就行了：

int x = y = -1;
for(int i = 1; i <= 9; ++i)
for(int j = 1; j <= 9; ++j)
    if(g[i][j] == 0)
    {
        x = i, y = j;
        break;
    }

这是大家都能够动手就写得出的代码。我们可以考虑将这一个功能写成函数，那么，采用什么方式把找到的位置返回，或者说是保存起来呢？方法是多样的。有许多编程语言可以便利地采用元组（tuple）返回多个值，C++11中也引入了std::tuple，这是一种方法。当然，也可以定义一个结构，然后通过它达到同样的目的。如果想练练指针，也可以直接在调用函数前声明两个变量，然后传地址进去，比如：

void GetABlank(int *x, int *y)
{
    *x = *y = -1;
    for(int i = 1; i <= 9; ++i)
    for(int j = 1; j <= 9; ++j)
        if(g[i][j] == 0)
        {
            *x = i, *y = j;
            break;
        }
}

写得更C++一点的话，我们可以扔掉指针，改为引用：

void GetABlank(int &x, int &y)
{
    x = y = -1;
    for(int i = 1; i <= 9; ++i)
    for(int j = 1; j <= 9; ++j)
        if(g[i][j] == 0)
        {
            x = i, y = j;
            break;
        }
}

这样看起来好像更简单一点了呢。等等，函数调用是有开销的呀，为了这么简单的功能写个函数是不是太慢了？那就加个inline内联一下吧。嗯，在clang-800.0.42.1编译器下跑出来的结果显示确实内联成功了。

二、给定当前点的位置和值，判断是否满足行、列的要求

这比刚才的问题更简单了：

inline bool CheckRow(int x, int value)
{
    for(int i = 1; i <= 9; ++i)
        if(g[x][i] == value)
            return false;
    return true;
}
inline bool CheckCol(int y, int value)
{
    for(int i = 1; i <= 9; ++i)
        if(g[i][y] == value)
            return false;
    return true;
}

三、给定当前点的位置和值，判断在3×3方阵中是否没有出现过

好像稍微复杂一点了，不过这种小问题肯定难不倒大家。我们设当前位置坐标为$(i,j)$，利用整数除法（向下取整）通过算术方法就能够算出这个方阵行、列的起止位置。0~8表示起来貌似比1~9要稍微简单一点：

$$
\begin{aligned}
x_{\mathrm{min}} &= \left \lfloor i \div 3 \right \rfloor \times 3 \\
x_{\mathrm{max}} &= \left ( \left \lfloor i \div 3 \right \rfloor + 1 \right ) \times 3 - 1 \\
y_{\mathrm{min}} &= \left \lfloor j \div 3 \right \rfloor \times 3 \\
y_{\mathrm{max}} &= \left ( \left \lfloor j \div 3 \right \rfloor + 1 \right ) \times 3 - 1
\end{aligned}
$$

由于我们之前一直是使用1~9表示，上面的方法就不行了，不过稍作修改即可。将范围算出来以后，写个循环判断一下就好：

inline bool CheckSmall(int x, int y, int value)
{
    int xs = (x - 1) / 3 * 3 + 1;
    int xt = ((x - 1) / 3 + 1) * 3;
    int ys = (y - 1) / 3 * 3 + 1;
    int yt = ((y - 1) / 3 + 1) * 3;
    for(int i = xs; i <= xt; ++i)
    for(int j = ys; j <= yt; ++j)
        if(g[i][j] == value)
            return false;
    return true;
}

将检查行、列和宫整合到一起：

inline bool CheckAll(int x, int y, int value)
{
    return CheckRow(x, value) 
        && CheckCol(y, value) 
        && CheckSmall(x, y, value);
}

好像有哪里不对？

让我们回到刚刚想到的方法：

从整个方阵中从上至下、从左至右地找到一个尚未填上的数。

将这个位置从1一直填到9，并检查是否满足数独的规则。

若满足规则，就将这个位置填为符合条件的数，并继续从步骤1开始填下一个数。

这样是不是不一定能算出答案？嗯……这个程序写出来应该是有很大几率算不出结果的。你应该知道为什么——我们没有考虑到每一个位置可能填上的所有数字，而只是贪心地填上当前满足条件的数字，所以之后的其他空格就不一定有数可填了。我们稍微修改一下上面的方法，并将它命名为填一个空：

从整个方阵中从上至下、从左至右地找到一个尚未填上的数。
将这个位置从1一直填到9，并检查是否满足数独的规则。
若满足规则，就将这个位置填为符合条件的数，并填一个空；若不满足规则，到第4步。
回到第2步直到9也填过为止。

代码写出来大概是这样：

void FillABlank(void)
{
    int i, j;
    GetABlank(i, j);
    for(int k = 1; k <= 9; ++k)
    {
        if(CheckAll(i, j, k))
        {
            g[i][j] = k;
            FillABlank();
        }
    }
}

那么问题来了，这个递归过程没有终止，这肯定是不行的。相信你已经想到了，刚才我们在实现GetABlank的时候就已经考虑了这一点，如果没有可以继续填的地方，i和j是为$-1$的。判断一下就可以知道这个数独有没有完成了。这样还不够。所谓回溯，即是要“回到原来的状态”，现在还没有体现出来。要实现这一点，我们得想办法判断当前状态往下继续填是否能填好，因此需要返回一个bool才行。这样一来，这个函数能做的事情已经不是“填一个空”这么简单，我们通过修改能使它完全解决数独问题，不如把它的名字改为“解题”。

这一步变更是真正的关键，我们大概可以把代码写成这样：

bool Solve(void)
{
    int i, j;
    GetABlank(i, j);
    if(i == -1 && j == -1)
        return true;
    for(int k = 1; k <= 9; ++k)
    {
        if(CheckAll(i, j, k))
        {
            g[i][j] = k;
            if(!Solve())
                g[i][j] = 0;
            else
                return true;
        }
    }
    return false;
}

这样一来，只需要调用Solve就可以求解数独，并且通过判断它的返回值可以知道给定的数独是否有解。

输出上的小技巧

OI的题目大多对于行末空格、文末换行没有要求，都是一并过滤的；ICPC则不同，行末多余空格会被视作Presentation Error，这就使人非常恼火。其实，在学习了数组之后，我们可以使用一些小技巧来快速便捷地写出输出符合没有行末空格要求答案的代码。

for(int i = 1; i <= 9; ++i)
for(int j = 1; j <= 9; ++j)
    std::cout << g[i][j] << " \n"[j == 9];

怎么样，应该已经恍然大悟了吧！将" \n"这个字符串字面量视作const char[3]操作，表达式j == 9在j不为9时为true，为9时为false，隐式类型转换成为1或0就可以作为const char[3]的下标（subscript）了。

课后练习

编写程序求解9×9数独（参考答案）。
思考：不使用递归函数如何解决这个问题？从函数调用的原理上考虑并编程实现。
思考：如何制造一个9×9数独谜题生成器？结合所学内容及随机数相关函数编程实现。
(*)附加题：自行了解DanceLink算法。

Catalog