10000 added 118. Sudoku Solver · skycache/LeetCode-1@3cda2b7 · GitHub
[go: up one dir, main page]
Skip to content

Commit 3cda2b7

Browse files
pezypezy
committed
added 118. Sudoku Solver
1 parent 62a8e7f commit 3cda2b7

File tree

3 files changed

+152
-0
lines changed

3 files changed

+152
-0
lines changed

‎118. Sudoku Solver/README.md

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
这道题我拿到手就想到了 **回溯+DFS** 的思路。
2+
3+
因为这就是咱们人工去解数独的方法，看到空的格子，首先在脑海里列出能够放的数字列表，然后先试第一个，接着看后续的格子，采取同样的方式。如果发现不对劲了，回溯回去，用列表中的第二个，再试。如此反复，就可以得到完整的数独方案了。
4+
5+
数独的问题不是第一次见，可以回顾一下：[064. Valid Sudoku](https://github.com/pezy/LeetCode/tree/master/064.%20Valid%20Sudoku).
6+
7+
-----
8+
9+
我们来看题目中的例子：
10+
11+
5 3 X | . 7 . . . . | // X 的备选方案：
12+
6 . . |------------ | // row : 1 2 4 6 8 9
13+
. 9 8 | 1 9 5 . . . | // col : 1 2 3 4 5 6 7 9
14+
------| . . . . 6 . | // cel : 1 2 4 7
15+
8 . . | . 6 . . . 3 |
16+
4 . . | 8 . 3 . . 1 | S(0)
17+
7 . . | . 2 . . . 6 | / | \
18+
. 6 . | . . . 2 8 . | 1 2 4
19+
. . . | 4 1 9 . . 5 | | | |
20+
. . . | . 8 . . 7 9 | S(0,1) S(0,2) S(0,4)
21+
22+
从上图的分析来看，我们填写 X 的过程如下：
23+
24+
1. 确定(row, col)
25+
2. 1 ~ 9 中逐一尝试放入 pos(row, col), 若没有，回到 1.
26+
1. 若 cur_row, cur_col, cur_cell 出现重复，将 (row, col) 置为 '.', 回到 1.
27+
2. 若无重复，填入该数字，回到 1.
28+
3. 所有(row, col)都填满，成功。
29+
30+
针对第一步，我们需要一个函数，尝试遍历整个矩阵，找到第一个 '.' 的位置，立刻返回：
31+
32+
```cpp
33+
bool findEmptyCell(const vector<vector<char> > &board, size_t &row, size_t &col)
34+
{
35+
for (row = 0; row < board.size(); ++row)
36+
for (col = 0; col < board[row].size(); ++col)
37+
if (board[row][col] == '.') return true;
38+
return false;
39+
}
40+
```
41+
42+
针对第二步，检查重复，我们也需要一个函数，分别检查**同行**,**同列**,**同Cell**是否有重复。
43+
```cpp
44+
bool isSafe(const vector<vector<char> > &board, size_t row, size_t col, char c)
45+
{
46+
for (size_t i=0; i<9; ++i) {
47+
if (board[row][i] == c) return false;
48+
if (board[i][col] == c) return false;
49+
if (board[row/3 * 3 + i / 3][col/3 * 3 + i % 3] == c) return false;
50+
}
51+
return true;
52+
}
53+
```
54+
55+
第三步，实际可以复用第一步的结果，如果找不到 '.', 那么自然可以认为，已经全都填满。
56+
57+
最后我们只需要组织逻辑十分清晰的主体递归函数即可：
58+
59+
```cpp
60+
bool solveSudoku(vector<vector<char> > &board) {
61+
size_t row = 0, col = 0;
62+
if (!findEmptyCell(board, row, col)) return true; // 第一步
63+
for (char c : {'1', '2', '3', '4', '5', '6', '7', '8', '9'}) // 第二步
64+
if (isSafe(board, row, col, c)) {
65+
board[row][col] = c;
66+
if (solveSudoku(board)) return true;
67+
board[row][col] = '.'; // 回溯
68+
}
69+
return false;
70+
}
71+
```
72+
73+
总共30行的代码。比起论坛里动辄百行的代码来说，是不是面试的时候遇到，更加有信心写出呢？
74+
75+
清晰简单的代码思路，通常也意味着效率并不高，这个答案提交，可能只是 C++ 中的垫底。
76+
77+
如果尝试用 hash 表来优化，可能就无法这么简洁了。（隐隐盼望可以）
78+
79+
------
80+
81+
随着 LeetCode 题目的难度升级，我有时可能无法做到一天一道题了。
82+
83+
风格，也从追求极致的效率，转变为短小精悍，意图清晰了。
84+
85+
毕竟，再高效的代码，你笔试面试的时候完全想不起来（或是不好理顺），也是白搭。

‎118. Sudoku Solver/main.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
4+
using namespace std;
5+
6+
int main()
7+
{
8+
Solution s;
9+
vector<std::vector<char>> board = {
10+
{'5','3','.','.','7','.','.','.','.'},
11+
{'6','.','.','1','9','5','.','.','.'},
12+
{'.','9','8','.','.','.','.','6','.'},
13+
{'8','.','.','.','6','.','.','.','3'},
14+
{'4','.','.','8','.','3','.','.','1'},
15+
{'7','.','.','.','2','.','.','.','6'},
16+
{'.','6','.','.','.','.','2','8','.'},
17+
{'.','.','.','4','1','9','.','.','5'},
18+
{'.','.','.','.','8','.','.','7','9'}
19+
20+
};
21+
s.solveSudoku(board);
22+
23+
for (const auto &v : board) {
24+
for (auto c : v)
25+
std::cout << c << " ";
26+
cout << std::endl;
27+
}
28+
29+
return 0;
30+
}
31+

‎118. Sudoku Solver/solution.h

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
#include <vector>
2+
using std::vector;
3+
#include <unordered_map>
4+
#include <unordered_set>
5+
#include <iostream>
6+
7+
class Solution {
8+
bool findEmptyCell(const vector<vector<char> > &board, size_t &row, size_t &col)
9+
{
10+
for (row = 0; row < board.size(); ++row)
11+
for (col = 0; col < board[row].size(); ++col)
12+
if (board[row][col] == '.') return true;
13+
return false;
14+
}
15+
bool isSafe(const vector<vector<char> > &board, size_t row, size_t col, char c)
16+
{
17+
for (size_t i=0; i<9; ++i) {
18+
if (board[row][i] == c) return false;
19+
if (board[i][col] == c) return false;
20+
if (board[row/3 * 3 + i / 3][col/3 * 3 + i % 3] == c) return false;
21+
}
22+
return true;
23+
}
24+
public:
25+
bool solveSudoku(vector<vector<char> > &board) {
26+
size_t row = 0, col = 0;
27+
if (!findEmptyCell(board, row, col)) return true;
28+
for (char c : {'1', '2', '3', '4', '5', '6', '7', '8', '9'})
29+
if (isSafe(board, row, col, c)) {
30+
board[row][col] = c;
31+
if (solveSudoku(board)) return true;
32+
board[row][col] = '.';
33+
}
34+
return false;
35+
}
36+
};

0 commit comments

Comments
 (0)
0