Leetcode题目037-解数独

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


class Solution
{
public:

    vector<vector<char>> result;

    void solveSudoku(vector<vector<char>>& board)
{
        vector<char> candidates = cal_candidates(board, 0, 3);
        //for (auto ch : candidates)
        //{
        //    cout << ch;
        //}
        //cout << endl;
        vector<vector<int>> to_be_filled = cal_to_be_filled(board);
        int N = to_be_filled.size();
        backtrace(0, board,to_be_filled);
        board = result;
    }


    vector<char> cal_candidates(vector<vector<char>>& board, int row, int col)
    {
        //计算每个位置的候选数字
        vector<char> res;
        if (board[row][col] != '.') return res;
        unordered_set<char> used_chars; //无序集合
        // 计算已经用过的数字，包含空位符号 ‘.'
        for (int i = 0; i < 9; i++) used_chars.insert(board[i][col]);
        for (int i = 0; i < 9; i++) used_chars.insert(board[row][i]);
        int R = row / 3;
        int C = col / 3;
        for(int i = 3 * R; i < 3 * R + 3; i++)
        {
            for (int j = 3 * C; j < 3 * C + 3; j++)
            {
                //cout << board[i][j];
                if (i != row && j != col)
                    used_chars.insert(board[i][j]);
            }
        }


        vector<char> all={'1','2','3','4','5','6','7','8','9'};
        for (char ch : all)
        {
            if (used_chars.find(ch) == used_chars.end())//找不到！
                res.push_back(ch); // 没用过的 做候选
        }


        return res;
    }


    vector<vector<int>> cal_to_be_filled(vector<vector<char>>& board)
    {
        //计算哪些位置空缺，需要填入数字
        vector<vector<int>> res;
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.') 
                    res.emplace_back(vector<int>{ i, j });
            }
        }
        return res;
    }
    
    
    void backtrace(int start, vector<vector<char>>& board, vector<vector<int>>& to_be_filled) //
{
        
        if (start == to_be_filled.size()) //退出条件。全部填完，的下一个不存在的位置
        {
            result = board; //需要另一个全局变量保存解。因为它会一闪而过......
            return;
        }


        //if (start == to_be_filled.size()) return;
        int row = to_be_filled[start][0];
        int col = to_be_filled[start][1];
            
        vector<vector<char>> temp = board; //备份，以待回溯
        vector<char> candidates = cal_candidates(board, row, col);
        for (char candidate : candidates)
        {
            //cout << row << "," << col << " =? " << candidate << endl;
            board[row][col] = candidate;
            backtrace(start + 1, board, to_be_filled); //进入下一层调用
            board = temp;//回溯
            //注意，在最后一层找到解后，会返回上一层，board会改变，（如果用board保存解）会丢失解的保存
            //board = temp 会让board 复原状态，也会丢失解的保存。所以需要另一个变量全局变量保存解
        }
    }


    void print_board(vector<vector<char>>& board)
{
        for (auto v_row : board)
        {
            for (auto c : v_row)
            {
                cout << c << ' ';
            }
            cout << endl;
        }
    }
}; 



int main(void)
{
    Solution sol;
    //vector<vector<char>> board(9,vector<char>(9));


    vector<vector<char>> 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'} };
    vector<vector<int>>tobe = sol.cal_to_be_filled(board);
    cout << "有"<<tobe.size() <<"个位置需要填入" <<endl;
    sol.solveSudoku(board);
    cout << endl;
    cout << "最终结果" << endl;
    sol.print_board(sol.result);
    return 0;
}