2020-03-24 22:23:32
问题描述：
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
提示:
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
问题求解：
经典的DFS问题，可以使用回溯法解决。
int[][] rows = new int[9][9];
int[][] cols = new int[9][9];
int[][] boxes = new int[9][9];
public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') continue;
int k = c - '0';
rows[i][k - 1] = 1;
cols[j][k - 1] = 1;
boxes[i / 3 * 3 + j / 3][k - 1] = 1;
}
}
helper(board, 0, 0);
}
private boolean helper(char[][] board, int row, int col) {
if (row >= 9) return true;
int nr = row;
int nc = col + 1;
if (col == 8) {
nr = nr + 1;
nc = 0;
}
if (board[row][col] != '.') return helper(board, nr, nc);
for (int i = 1; i <= 9; i++) {
if (rows[row][i - 1] == 1 || cols[col][i - 1] == 1 || boxes[row / 3 * 3 + col / 3][i - 1] == 1) continue;
rows[row][i - 1] = 1;
cols[col][i - 1] = 1;
boxes[row / 3 * 3 + col / 3][i - 1] = 1;
board[row][col] = (char)(i + '0');
if (helper(board, nr, nc)) return true;
board[row][col] = '.';
rows[row][i - 1] = 0;
cols[col][i - 1] = 0;
boxes[row / 3 * 3 + col / 3][i - 1] = 0;
}
return false;
}