37. 解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。

image.png

答案：

image.png

思路
利用回溯法，将81个格子进行遍历，如果格子中数位空，则填入1~9一次遍历，直到该位置满足要求，然后继续下一个格子/

#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<char>> numTable = {
        { '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' , '.' , '.' , '.' , '9' }
    };
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board, 0);
    }
    bool solve(vector<vector<char>>& board, int pos)
    {
        if (pos == 81)
        {
            return true;
        }
        int row = pos / 9;
        int col = pos % 9;
        if (board[row][col] == '.')
        {
            for (int i = 1; i <= 9; i++)
            {
                board[row][col] = i + '0';
                if (check(board, pos))
                {
                    if (solve(board, pos + 1))
                    {
                        return true;
                    }
                }
                board[row][col] = '.';
            }
        }
        else
        {
            if (solve(board, pos + 1))
            {
                return true;
            }
        }
        return false;
    }
    bool check(vector<vector<char>>& board, int pos)
    {
        int v = pos / 9;
        int h = pos % 9;
        char target = board[v][h];

        //ROW列
        for (vector<char>::size_type st= 0; st < 9; st++)
        {
            if (st != h)
            {
                if (target == board[v][st])
                {
                    return false;
                }
            }
        }

        //COL行
        for (vector<char>::size_type st = 0; st < 9; st++)
        {
            if (st != v)
            {
                if (target == board[st][h])
                {
                    return false;
                }
            }
        }

        int beginX = v / 3 * 3;
        int beginY = h / 3 * 3;
        for (int i = beginX; i < beginX + 3; i++)
        {
            for (int j = beginY; j < beginY + 3; j++)
            {
                if (i != v && j != h)
                {
                    if (target == board[i][j])
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

int main(int argc, char* argv[])
{
    auto test = Solution().numTable;
    Solution().solveSudoku(test);
    return 0;
}