题解 | #Sudoku# 首个自己完成的困难级题目！

与HJ28 素数伴侣 <二向图的最大匹配个数>类似，此题可以分为找到每个空格的所有独立取值，为N个空格找到一组互斥的解两个部分<N分图的可行解>。

可行解与最大匹配不同，不需要遍历所有元素。

思路：

• 找出所有的空格。针对每个空格，得到其独立可能的取值（在行、列、宫中未出现）；
• 对N个空格，及其每个空格可能的取值，使用DFS+回溯的思想处理（找出可行解）：
• 每个顶点（空格）依次遍历其链表中的元素（取值）。
• 若该取值被使用过，且被使用的位置与当前位置冲突，则跳过当前链表元素，continue；
• 若该取值未被使用过，则将该取值保存至路径结果中，并继续下一个状态的dfs。边界条件如下：
• 遍历到最后一个顶点（空格）；
• 结果路径的个数 == 空格个数
• dfs(int k, vector<int> ori_fill, vector<pair<int, int>> ori_pre[10])

注意：

• 若当前值不满足，continue遍历下一个值。结果路径以及当前解使用数组，需要重置至原来的状态。

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

/*
给定一个包含空格的数独，根据已有的数据，推算出剩余的数字
每行、每列、每宫中的元素： 0 - 9

行、列、宫作为一个处理对象。
    当其中有一个0时，根据其他的值进行处理。
    若存在两个0，比如正方形的四角是0; 两行两列均不可解决。

思路：
（1）根据每行、每列、每宫，确定这个位置可能的填值，三者的并集。
（2）k个空，每个空存在一些可能的选值。即等价于k分图的最大匹配。
*/

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;


vector<vector<int>> sd;     // 保存输入的数独信息
vector<pair<int, int>> tofill;      // 保存每个空格的坐标(0, 0)。
vector<vector<int>> cand;           // 保存每个空格(如0_0)可以选择的数据  


vector<int> ans;
int ans_flag = 0;
int dfs_cnt = 0;

// N分图的最大匹配
// vector<pair<int, int>> pre[10];     // 保存空格填值为1-9时，对应的坐标。
bool dfs(int k, vector<int> ori_fill, vector<pair<int, int>> ori_pre[10]){
    // 遍历tofill[k]这个空格，其可以填充的数值，cand[0]
    int x;
    dfs_cnt ++;
    
    if (k >= cand.size()) return true;   // 当两个空格时，k最大遍历到1
    
    
    // 注意当回溯的时候，pre的记录值需要重置。因为i=0和i=1时候的pre值应该不同。
    vector<pair<int, int>> cur_pre[10];
    vector<int> cur_fill;
    for(int i = 0; i < cand[k].size(); i++){
        for (int i = 0; i < 10; i++) {
            cur_pre[i] = ori_pre[i]; // 逐个复制元素
        }
        cur_fill = ori_fill;
        // cur_pre = ori_pre;  // 选择链表中不同的元素时，需要重置前置记录
        x = cand[k][i];
        
        // 检查这里使用x，是否与其他的空格pre.排斥。 // printf("k:%d, i:%d, x:%d\n", k, i, x);
        
        int flag = 0;
        for(auto p : cur_pre[x]){
            int r1 = tofill[k].first, c1 = tofill[k].second;    // 检查当前空格与该数已经填补的空格，是否处于同一行、列、宫。
            int r2 = p.first, c2 = p.second;
            if(r1 == r2 || c1 == c2 || (c1 / 3 * 3 == c2 / 3 * 3 && r1 / 3 * 3 == r2 / 3 * 3)){
                flag = 1;
                // printf("k:%d, i:%d, x:%d, (r1, c1):(%d, %d), (r2, c2):(%d, %d)\n", k, i, x, r1, c1, r2, c2);
                break;  // 当前的x填放在这里会造成冲突。
            }
        }
        if(flag) continue;
        
        // 若不冲突。
        
        cur_pre[x].push_back(tofill[k]);    // 将当前的位置保存在值的索引中。
        cur_fill.push_back(x);    // 将当前值保存到结果中
        // printf("k:%d, i:%d, cand[k]_size:%d, x:%d, cur_fill_cnt:%d\n", k, i, cand[k].size(), x, cur_fill.size());
        
        if(cur_fill.size() == cand.size()){
            ans_flag = 1;   // 进行剪枝，
            ans = cur_fill;  // 保存最终的结果
            break;
        }
        // 因为只有找到一条路径即可；注意dfs(x_i+1)的利用方式
        if (dfs(k+1, cur_fill, cur_pre)){
            return true;   
        }
    }   
    if(ans_flag) return true;        // 当遍历到正确答案之后，结束dfs
    return false;
    
}


