回溯法最经典问题-数独

摘要: 数独的状态空间树与回溯法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 回溯法的思想、设计与分析 中，我们系统了解了回溯法的思想。

我们知道要用回溯法解决问题，首先需要明确问题的解空间，构成解空间的向量可以表示为 $(x_{0}, x_{1}, \cdots, x_{n-1})$。解空间一般描述为树形结构，称为状态空间树。文章 回溯法三种常见的状态空间树：子集树、排列树、满m叉树 中，我们学习了三种常见的状态空间树。

显式约束规定了待求解问题的所有可能的候选解，这些候选解组成了问题实例的解空间。也就是说，显式约束决定了状态空间树。

隐式约束用于判定一个候选解是否为可行解。根据隐式约束，我们可以设计一个判定函数 $p(x_{0},x_{1},\cdots,x_{n-1})$，若该函数为真，则称候选解 $(x_{0},x_{1},\cdots,x_{n-1})$ 是问题的可行解。

本文我们以数独问题，来看一下回溯法解决实际问题的过程：明确显式约束、及其对应的解空间和状态空间树，明确判断可行解的隐式约束，寻找合适的剪枝策略。

---

36. 有效的数独 (判断是否可行)

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

示例 1：

输入：board =
[[“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”]]
输出：true

示例 2：
输入：board =
[[“8”,”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”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

算法：枚举

这是在回溯法求解数独过程中的一步判断，这里判断数独局面是否合法的若干条件，可以视为是回溯法求解数独过程中的隐式条件。

判断过程即枚举起盘的所有位置，若该位置有数字，则判断该数字在同行、同列、同块中是否出现过。

维护三个状态数组：row_state[i][j] 表示第 i 行是否出现数字 j；col_state 表示第 i 列是否出现数字 j，block_state 表示第 i 个块是否出现数字 j。

代码 (Python)

import numpy as np

def block_id(i, j):
    r = i // 3
    c = j // 3
    return 3 * r + c

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        col_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        block_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    num = int(board[i][j])
                    if row_state[i][num - 1]:
                        return False
                    row_state[i][num - 1] = True
                    if col_state[j][num - 1]:
                        return False
                    col_state[j][num - 1] = True
                    if block_state[block_id(i, j)][num - 1]:
                        return False
                    block_state[block_id(i, j)][num - 1] = True
        return True

代码 (C++)

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<bool> > row_state(9, vector<bool>(9, false));
        vector<vector<bool> > col_state(9, vector<bool>(9, false));
        vector<vector<bool> > block_state(9, vector<bool>(9, false));
        for(int i = 0; i < 9; ++i)
            for(int j = 0; j < 9; ++j)
            {
                if(board[i][j] != '.')
                {
                    if(!row_state[i][board[i][j] - '0' - 1])
                        row_state[i][board[i][j] - '0' - 1] = true;
                    else
                        return false;
                    if(!col_state[j][board[i][j] - '0' - 1])
                        col_state[j][board[i][j] - '0' - 1] = true;
                    else
                        return false;
                    if(!block_state[block_id(i, j)][board[i][j] - '0' - 1])
                        block_state[block_id(i, j)][board[i][j] - '0' - 1] = true;
                    else
                        return false;
                }
            }
        return true;
    }

private:
    int block_id(int i, int j)
    {
        int r = i / 3;
        int c = j / 3;
        return 3 * r + c;
    }
};

---

37. 解数独 (返回任一种可行解)

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解

示例 1：

