学好算法，你就可以轻轻松松解数独啦

用户3147702

发布于 2022-06-27 14:38:48

7340

发布于 2022-06-27 14:38:48

文章被收录于专栏：小脑斧科技博客

1. 计算机五大经典算法

在计算机领域，有五大基本的经典算法，分别是：

分治
动态规划
贪心
回溯
分支限界

关于分治、动态规划与贪心算法，我们此前已经做过不少介绍

本文我们就来介绍五大经典算法的下一个 — 回溯算法。

2. 回溯算法

数学课堂上，老师说：“同学们，6 可以拆分成几加几呀？”，台下的同学们鸦雀无声，顿时有些冷场，老师一下子有点生气“掰着指头算不会吗？”

这个“掰着指头算”就是一个数字一个数字的尝试，通过穷举获得问题的结果集，对于复杂的有限空间的问题，通过穷举的方法是最容易想到且十分有效的。可以想象，走迷宫方式就是经典的“穷举”，沿着一个方向走，到达一个交叉点时，先选择一条路，当无路可走时，就退回上一个交叉点，选择接下来的一条路，这个方法就是典型的“回溯算法”，寻找迷宫出口的路，就是搜索路径，而交叉口就是“回溯点”。由于回溯算法的通用性，他又有着“通用解题方法”的美称。

3. 回溯算法的基本思想与一般步骤

通过上面迷宫的例子，我们可以看出来，所谓的回溯算法实际上就是沿着图的深度优先搜索的策略进行遍历，从一个节点到达另一个节点，而在每个节点，都需要一个方法来判断当前是否是有效结果，这个判断函数就是“剪枝函数”也叫“约束函数”。回溯算法的一般步骤就是：

将问题空间转化为树或图
确定搜索规则与剪枝函数
通过深度优先策略遍历树或图，通过剪枝函数避免无效搜索
回溯完成获得结果集

4. 回溯法的经典问题

相比于其他经典算法，回溯算法最大的优势就在于其通用性，只要能够把问题限制在有限空间内，并且构造树或图结构存储解题节点进行遍历，就可以利用回溯法快速解决问题。因此，有很多经典的问题可以利用回溯法来解决：

八皇后问题 — 如何在国际象棋棋盘的 8*8 个格子里放下八个皇后，并且让他们相互不攻击到
0-1背包问题 — 给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 pi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？
图的着色问题
解迷宫问题
解数独问题

5. 利用递推回溯法解决数独问题

数独是一个经典的益智类游戏，在 99 的 81 个格子中填充数字，让每一行、每一列、每 33 的小格子内都不出现重复的数字，它诞生于 19 世纪的法国，至今仍然风靡世界。作为一个有限空间的图问题，我们用回溯的方法可以轻松解决数独问题。

5.1. 构造问题空间

数独作为一个图问题，已经为我们省去了将问题转化为图的抽象过程，对于问题空间，我们可以通过一个 char ** 类型的二维数组来保存。有数字的地方填充相应的数字，空格的地方填充 ’.’，从而构造数独游戏的棋盘空间。

char board[9][9] = {
    {'5','3','.','.','7','.','.','.','.'},
    {'6','.','.','1','9','5','.','.','.'},
    {'.','9','8','.','.','.','.','6','.'},
    {'8','.','.','.','6','.','.','.','3'},
    {'4','.','.','8','.','3','.','.','1'},
    {'7','.','.','.','2','.','.','.','6'},
    {'.','6','.','.','.','.','2','8','.'},
    {'.','.','.','4','1','9','.','.','5'},
    {'.','.','.','.','8','.','.','7','9'}
};

5.2. 剪枝函数

根据数独游戏的限制条件，我们必须保证每次填充的数字在行、列还有 3*3 的小方格内是唯一的。

int checkSudokuPosition(char board[9][9], int i, int j, char k) {
    for (int v = 0; v < 9; ++v) {
        if (board[i][v] == k || board[v][j] == k || board[i/3*3 + v/3][j/3*3 + v%3] == k)
            return 0;
    }
    return 1;
}

