问题描述：填充数独表中空元素。空元素为'.'
算法分析：没填充一个数，都要看这个数所在的行，列，小矩阵是否合法。然后还要看整个数独表是否正确，而判断整个数独表只能通过递归，因为前一个结果的判断要依赖后一个结果。这应该属于动态规划问题。要递归回溯。
public void solveSudoku(char[][] board) {
solve(board);
}
public boolean solve(char[][] board)
{
for(int i = 0; i < 9; i ++)
{
for(int j = 0; j < 9; j ++)
{
if(board[i][j] == '.')
{
for(int k = 1; k <= 9; k ++)
{
board[i][j] = (char) (k+'0');
if(isValid(board, i, j) && solve(board))//当前有多个选择要递归回溯
{
return true;
}
board[i][j] = '.';
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int i ,int j)
{
HashSet<Character> set = new HashSet<>();
for(int k = 0; k < 9; k ++)
{
if(set.contains(board[i][k]))
{
return false;
}
if(board[i][k]!='.')
{
set.add(board[i][k]);
}
}
set.clear();
for(int k = 0; k < 9; k ++)
{
if(set.contains(board[k][j]))
{
return false;
}
if(board[k][j]!='.')
{
set.add(board[k][j]);
}
}
set.clear();
for(int m = 0; m < 3; m ++)
{
for(int n = 0; n < 3; n ++)
{
int x = i/3*3+m;
int y = j/3*3+n;
if(set.contains(board[x][y]))
{
return false;
}
if(board[x][y]!='.')
{
set.add(board[x][y]);
}
}
}
return true;
}