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.
编写一个程序，通过填充空单元格来解决数独谜题。 空单元格由字符’。’表示。
数独只有一个解
使用3个二维数组，分别记录 每一行、每一列、每个小九宫格里已经出现的数字。下标代表数字，值代表是否出现过
然后使用 DSF。对每个需要填充的单元格进行递归。递归时根据之前统计的3个二维数组来判断应该填哪个数字
public static boolean filling(char[][] board, int[][] row, int[][] col, int[][] square) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (int k = 0; k < 9; k++) {
int sIndex = i / 3 * 3 + j / 3;
if (row[i][k] == 0 && col[j][k] == 0 && square[sIndex][k] == 0) {
board[i][j] = ((k + 1) + "").charAt(0);
row[i][k] = col[j][k] = square[sIndex][k] = 1;
if (filling(board, row, col, square)) {
return true;
} else {
board[i][j] = '.';
row[i][k] = col[j][k] = square[sIndex][k] = 0;
}
}
}
return false;
}
}
}
return true;
}
public static void solveSudoku(char[][] board) {
int[][] row = new int[9][9];
int[][] col = new int[9][9];
int[][] square = new int[9][9];
//init array
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '0' - 1;
//根据 i、j 计算属于第几个九宫格
int sIndex = i / 3 * 3 + j / 3;
row[i][num] = col[j][num] = square[sIndex][num] = 1;
}
}
}
filling(board, row, col, square);
}