/*
 *
 * [37] 解数独
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution
{
    vector<vector<char>> board; //将键入数据存入类内全局中，在其他函数传递时可以少一个参数
    bool val[9][9][10];         //存储每个元素可能的值
    bool hadModified;           //判断一次slove是否已知晓该格的值，作为全局可减少调用函数时的参数个数
    bool only[10];              //存储一个元素的唯一值，该唯一值由所在行、列、九宫格可能的值排除而来
    struct Status               //用于表示当前状态的类型
    {
        vector<vector<char>> board;
        bool val[9][9][10];
        pair<int, int> coord; //尝试修改的地方的坐标
    };
    stack<Status> stu; //在一次枚举前记录当前状态

private:
    bool notFull() //判断整张表是否未填满（有空位）
    {
        for (int i = 0; i < board.size(); i++)
            if (find(board[i].begin(), board[i].end(), '.') != board[i].end())
                return 1;
        return 0;
    }

    inline pair<int, int> locate(const pair<int, int> &apair) //定位一个格子所在的九宫格的左上角的格子的坐标
    {
        return {apair.first / 3 * 3, apair.second / 3 * 3};
    }

private: //函数对象
    struct
    {
        void operator()(vector<char> &board)
        {
            for (int i = 0; i < board.size(); ++i)
                if (board[i] != '.')
                    board[i] -= '0';
        }
    } turnToNum; //将二维数组中的字符数翻译成数字，用于操作

    static struct
    {
        void operator()(vector<char> &board)
        {
            for (int i = 0; i < board.size(); ++i)
                if (board[i] != '.')
                    board[i] += '0';
        }
    } turnToChar; //将二维数组中的数字翻译回字符数，用于打印

private: //核心代码：解决(x,y)的值
    inline bool solve(const int x, const int y)
    {
        // 0是正常退出，1是异常退出

        //将要用到的工具声明并初始化
        bool valOri[10];                         //记录原始数据
        copy(val[x][y], val[x][y] + 10, valOri); //将原始数据备份
        size_t cnt;                              //记录(x,y)可能的值的个数

        // remove：检查(x,y)所在的行、列、九宫格，去掉不可能的val

        //检查行
        for (int i = 0; i < board.size(); i++)
        {
            if (board[x][i] != '.')
                val[x][y][board[x][i]] = 0;
        }
        cnt = count(val[x][y] + 1, val[x][y] + 10, 1);
        if (cnt == 1) //如果(x,y)只剩一个val，则结束
        {
            board[x][y] = find(val[x][y] + 1, val[x][y] + 10, 1) - val[x][y];
            hadModified = 1;
            return 0;
        }
        else if (cnt == 0) //如果(x,y)没有可能的val，则异常退出
            return 1;

        //检查列
        for (int i = 0; i < board.size(); i++)
        {
            if (board[i][y] != '.')
                val[x][y][board[i][y]] = 0;
        }
        cnt = count(val[x][y] + 1, val[x][y] + 10, 1);
        if (cnt == 1) //如果(x,y)只剩一个val，则结束
        {
            board[x][y] = find(val[x][y] + 1, val[x][y] + 10, 1) - val[x][y];
            hadModified = 1;
            return 0;
        }
        else if (cnt == 0) //如果(x,y)没有可能的val，则异常退出
            return 1;

        //检查九宫格
        const pair<int, int> gongGe = locate({x, y});
        for (int i = gongGe.first; i < gongGe.first + 3; i++)
        {
            for (int j = gongGe.second; j < gongGe.second + 3; j++)
            {
                if (board[i][j] != '.')
                    val[x][y][board[i][j]] = 0;
            }
        }
        cnt = count(val[x][y] + 1, val[x][y] + 10, 1);
        if (cnt == 1) //如果(x,y)只剩一个val，则结束
        {
            board[x][y] = find(val[x][y] + 1, val[x][y] + 10, 1) - val[x][y];
            hadModified = 1;
            return 0;
        }
        else if (cnt == 0) //如果(x,y)没有可能的val，则异常退出
            return 1;

        //如果与原始数据相比，可能的值发生了变化，说明虽然该函数此次没有计算出(x,y)的值，但是缩小了可能的值的范围，发挥了作用
        if (!equal(val[x][y], val[x][y] + sizeof(val[x][y]), valOri))
            hadModified = 1; //发挥作用置1

        return 0; //正常退出
    }

public: //唯一接口
    void solveSudoku(vector<vector<char>> &in)
    {
        //初始化操作
        board = in;                  //将键入数据in深拷贝到全局board中
        memset(val, 1, sizeof(val)); // fill_n作用于三维数组可能会编译出错

        //将字符转义为数字，便于后续操作
        for_each(board.begin(), board.end(), turnToNum);

        //核心循环
        while (notFull()) //直到把表填完
        {
        new_while:
            hadModified = 0; //一个新的while视为尚未修改，只要在整张表中有一个元素发生了值的修改或者可能的值的修改，就视为表发生了修改
            for (int i = 0; i < board.size(); i++)
                for (int j = 0; j < board[i].size(); j++)
                    if (board[i][j] == '.') //若(i,j)没有值，则尝试得到它的值
                    {
                        if (solve(i, j)) //解决(i,j)，如果(i,j)产生异常返回
                        {                //回退状态值
                            int x = stu.top().coord.first, y = stu.top().coord.second;
                            stu.top().val[x][y][board[x][y]] = 0; //(x,y)可能的值不是当前的值
                            board = stu.top().board;
                            for (int ii = 0; ii < 9; ii++) //无法直接在top中将数组出栈
                                for (int jj = 0; jj < 9; jj++)
                                    for (int kk = 0; kk < 10; kk++)
                                        val[ii][jj][kk] = stu.top().val[ii][jj][kk];
                            stu.pop();

                            if (count(val[x][y] + 1, val[x][y] + 10, 1) == 1) //如果在排除掉原先的val后如果(x,y)可能的值只剩一个
                            {
                                board[x][y] = find(val[x][y] + 1, val[x][y] + 10, 1) - val[x][y]; //(x,y)的值只能是这个唯一值
                                goto new_while;                                                   //不需要尝试新值，直接进入新的while
                            }
                            else
                                goto try_val; //重新尝试新值
                        }
                    }
                    else
                    { //(i,j)已有值，其可能的值只能是board[i][j]
                        fill_n(val[i][j], 10, 0);
                        val[i][j][board[i][j]] = 1;
                    }
            if (!hadModified) //若填充完一次表后，没有对表中的数据进行修改，说明此时只用排除法无法完成题目
            {
                //记录一次当前的状态
                stu.push({board}); //无法直接在push中将数组入栈
                for (int ii = 0; ii < 9; ii++)
                    for (int jj = 0; jj < 9; jj++)
                        for (int kk = 0; kk < 10; kk++)
                            stu.top().val[ii][jj][kk] = val[ii][jj][kk];

                //尝试可能的值
            try_val:
                for (size_t valNum = 2; valNum <= 9; valNum++) //从可能的值的个数最少的格子开始枚举（以保证出现回退的次数尽可能的少）
                {
                    for (int i = 0; i < board.size(); i++)
                    {
                        for (int j = 0; j < board[i].size(); j++)
                        {
                            if (board[i][j] == '.' && count(val[i][j] + 1, val[i][j] + 10, 1) == valNum) //如果(i,j)尚未填充且该位可能的值有valNUm个
                            {
                                stu.top().coord = {i, j};                                         //尝试修改的元素的坐标为(i,j)
                                board[i][j] = find(val[i][j] + 1, val[i][j] + 10, 1) - val[i][j]; //(i,j)是其中一个可能的值
                                fill_n(val[i][j], 10, 0);                                         //此时(i,j)可能的值只剩下board[i][j]
                                val[i][j][board[i][j]] = 1;                                       // board[i][j]的值即为(i,j)唯一可能的值

                                goto new_while;
                            }
                        } // for j
                    }     // for i
                }         // for valNUm
            }             // if hadn't modified
        }                 // while

        //将数字转义回字符，实现数据对接
        for_each(board.begin(), board.end(), turnToChar);
        in = board; //将答案深拷贝回原位置in中
    }
};
// @lc code=end

namespace tool
{
    struct
    {
        bool operator()(const char c)
        {
            return c != '.';
        }
    } notEmpty;

    void printSudoku(const vector<vector<char>> &board)
    {
        for (vector<char> vc : board)
        {
            for (char c : vc)
            {
                cout << c << " ";
            }
            cout << endl;
        }
    }

    int count_filled(const vector<vector<char>> &board)
    {
        int cnt = 0;
        for (vector<char> vc : board)
            cnt += count_if(vc.begin(), vc.end(), notEmpty);
        return cnt;
    }

    struct test
    {
        int a[3][3];
        void fun()
        {
            cout << sizeof(a) / sizeof(int) << endl; // 3*3=9
        }
    };
};

using namespace tool;

int main()
{
    // test t;
    // t.fun();

    // bool p[6]{0, 0, 0, 0, 0, 1};
    // char c;
    // c = find(p + 1, p + 6, 1) - p;
    // cout << (int)c << " " << (char)(c + '0') << endl;

    Solution s;
    size_t cnt, cnt2;
    vector<vector<char>> board, board2;
    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'}};
    board2 = {{'.', '.', '9', '7', '4', '8', '.', '.', '.'}, {'7', '.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '2', '.', '1', '.', '9', '.', '.', '.'}, {'.', '.', '7', '.', '.', '.', '2', '4', '.'}, {'.', '6', '4', '.', '1', '.', '5', '9', '.'}, {'.', '9', '8', '.', '.', '.', '3', '.', '.'}, {'.', '.', '.', '8', '.', '3', '.', '2', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.', '6'}, {'.', '.', '.', '2', '7', '5', '9', '.', '.'}};

    cnt = count_filled(board);
    // printSudoku(board);
    s.solveSudoku(board);
    cnt2 = count_filled(board);
    // printSudoku(board);
    cout << cnt << " " << cnt2 << endl;

    // printSudoku(board2);
    cnt = count_filled(board2);
    s.solveSudoku(board2);
    cnt2 = count_filled(board2);
    printSudoku(board2);
    cout << cnt << " " << cnt2 << endl;

    // cout << CNT << endl;

    return 0;
}

//废弃代码
//     // find_only：检查(x,y)所在的行、列、九宫格不可能出现的数字，试找出(x,y)唯一可能的数字\
        // 如果(x,y)所在行/列/九宫格的其他位置都不可能出现某个值，那么这个值就只能在(x,y)上
//     fill_n(only + 1, 9, 1); //重置only
//     //检查行
//     for (int i = 0; i < board.size(); i++)
//     {
//         if (board[x][i] != '.')
//             only[board[x][i]] = 0;
//         else
//             for (int j = 1; j < 10; j++)
//                 if (val[x][i][j])
//                     only[j] = 0;
//     }
//     if (count(only + 1, only + 10, 1)) //如果only有唯一值
//     {
//         board[x][y] = find(only + 1, only + 10, 1) - only; //则(x,y)必为该值
//         return 0;                                            //(x,y)已确定，结束函数
//     }
//     fill_n(only + 1, 9, 1); //重置only
//     //检查列
//     for (int i = 0; i < board.size(); i++)
//     {
//         if (board[i][y] != '.')
//             only[board[i][y]] = 0;
//         else
//             for (int j = 1; j < 10; j++)
//                 if (val[i][y][j])
//                     only[j] = 0;
//     }
//     if (count(only + 1, only + 10, 1)) //如果only有唯一值
//     {
//         board[x][y] = find(only + 1, only + 10, 1) - only; //则(x,y)必为该值
//         return 0;                                            //(x,y)已确定，结束函数
//     }
//     fill_n(only + 1, 9, 1); //重置only
//     //检查九宫格
//     for (int i = gongGe.first; i < gongGe.first + 3; i++)
//     {
//         for (int j = gongGe.second; j < gongGe.second + 3; j++)
//         {
//             if (board[i][j] != '.')
//                 only[board[i][j]] = 0;
//             else
//                 for (int k = 1; k < 10; k++)
//                     if (val[i][j][k])
//                         only[k] = 0;
//         }
//     }
//     if (count(only + 1, only + 10, 1)) //如果only有唯一值
//     {
//         board[x][y] = find(only + 1, only + 10, 1) - only; //则(x,y)必为该值
//         return 0;                                            //(x,y)已确定，结束函数
//     }