正文
Leetcode之回溯法专题-37. 解数独（Sudoku Solver）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Leetcode之回溯法专题-37. 解数独（Sudoku Solver）
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
解法：
分析：
给定一个9*9的char型的二维数组，数组里已经填好了一些数字，要求生成一个数独。
本题可以用回溯法，在空的格子里填下1-9数字，全部填完后，判断是否为数独，是->保存退出，否->回溯，继续循环下一个数字。
判断当前坐标为：(row,col)的坐标点的行，列，方块区内是否满足条件的函数：
public boolean isValid(char board[][],int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] != '.' && board[i][col] == c)
return false; // 检查行
if (board[row][i] != '.' && board[row][i] == c)
return false; // 检查列
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
&& board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false; // 检查3x3小方格
}
return true;
}
AC代码为（这样写时间复杂有点高，后面再优化）：
class Solution {
public boolean isValid(char board[][], int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] != '.' && board[i][col] == c)
return false; // 检查行
if (board[row][i] != '.' && board[row][i] == c)
return false; // 检查列
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
&& board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false; // 检查3x3小方格
}
return true;
}
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
Set<Character> set = new HashSet<>();
boolean flag = true;
for (int j = 0; j < 9; j++) {
char ch = board[i][j];
if (ch == '.')
continue;
if (set.contains(ch) == true) {
flag = false;
}
set.add(ch);
}
if (flag == false) {
return false;
}
}
for (int i = 0; i < 9; i++) {
Set<Character> set = new HashSet<>();
boolean flag = true;
for (int j = 0; j < 9; j++) {
char ch = board[j][i];
if (ch == '.')
continue;
if (set.contains(ch) == true) {
flag = false;
}
set.add(ch);
}
if (flag == false) {
return false;
}
}
for (int a = 0; a < 3; a++) {
for (int b = 0; b < 3; b++) {
Set<Character> set = new HashSet<>();
boolean flag = true;
for (int i = a * 3; i < a * 3 + 3; i++) {
for (int j = b * 3; j < b * 3 + 3; j++) {
char ch = board[i][j];
if (ch == '.')
continue;
if (set.contains(ch) == true) {
flag = false;
}
set.add(ch);
}
}
if (flag == false) {
return false;
}
}
}
return true;
}
char[][] ans = new char[9][9];
public void solveSudoku(char[][] board) {
dfs(board, 0);
for (int aa = 0; aa < 9; aa++) {
for (int bb = 0; bb < 9; bb++) {
board[aa][bb] = ans[aa][bb];
}
}
}
public void dfs(char[][] board, int x) {
int i = x / 9;
int j = x % 9;
if (x == 81) {
for (int aa = 0; aa < 9; aa++) {
for (int bb = 0; bb < 9; bb++) {
ans[aa][bb] = board[aa][bb];
}
}
return;
}
if (board[i][j] != '.') {
dfs(board, x + 1);
} else {
for (int k = 1; k <= 9; k++) {
if (isValid(board, i, j, (char) ('0' + k))) {
board[i][j] = (char) ('0' + k);
dfs(board, x + 1);
board[i][j] = '.';
}
}
}
}
}