剪枝函数通过传入棋盘空间、待检查位置的横坐标、纵坐标以及待填充数字来判断待填充数字是否可行。根据游戏规则，我们遍历待填充位置所在列的每一个元素，即 board[i][v] 以及待填充位置所在行的每一个元素，即 board[v][j] 来判断待填充数字是否已存在。那么，如何来找寻待填充位置所在的 33 小格呢？我们首先通过 i/33, j/33 找到 33 小格子左上角的起始坐标，然后通过 v/3, v%3，构造出 (0, 0)、(0, 1)、(0, 2)、(1, 0)、(1, 1)、(1, 2)、(2, 0)、(2, 1)、(2, 2) 的相对坐标，从而实现对 3*3 小格中每个数字的遍历。

5.3. 递推函数

我们通过一个栈来记录已遍历的问题节点，从而方便回溯。每当找到一个新的可行解，即将可行解所在横纵坐标压栈，并继续寻找下一个问题节点的可行解。当当前节点无法找到可行解，即出栈并回溯到上一节点，继续寻找上一节点的下一个可行解。最终有两种可能：

寻找到可行解 — 完成整个数独游戏棋盘的填充就说明已经找到了游戏的可行解
无解 — 当所有元素都已经出栈且无法找到初始节点的可行解，就说明当前这个数独游戏是无解的

下面就是我们的递推函数，通过返回 0 或 1，说明数独无解或已经找到可行解：

typedef struct {
    int i;
    int j;
} SudokuPosition;

int solveSudoku(char board[9][9]) {
    SudokuPosition **stack = malloc(sizeof(int) * 9 * 9);
    int stackSize = 0;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                char k = '1';
label:
                for (/* none */; k <= '9'; ++k) {
                    if (checkSudokuPosition(board, i, j, k) == 1) {
                        SudokuPosition *position = malloc(sizeof(SudokuPosition));
                        position->i = i;
                        position->j = j;
                        stack[stackSize] = position;
                        stackSize++;
                        board[i][j] = k;
                        break;
                    }
                }
                if (k >= '9' + 1) {
                    if (stackSize == 0) {
                        return 0;
                    }
                    SudokuPosition *position = stack[stackSize - 1];
                    i = position->i;
                    j = position->j;
                    k = board[i][j] + 1;
                    board[i][j] = '.';
                    free(position);
                    stackSize--;
                    goto label;
                }
            }
        }
    }
    return 1;
}

运行程序，输出了：

The solution of this sudoku is: 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9

6. 通过递归回溯法解数独

递推的方式非常便于理解，但是，既然我们通过栈空间来进行问题节点的记录，我们是否可以通过函数递归天然提供给我们的栈空间来实现问题的解决呢？当然是可以的，递归正是回溯法最常采用的方式。

6.1. 中止条件

每个空格就是数独问题的问题节点，当我们找到一个空格时，填充当前最小的可行解，然后递归到下一个问题节点。当无法找到可行解时，返回无解，上一层递归继续寻找下一个可行解。直到全部递归完成或最外层函数无法找到可行解，就标志着数独的解完成了获取或者这个数独无解。

6.2. 递归函数

int solveSudoku(char board[9][9], int p) {
    for (/*none*/; p < 81; ++p) {
        if (board[p/9][p%9] == '.') {
            for (k = '1'; k <= '9'; ++k) {
                if (checkSudokuPosition(board, p/9, p%9, k) == 1) {
                    board[p/9][p%9] = k;
                    int res = solveSudoku(board, p + 1);
                    if (res == 1) {
                        return 1;
                    }
                 }
            }
            board[p/9][p%9] = '.';
            return 0;
        }
    }
    return 1;
}

在这个函数中，我们传入 char ** 的棋盘空间，和初始搜索位置 p，通过 p/9, p%9 获取 p 所对应的横纵坐标。通过遍历，到达为 ’.’ 的问题节点时，就尝试填充 ’1’ 到 ’9’ 来让剪枝函数校验，校验通过则继续递归到下一节点。如果当前有可行解则返回 1，没有则返回 0。

