LeetCode 0037 - Sudoku Solver
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard | or |
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits
1-9
must occur exactly once in each row.Each of the digits
1-9
must occur exactly once in each column.Each of the the digits
1-9
must occur exactly once in each of the sub-boxes of the grid.
Empty cells are indicated by the character '.'
.
A sudoku puzzle...
...and its solution numbers marked in red.
Note:
The given board contain only digits 1-9
and the character '.'
.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always .
# 题意
给定一个 的数独,求出该数独的解。输入保证有且仅有一个合法解。
# 题解
考虑DFS枚举所有可能的情况,然后用合法性剪枝处理掉所有的非法解即可。在存在合法性剪枝的情况下,搜索本身的时间复杂度为 。
注意,一个可能的想法是利用LeetCode 0036中刚写完的数独合法性判断来求解本题,从正确性上来说当然没什么问题,但每次都进行 的判定毫无疑问是非常低效的,总的时间复杂度为 。不难发现这样会执行很多次重复的合法性判断。
我们应当在DFS的过程中维护每行每列每个方格中的数字出现情况,这样就可以免除大量的重复判断,总的时间复杂度仍为 。。
# AC代码( 解法)
class Solution {
public:
void solveSudoku(vector<vector<char>> & board) {
// DFS
bool flag = false;
dfs(0, 0, board, flag);
}
// 深度优先搜索
void dfs(int x, int y, vector<vector<char>> & board, bool & flag) {
// 递归终止
if (flag) {
return;
}
if (y == 9) {
flag = true;
return;
}
// 获取目标坐标
int nx = (x + 1) % 9, ny = (x == 8 ? y + 1 : y);
// 递归
if (board[x][y] != '.') {
dfs(nx, ny, board, flag);
return;
}
// 递归
for (char ch = '1'; ch <= '9' && !flag; ch ++) {
board[x][y] = ch;
if (isValidSudoku(board)) {
dfs(nx, ny, board, flag);
}
if (!flag) {
board[x][y] = '.';
}
}
}
// 判断数独是否合法
bool isValidSudoku(const vector<vector<char>> & board) {
// 声明
bool existed[10];
// 判断行
for (int i = 0; i < 9; i ++) {
memset(existed, false, sizeof(existed));
for (int j = 0; j < 9; j ++) {
if (!check(board[i][j], i, j, existed)) {
return false;
}
}
}
// 判断列
for (int j = 0; j < 9; j ++) {
memset(existed, false, sizeof(existed));
for (int i = 0; i < 9; i ++) {
if (!check(board[i][j], i, j, existed)) {
return false;
}
}
}
// 判断方格
for (int k = 0; k < 9; k ++) {
memset(existed, false, sizeof(existed));
int x = 3 * (k / 3), y = 3 * (k % 3);
for (int i = x; i < x + 3; i ++) for (int j = y; j < y + 3; j ++) {
if (!check(board[i][j], i, j, existed)) {
return false;
}
}
}
// 返回
return true;
}
// 判断
bool check(char num, int x, int y, bool existed[]) {
if (num == '.') {
return true;
}
if (!existed[num - '0']) {
existed[num - '0'] = true;
return true;
}
return false;
}
};
# AC代码( 解法)
class Solution {
public:
void solveSudoku(vector<vector<char>> & board) {
// 初始化
memset(existed_row, false, sizeof(existed_row));
memset(existed_column, false, sizeof(existed_column));
memset(existed_square, false, sizeof(existed_square));
for (int x = 0; x < 9; x ++) for (int y = 0; y < 9; y ++) {
int z = 3 * (x / 3) + (y / 3);
if (board[x][y] != '.') {
int num = board[x][y] - '0';
set_number(x, y, z, num, true);
}
}
// DFS
bool flag = false;
dfs(0, 0, board, flag);
}
// 设置数字
inline void set_number(int x, int y, int z, int num, bool flag) {
existed_row[x][num] = flag;
existed_column[y][num] = flag;
existed_square[z][num] = flag;
}
// 深度优先搜索
void dfs(int x, int y, vector<vector<char>> & board, bool & flag) {
// 递归终止
if (flag) {
return;
}
if (y == 9) {
flag = true;
return;
}
// 获取目标坐标
int nx = (x + 1) % 9, ny = (x == 8 ? y + 1 : y);
// 递归
if (board[x][y] != '.') {
dfs(nx, ny, board, flag);
return;
}
// 递归
int z = 3 * (x / 3) + (y / 3);
for (char ch = '1'; ch <= '9' && !flag; ch ++) {
int num = ch - '0';
if (is_legal(x, y, z, num)) {
set_number(x, y, z, num, true);
board[x][y] = ch;
dfs(nx, ny, board, flag);
if (!flag) {
set_number(x, y, z, num, false);
board[x][y] = '.';
}
}
}
}
// 判断是否合法
inline bool is_legal(int x, int y, int z, int num) {
return (!existed_row[x][num] && !existed_column[y][num] && !existed_square[z][num]);
}
// 全局变量
bool existed_row[9][10];
bool existed_column[9][10];
bool existed_square[9][10];
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01