输入：board = [[“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”,”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”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

算法：回溯

• 显式约束：每个位置有 9 种选择，一共有 81 个位置，状态空间树构成一个 81 层的满 9 叉树。
• 隐式约束：数字不能在同一行、同一列、同一块出现过。

代码 (python)

import numpy as np

def block_id(i, j):
    r = i // 3
    c = j // 3
    return 3 * r + c

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.row_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        self.col_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        self.block_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    num = int(board[i][j])
                    self.row_state[i][num - 1] = True
                    self.col_state[j][num - 1] = True
                    self.block_state[block_id(i, j)][num - 1] = True
        return self.dfs(board, 0, 0)

    def check(self, board, i, j, num):
        # 隐式约束
        if self.row_state[i][num - 1]:
            return False
        if self.col_state[j][num - 1]:
            return False
        if self.block_state[block_id(i, j)][num - 1]:
            return False
        return True

    def dfs(self, board, i, j):
        if i == 9:
            return True
        nxt_i = (i * 9 + j + 1) // 9
        nxt_j = (i * 9 + j + 1) % 9
        if board[i][j] != ".":
            return self.dfs(board, nxt_i, nxt_j)
        for num in range(1, 10):
            if not self.check(board, i, j, num):
                continue
            board[i][j] = str(num)
            self.row_state[i][num - 1] = True
            self.col_state[j][num - 1] = True
            self.block_state[block_id(i, j)][num - 1] = True
            if self.dfs(board, nxt_i, nxt_j):
                return True
            board[i][j] = "."
            self.row_state[i][num - 1] = False
            self.col_state[j][num - 1] = False
            self.block_state[block_id(i, j)][num - 1] = False
        return False

代码 (C++)

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        row_state = vector<vector<bool>>(9, vector<bool>(9, false));
        col_state = vector<vector<bool>>(9, vector<bool>(9, false));
        block_state = vector<vector<bool>>(9, vector<bool>(9, false));
        for(int i = 0; i < 9; ++i)
            for(int j = 0; j < 9; ++j)
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row_state[i][num - 1] = true;
                    col_state[j][num - 1] = true;
                    block_state[block_id(i, j)][num - 1] = true;
                }
        dfs(board, 0, 0);
    }

private:
    vector<vector<bool>> row_state;
    vector<vector<bool>> col_state;
    vector<vector<bool>> block_state;
    int block_id(int i, int j)
    {
        int r = i / 3;
        int c = j / 3;
        return 3 * r + c;
    }

    bool check(int i, int j, int num)
    {
        // 隐式约束
        if(row_state[i][num - 1])
            return false;
        if(col_state[j][num - 1])
            return false;
        if(block_state[block_id(i, j)][num - 1])
            return false;
        return true;
    }

    bool dfs(vector<vector<char>>& board, int i, int j)
    {
        if(i == 9)
            return true;
        int nxt_i = (i * 9 + j + 1 ) / 9;
        int nxt_j = (i * 9 + j + 1 ) % 9;
        if(board[i][j] != '.')
            return dfs(board, nxt_i, nxt_j);
        for(int num = 1; num <= 9; ++num)
        {
            if(!check(i, j, num))
                continue; 
            board[i][j] = '0' + num;
            row_state[i][num - 1] = true;
            col_state[j][num - 1] = true;
            block_state[block_id(i, j)][num - 1] = true;
            if(dfs(board, nxt_i, nxt_j))
                return true;
            board[i][j] = '.';
            row_state[i][num - 1] = false;
            col_state[j][num - 1] = false;
            block_state[block_id(i, j)][num - 1] = false;
        }
        return false;
    }
};

剪枝、搜索顺序

在构成状态空间的 81 层满 9 叉树中，不满足隐式约束的分支不会搜索到，因此隐式约束是一种可行性剪枝。

我们希望剪枝尽可能发生在浅层，这样就可以减少很多对无效状态的搜索。在选择下一个填写的位置时，之前是直接按从小到大顺序来。现在选择可填数字最少的坐标作为下一个要填数的位置。

代码 (C++)

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        row_state = vector<vector<bool>>(9, vector<bool>(9, false));
        col_state = vector<vector<bool>>(9, vector<bool>(9, false));
        block_state = vector<vector<bool>>(9, vector<bool>(9, false));
        for(int i = 0; i < 9; ++i)
            for(int j = 0; j < 9; ++j)
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    row_state[i][num - 1] = true;
                    col_state[j][num - 1] = true;
                    block_state[block_id(i, j)][num - 1] = true;
                }
        int nxt_i = -1, nxt_j = -1;
        get_nxt(board, nxt_i, nxt_j);
        dfs(board, nxt_i, nxt_j);
    }