int main()
{
    
    string s;

    int row_fill = 0;
    while(getline(cin, s)){
        istringstream ss(s);    // istringstream可以当作标准输入cin使用
        
        vector<int> cur;
        int tmp;
        int col_fill = 0;
        while(ss >> tmp){
            cur.push_back(tmp);
            if(tmp == 0){
                tofill.push_back(make_pair(row_fill, col_fill));
            }
            col_fill ++;
        }
        sd.push_back(cur);
        row_fill ++;
    }
    
    // 对于每个空缺，保存其可以存放的数值
    // vector<int> cand[tofill.size()];    // 保存每个空格可以存放的数值
    
    for(int t = 0; t < tofill.size(); t++){
        vector<int> f(10, 0);   // 保存每行、每列、每宫中1-9的次数。次数为零的值，即该空缺可以填放的值。
        
        // 处理该行
        for(auto cur : sd[tofill[t].first]){
            if (cur != 0) f[cur]++;
        }
        
        // 处理该列
        for(int i = 0; i < sd.size(); i++){
            if(sd[i][tofill[t].second] != 0) f[sd[i][tofill[t].second]]++;
        }
        
        // 处理该宫
        int up = (tofill[t].first / 3) * 3;
        int left = (tofill[t].second / 3) * 3;  // 定位起始点
        for(int i = up; i < up + 3; i++){
            for(int j = left; j < left + 3; j++){
                if(sd[i][j] != 0) f[sd[i][j]]++;
            }
        }
        
        // 找到三个位置中，1-9之间累计值为0的值。
        vector<int> cur_cand;
        for(int i = 1; i < f.size(); i++){
            if(f[i] == 0) {
                cur_cand.push_back(i);
                // cout << tofill[t].first << " " << tofill[t].second << " " << i << endl; 
            }
        }
        cand.push_back(cur_cand);
    }
    
    
    // 打印空格的索引，以及空格可以存放的数值
    // int dfs_test = 1;
    // cout << tofill.size() << " " << cand.size() << endl;
    // for(int i = 0; i < tofill.size(); i++){
    //     cout << tofill[i].first << " " << tofill[i].second << ": ";
        
        
    //     // dfs_test *= cand[i].size();
    //     // cout << i << " " << cand[i].size() << " " << dfs_test << endl;
    //     for(auto c: cand[i]){
    //         cout << c << " ";
    //     }
    //     cout << endl;
    // }


    vector<int> cand_fill;    // 保存每个空格存放的元素
    vector<pair<int, int>> pre[10];     // 保存空格填值为1-9时，对应的坐标。
    // cout << "dfs" << endl;
    dfs(0, cand_fill, pre);
    
        // printf("估计的测试次数:%d\n", dfs_test); // 全部dfs是所有可能的乘积；
    // printf("估计的测试次数:%d\n", dfs_cnt); // 实际的dfs次数；
    
    // 打印出填补数据
    // printf("cand的大小:%d\n", cand.size());
    // printf("ans的大小:%d\n", ans.size());
    // for(auto a : ans){
    //     cout << a << " ";
    // }
    // cout << endl;
    
    // 将填补的元素放入空格中
    for(int i = 0; i < tofill.size(); i++){
        auto f = tofill[i];
        sd[f.first][f.second] = ans[i];
    }
    
    // 打印填补后的数组
    for(auto pair : sd){
        for(auto c : pair){
            cout << c << " ";
        }
        cout << endl;
    }
    
    
    
    
    return 0;
}