Description
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.
A sudoku puzzle…
…and its solution numbers marked in red.
Discussion
给出数独游戏的一个解。
这道题可以用回溯法解。与DFS方法类似，添加适当的剪枝。
对于当前某一个格子，将1-9代入，判断是否合法，如果合法，继续往下一个格子走，不合法则跳过。
判断是否合法可以仅对当前添加的格子进行判断，即判断它是否与同行，同列，同九宫格的数字相同，都不同则合法。
C++ Code
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
dfs(board, 0, 0);
}
bool dfs(vector<vector<char>> & board, int i, int j)
{
if(j >= 9)
{
return dfs(board, i + 1, 0);
}
if(i >= 9)
{
return true;
}
if(board[i][j] != '.')
{
return dfs(board, i, j + 1);
}
else
{
for(int k = 1; k <= 9; k++)
{
board[i][j] = (char)('0' + k);
if(isValid(board, i, j))
{
if(dfs(board, i, j + 1))
{
return true;
}
}
board[i][j] = '.';
}
}
return false;
}
bool isValid(vector<vector<char>> & board, int i, int j)
{
//判断board[i][j]是否与当前行的元素相同
for(int k = 0; k < 9; k++)
{
if(j != k && board[i][j] == board[i][k])
{
return false;
}
}
//判断board[i][j]是否与当前列的元素相同
for(int k = 0; k < 9; k++)
{
if(i != k && board[i][j] == board[k][j])
{
return false;
}
}
//判断board[i][j]是否与当前九宫格的元素相同,board[i/3*3][j/3*3]是board[i][j]所在九宫格的第一个元素
for(int row = i/3*3; row < i/3*3 + 3; row ++)
{
for(int col = j/3*3; col < j/3*3 + 3; col ++)
{
if(((i != row) || (j != col)) && board[i][j] == board[row][col])
{
return false;
}
}
}
return true;
}
};