7. 附录 — 本文完整代码

8.1. Makefile

CFLAGS = -Wall -g
main: main.c function/function.o
    ${CC} ${CFLAGS} -o $@ $^
clean: 
    rm -f main main.o function/function.o

8.2. 递推法

8.2.1. function/function.h

#ifndef _FUNCTION_BACKTRAKING_20200531_
#define _FUNCTION_BACKTRAKING_20200531_

typedef struct {
    int i;
    int j;
} SudokuPosition;

int checkSudokuPosition(char board[9][9], int i, int j, char k);
int solveSudoku(char board[9][9]);

#endif

8.2.2. function/function.c

#include <malloc.h>
#include "function.h"

int checkSudokuPosition(char board[9][9], int i, int j, char k) {
    for (int v = 0; v < 9; ++v) {
        if (board[i][v] == k || board[v][j] == k || board[i/3*3 + v/3][j/3*3 + v%3] == k)
            return 0;
    }
    return 1;
}

int solveSudoku(char board[9][9]) {
    SudokuPosition **stack = malloc(sizeof(int) * 9 * 9);
    int stackSize = 0;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                char k = '1';
label:
                for (/* none */; k <= '9'; ++k) {
                    if (checkSudokuPosition(board, i, j, k) == 1) {
                        SudokuPosition *position = malloc(sizeof(SudokuPosition));
                        position->i = i;
                        position->j = j;
                        stack[stackSize] = position;
                        stackSize++;
                        board[i][j] = k;
                        break;
                    }
                }
                if (k >= '9' + 1) {
                    if (stackSize == 0) {
                        return 0;
                    }
                    SudokuPosition *position = stack[stackSize - 1];
                    i = position->i;
                    j = position->j;
                    k = board[i][j] + 1;
                    board[i][j] = '.';
                    free(position);
                    stackSize--;
                    goto label;
                }
            }
        }
    }
    return 1;
}

8.2.3. main.c

#include <stdio.h>
#include "function/function.h"

int main() {
    char board[9][9] = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    int res = solveSudoku(board);
    if (res == 0) {
        printf("This sudoku is no way to solve.\n");
        return 0;
    }
    printf("The solution of this sudoku is:\n");
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
    return 0;
}

8.3. 递归法

8.3.1. function/function.h

#ifndef _FUNCTION_RECURSIVE_20200531_
#define _FUNCTION_RECURSIVE_20200531_

int checkSudokuPosition(char board[9][9], int i, int j, char k);
int solveSudoku(char board[9][9], int p);

#endif

8.3.2. function/function.c

#include "function.h"

int checkSudokuPosition(char board[9][9], int i, int j, char k) {
    for (int v = 0; v < 9; ++v) {
        if (board[i][v] == k || board[v][j] == k || board[i/3*3 + v/3][j/3*3 + v%3] == k)
            return 0;
    }
    return 1;
}

int solveSudoku(char board[9][9], int p) {
    for (/*none*/; p < 81; ++p) {
        if (board[p/9][p%9] == '.') {
            for (k = '1'; k <= '9'; ++k) {
                if (checkSudokuPosition(board, p/9, p%9, k) == 1) {
                    board[p/9][p%9] = k;
                    int res = solveSudoku(board, p + 1);
                    if (res == 1) {
                        return 1;
                    }
                 }
            }
            board[p/9][p%9] = '.';
            return 0;
        }
    }
    return 1;
}

8.3.3. main.c

#include <stdio.h>
#include "function/function.h"

int main() {
    char board[9][9] = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };
    int res = solveSudoku(board, 0);
    if (res == 0) {
        printf("This sudoku is no way to solve.\n");
        return 0;
    }
    printf("The solution of this sudoku is:\n");
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-06-01，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

游戏

本文分享自小脑斧科技博客微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

游戏

登录后参与评论

0 条评论

热度