private:
    vector<vector<bool>> row_state;
    vector<vector<bool>> col_state;
    vector<vector<bool>> block_state;
    vector<vector<vector<bool>>> used;

    void get_nxt(const vector<vector<char>>& board, int& nxt_i, int& nxt_j)
    {
        int min_choose = 10;
        for(int i = 0; i < 9; ++i)
            for(int j = 0; j < 9; ++j)
            {
                if(board[i][j] != '.')
                    continue;
                int used = 0;
                for(int num = 1; num <= 9; ++num)
                {
                    if(!check(i, j, num))
                        used |= (1 << (num - 1));
                }
                int choose = 9 - ones(used);
                if(choose < min_choose)
                {
                    min_choose = choose;
                    nxt_i = i;
                    nxt_j = j;
                }
            }
    }

    int ones(int x)
    {
        int ans = 0;
        while(x > 0)
        {
            if(x & 1)
                ++ans;
            x >>= 1;
        }
        return ans;
    }

    int block_id(int i, int j)
    {
        int r = i / 3;
        int c = j / 3;
        return 3 * r + c;
    }

    bool check(int i, int j, int num)
    {
        // 隐式约束
        if(row_state[i][num - 1])
            return false;
        if(col_state[j][num - 1])
            return false;
        if(block_state[block_id(i, j)][num - 1])
            return false;
        return true;
    }

    bool dfs(vector<vector<char>>& board, int i, int j)
    {
        if(i == -1)
            return true;
        for(int num = 1; num <= 9; ++num)
        {
            if(!check(i, j, num))
                continue; 
            board[i][j] = '0' + num;
            row_state[i][num - 1] = true;
            col_state[j][num - 1] = true;
            block_state[block_id(i, j)][num - 1] = true;
            int nxt_i = -1, nxt_j = -1;
            get_nxt(board, nxt_i, nxt_j);
            if(dfs(board, nxt_i, nxt_j))
                return true;
            board[i][j] = '.';
            row_state[i][num - 1] = false;
            col_state[j][num - 1] = false;
            block_state[block_id(i, j)][num - 1] = false;
        }
        return false;
    }
};

代码 (Python)

import numpy as np

def block_id(i, j):
    r = i // 3
    c = j // 3
    return 3 * r + c


def ones(x):
    ans = 0
    while x > 0:
        if (x & 1) == 1:
            ans += 1
        x >>= 1
    return ans


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.row_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        self.col_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        self.block_state = np.array([False] * 9 * 9, np.bool_).reshape(9, 9)
        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    num = int(board[i][j])
                    self.row_state[i][num - 1] = True
                    self.col_state[j][num - 1] = True
                    self.block_state[block_id(i, j)][num - 1] = True
        nxt_i, nxt_j = self.get_nxt(board)
        return self.dfs(board, nxt_i, nxt_j)

    def get_nxt(self, board):
        min_choose = 10
        nxt_i = nxt_j = -1
        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    continue
                used = 0
                for num in range(1, 10):
                    if not self.check(board, i, j, num):
                        used |= (1 << (num - 1))
                choose = 9 - ones(used)
                if choose < min_choose:
                    min_choose = choose
                    nxt_i = i
                    nxt_j = j
        return nxt_i, nxt_j

    def check(self, board, i, j, num):
        # 隐式约束
        if self.row_state[i][num - 1]:
            return False
        if self.col_state[j][num - 1]:
            return False
        if self.block_state[block_id(i, j)][num - 1]:
            return False
        return True

    def dfs(self, board, i, j):
        if i == -1:
            return True
        for num in range(1, 10):
            if not self.check(board, i, j, num):
                continue
            board[i][j] = str(num)
            self.row_state[i][num - 1] = True
            self.col_state[j][num - 1] = True
            self.block_state[block_id(i, j)][num - 1] = True
            nxt_i, nxt_j = self.get_nxt(board)
            if self.dfs(board, nxt_i, nxt_j):
                return True
            board[i][j] = "."
            self.row_state[i][num - 1] = False
            self.col_state[j][num - 1] = False
            self.block_state[block_id(i, j)][num - 1] = False
        return False

---