37. Sudoku Solver(Hard)

1.这道题目主要是使用回溯法进行遍历，其中需要注意的是进行剪枝。剪枝情况如下：

首先是遍历可以填充的数字，如果遍历完后都没有可以填充，那么就直接回溯，不用继续遍历接下来的空格。

否则会出现这种情况，前面还没填充就去填充后面的：

另外最基本的就是用hash检测行列和方块里面的数字是否已经被使用，其中方块数字的index应该为［i／3*3+j/3］。

AC代码如下：

[c language=”++”]
class Solution {
public:
vector<vector<bool>> HashRow;
vector<vector<bool>> HashRec;
vector<vector<bool>> HashCol;
void dfs(vector<vector<char>>& board,int&leftNumber,bool&isFilled)
{
//printfVectorInt2(board);
//printf("\n");
if (leftNumber == 0)
isFilled = true;
else
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == ‘.’)
{
bool noNum = true;
for (int num = 1; num <= 9; num++)
{
if (!HashRow[i][num] && !HashCol[j][num] && !HashRec[i / 3 * 3 + j / 3][num])
{
noNum = false;
HashRow[i][num] = true;
HashCol[j][num] = true;
HashRec[i / 3 * 3 + j / 3][num] = true;

leftNumber–;
board[i][j] = num+’0′;
dfs(board, leftNumber, isFilled);
if (isFilled)
return;//已经填充成功

//填充失败，还原情况
board[i][j] = ‘.’;
leftNumber++;
HashRow[i][num] = false;
HashCol[j][num] = false;
HashRec[i / 3 * 3 + j / 3][num] = false;
noNum = true;
}
}
if (noNum) return;
}
}
}
}
}

void solveSudoku(vector<vector<char>>& board) {
HashRow = vector<vector<bool>>(10, vector<bool>(10, false));
HashRec = vector<vector<bool>>(10, vector<bool>(10, false));
HashCol = vector<vector<bool>>(10, vector<bool>(10, false));
vector<int> CountRow(9, 0);
vector<int> CountRec(9, 0);
vector<int> CountCol(9, 0);
int leftNumber = 0;//仍需要填充的数字个数
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[i].size(); j++)
{
if (board[i][j] != ‘.’)
{//记录已经出现过的数字
CountRow[i]++;
CountCol[j]++;
CountRec[i / 3 * 3 + j / 3]++;
HashRow[i][board[i][j]-‘0’] = true;
HashCol[j][board[i][j]-‘0’] = true;
HashRec[i / 3 * 3 + j / 3][board[i][j] – ‘0’] = true;
}
else
leftNumber++;
}
}
bool isFilled = false;
dfs(board, leftNumber, isFilled);
}
};
[/c]