0%

leetcode 36. Valid Sudoku || 37. Sudoku Solver

本次题解包括

  • 36. Valid Sudoku
  • 37. Sudoku Solver

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

题目地址:leetcode Valid Sudoku

题目大意:给你一个数独,让你判断是否是合法的数独。合法的数度定义为:每一行和每一列的数字以及每9个宫格数字不能重复出现。

思路:

先判断行和列是否有重复的,再判断9个是否有重复的。

直观的写法:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; ++i) {
vector<bool> vis(10, false);
for (int j = 0; j < 9; ++j) {
char c = board[i][j];
if (c == '.') continue;
c -= '0';
if (vis[c]) return false;
vis[c] = true;
}
}

for (int j = 0; j < 9; ++j) {
vector<bool> vis(10, false);
for (int i = 0; i < 9; ++i) {
char c = board[i][j];
if (c == '.') continue;
c -= '0';
if (vis[c]) return false;
vis[c] = true;
}
}

for (int si = 0; si < 9; si += 3) {
for (int sj = 0; sj < 9; sj += 3) {
vector<bool> vis(10, false);
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
char c = board[si + i][sj + j];
if (c == '.') continue;
c -= '0';
if (vis[c]) return false;
vis[c] = true;
}
}
}
}
return true;
}
};

 

更好的写法:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool row_vis[9][9] = { false }, col_vis[9][9] = { false }, sub_box_vis[9][9] = { false };
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') continue;
int index = board[i][j] - '1';
int sub_index = i / 3 * 3 + j / 3;
if (row_vis[i][index] || col_vis[j][index] || sub_box_vis[sub_index][index])
return false;
row_vis[i][index] = col_vis[j][index] = sub_box_vis[sub_index][index] = true;
}
}
return true;
}
};

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
row_vis = [[False] * 9 for _ in range(9)]
col_vis = [[False] * 9 for _ in range(9)]
sub_box_vis = [[False] * 9 for _ in range(9)]

for i in range(9):
for j in range(9):
if board[i][j] == '.': continue
index = ord(board[i][j]) - ord('1')
sub_index = i // 3 * 3 + j // 3
if row_vis[i][index] or col_vis[j][index] or sub_box_vis[sub_index][index]:
return False
row_vis[i][index] = col_vis[j][index] = sub_box_vis[sub_index][index] = True
return True


 


37. Sudoku Solver

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.

A sudoku puzzle...

...and its solution numbers marked in red.

题目地址:leetcode Sudoku Solver

题目大意: 给个数独,让你输出解

思路:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
bool dfs(int cur, vector<vector<char>> &board, bool row[][9], bool col[][9], bool grid[][9]){
if(cur >= 81)
return true;
int x = cur / 9, y = cur % 9;
if(board[x][y] != '.')
return dfs(cur + 1, board, row, col, grid);
for(int i = 0; i < 9; ++i){
int k = x / 3 * 3 + y / 3;
if(row[x][i] col[y][i] grid[k][i])
continue;
row[x][i] = col[y][i] = grid[k][i] = true;
board[x][y] = i + '1';
if(dfs(cur + 1, board, row, col, grid))
return true;
board[x][y] = '.';
row[x][i] = col[y][i] = grid[k][i] = false;
}
return false;
}

public:
void solveSudoku(vector<vector<char>>& board) {
bool row[9][9] = {false}, col[9][9] = {false}, grid[9][9] = {false};
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
if(board[i][j] == '.') continue;
int t = board[i][j] - '1', k = i / 3 * 3 + j / 3;
row[i][t] = col[j][t] = grid[k][t] = true;
}
}
dfs(0, board, row, col, grid);
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
def dfs(self, cur, board, vis_row, vis_col, vis_sub_box):
if cur == 81: return True
x, y = cur // 9, cur % 9
if board[x][y] != '.':
return self.dfs(cur + 1, board, vis_row, vis_col, vis_sub_box)

for k in range(9):
sub_index = x // 3 * 3 + y // 3
if vis_row[x][k] or vis_col[y][k] or vis_sub_box[sub_index][k]:
continue

vis_row[x][k] = vis_col[y][k] = vis_sub_box[sub_index][k] = True
board[x][y] = chr(k + ord('1'))

if self.dfs(cur + 1, board, vis_row, vis_col, vis_sub_box):
return True

board[x][y] = '.'
vis_row[x][k] = vis_col[y][k] = vis_sub_box[sub_index][k] = False

return False

def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
vis_row = [[False] * 9 for _ in range(9)]
vis_col = [[False] * 9 for _ in range(9)]
vis_sub_box = [[False] * 9 for _ in range(9)]

for i in range(9):
for j in range(9):
if board[i][j] == '.': continue
k = ord(board[i][j]) - ord('1')
sub_index = i // 3 * 3 + j // 3
vis_row[i][k] = vis_col[j][k] = vis_sub_box[sub_index][k] = True
self.dfs(0, board, vis_row, vis_col, vis_sub_box)


 

本文是leetcode如下的题解

  • 36. Valid Sudoku
  • 37. Sudoku Solver

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~