前向检测+启发式(约束满足问题) LeetCode37. Sudoku Solver

约束满足问题

约束满足问题简称CSP问题(Constraint Satisfaction Problem)。
CSP问题表示一组具有约束条件的变量集。它可以定义为一个三元组<V, D, C>,其中，V表示变量的集合，D表示各个变量域的集合，C表示约束条件的集合。
局部状态是对一些变量的一个赋值，目标状态则是对所有变量的一个赋值。求解CSP问题就是给定局部状态求解目标状态。

前向检测解决CSP问题

前向检测是一种深度优先搜索策略，它是回溯法的一种扩展。它采用了“向前看”的策略，即对一个变量进行赋值时，修改约束条件下相关变量的值域。其过程如下：
1. 选择一个变量。
2. 遍历变量值域。
3. 根据变量的赋值，调整相关变量的值域空间。若不会导致DWO(Domain Wipe Out)则往下递归。
4. 若有解则结束。否则恢复相关变量的值域空间，并回到步骤2。
5. 该局部状态无解
（对于步骤1选择变量，可使用启发式搜索优化。如MRV启发式，优先选择值域空间小的变量。）

LeetCode37. Sudoku Solver

数独问题可以抽象为一个CSP问题。每个格子代表一个变量；变量的值域都是1~9；约束条件是同行同列同九宫格不可有相同取值。
使用前向检测+MRV启发式搜索求解。

思路

启发式搜索指每次选择取值范围最小的那个格子。前向检测则是每填一个格子，就调整其他格子的取值范围。以此过程递归回溯即可。

核心步骤

1. 取值域最小的格子
2. 保存当前状态(值域)
3. 遍历格子的值域
4. 对格子进行赋值，并修改相关变量值域。
5. 递归搜索，有解返回。无解恢复状态。回到第三步
6. 无解返回。

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


// 格子0~8 * 0~8, 取值1~9
class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            init(board);
            solve(board);
        }

        bool solve(vector<vector<char>>& board)
        {
            // 取一个格子
            pair<int, int> cell = selectCell(board);
            if (cell.first == -1 && cell.second == -1) return true;
            if (domain[cell.first][cell.second][0] == 0) return false;

            // 保存当前状态, 主要是domain 
            int temp_domain[9][9][10];
            memcpy(temp_domain, domain, sizeof(domain));

            // 遍历格子的domain
            for (int num = 1; num <= 9; num++)
                if (domain[cell.first][cell.second][num] == 1)
                {
                    // 对cell赋值num, 修改相关domain和board
                    setCell(cell.first, cell.second, num, board);
                    if (solve(board) == true) return true;

                    // 恢复状态, 主要是domain
                    memcpy(domain, temp_domain, sizeof(domain));
                }

            // 这个board无解
            board[cell.first][cell.second] = '.';
            return false;
        }

    private:
        int domain[9][9][10];               // [i][j][0]表示可以填的数字个数，[i][j][k]表示是否可以填k
        // 根据board初始化domain
        void init(vector<vector<char>>& board)
        {
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                {
                    domain[i][j][0] = 9;
                    for (int k = 1; k <= 9; k++)
                        domain[i][j][k] = 1;
                }
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    if (board[i][j] != '.')
                        setCell(i, j, board[i][j]-'0', board);
        }
        // 将格子(i, j)设置为num
        void setCell(int i, int j, int num, vector<vector<char>>& board)
        {
            board[i][j] = num+'0';
            int ii = (i/3) * 3, jj = (j/3) * 3;
            for (int k = 0; k < 9; k++)
            {
                domain[i][k][0] -= domain[i][k][num];
                domain[i][k][num] = 0;
                domain[k][j][0] -= domain[k][j][num];
                domain[k][j][num] = 0;
                domain[ii+(k/3)][jj+(k%3)][0] -= domain[ii+(k/3)][jj+(k%3)][num];
                domain[ii+(k/3)][jj+(k%3)][num] = 0;
            }
        }
        // 选择domain最小的一个格子
        pair<int, int> selectCell(vector<vector<char>>& board)
        {
            int row = -1, col = -1, choice = 10;
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    if (board[i][j] == '.' && domain[i][j][0] < choice)
                    {
                        row = i;
                        col = j;
                        choice = domain[i][j][0];
                    }
            return {row, col};
        }
};