使用计算机语言解决谜题问题，对大部分编程爱好者来说都是最感兴趣的。今天来看一道数独问题。

先来讲一下数独的规则。

在一个九宫格（9x9的阵列）的每个格子都有一个数字，并且：

每一行中都包含1-9九个数字且不重复；

每一列都包含1-9九个数字且不重复；

将九宫格分成9个3x3小格子，每个小格子中，包含1-9九个数字且不重复；

在给出一个九宫格，里面已经填写了部分数字后，按照规则要求解出其他未填的空格。

虽然我们人脑做数独题时颇费脑筋，但是计算机解决起来还是很容易的。

下面这是我的解决方案，略加优化的使用递归暴力法。

/*九宫格用board存储，每个格中填写'1' - '9', 或者 '.',表示待填项.*/class Solution {public:    void solveSudoku(vector<vector<char>>& board) {                //首先将待解决的空格收集存放到一个列表中        vector<pair<int,int>> toBeSolved;        for(int i=0;i<9;i++)        {            for(int j=0;j<9;j++)            {                if(board[i][j]=='.')                    toBeSolved.push_back(pair<int,int>(i,j));            }        }        //从第一个开始，逐个解决每一个空格        subsolver(board,toBeSolved,0);    }    // 递归解决每一个空格    // currIdx是当前待解决的空格索引    bool subsolver(vector<vector<char>>& board,vector<pair<int,int>> toBeSolved,int currIdx){        pair<int,int> curr = toBeSolved[currIdx];                //根据数独规则，计算出当前空格可以填写的数字集合        set<char> available = getAvailable(board, curr);                //如果没有可填写的数字，说明这条路径走不通        if(available.empty())            return false;                //如果已经是最后一个空格，到这一步就胜利了, 成功返回！！！        ++currIdx;        if(currIdx==toBeSolved.size())        {               board[curr.first][curr.second] = *available.begin();            return true;        }        //依次填入一个可选数字，递归调用本函数，看是否能够得到正确答案        for(auto c:available){            board[curr.first][curr.second] = c;                        //这个数字得到了正确结果，返回true            if(subsolver(board,toBeSolved,currIdx))                return true;                        //这个数字不对，恢复现场，再试下一个;            board[curr.first][curr.second] = '.';        }        //本轮挑战失败        return false;    }    //按照规则计算当前空格可选的数字    set<char> getAvailable(vector<vector<char>>& board,pair<int,int>& curr){        set<char> available = {'1','2','3','4','5','6','7','8','9'};        for(int i=0;i<9;i++)        {            available.erase(board[curr.first][i]);            available.erase(board[i][curr.second]);            if(available.empty())                return available;        }        int sub_row = curr.first/3*3;        int sub_col = curr.second/3*3;        for(int i=0;i<3;i++)        {            for(int j=0;j<3;j++)            {                available.erase(board[sub_row+i][sub_col+j]);                if(available.empty())                    return available;            }        }        return available;    }};

算法时间复杂度较高，每个空格最多可选项9个，时间复杂度是：

程序的空间复杂度是O(1).