数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中的有效数独
假设我们有一个 9x9 的数独棋盘。我们必须检查该棋盘是否有效。根据以下规则，只需验证已填入的方格 −
- 每一行都必须包含 1-9 的数字，不可重复。
- 每一列都必须包含 1-9 的数字，不可重复。
- 网格的 9 个 (3x3) 子方格中的每一个都必须包含 1-9 的数字，不可重复。
假设数独网格如下 −
| 5 | 3 | 7 | ||||||
| 6 | 1 | 9 | 5 | |||||
| 9 | 8 | 6 | ||||||
| 8 | 6 | 3 | ||||||
| 4 | 8 | 3 | 1 | |||||
| 7 | 2 | 6 | ||||||
| 6 | 2 | 8 | ||||||
| 4 | 1 | 9 | 5 | |||||
| 8 | 7 | 9 |
这是有效的。
为了解决这个问题，我们将遵循以下步骤 −
- 从 0 到 8 的 i
- 创建名为 row、col 和 block 的空字典，row_cube := 3 * (i / 3)，col_cube := 3 * (i mod 3)
- 从 0 到 8 的 j
- 如果 board[i, j] 不为空且 board[i, j] 在 row 中，则返回 false
- row[board[i, j]] := 1
- 如果 board[j, i] 不为空且 board[j, i] 在 col 中，则返回 false
- col[board[j, i]] := 1
- rc := row_cube + j/3 和 cc := col_cube + j mod 3
- 如果 board[rc, cc] 在 block 中且 board[rc, cc] 不为空，则返回 false
- block[board[rc, cc]] := 1
- 返回 true
示例（Python）
下面让我们看看以下实现以加深理解 −
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for i in range(9):
row = {}
column = {}
block = {}
row_cube = 3 * (i//3)
column_cube = 3 * (i%3)
for j in range(9):
if board[i][j]!='.' and board[i][j] in row:
return False
row[board[i][j]] = 1
if board[j][i]!='.' and board[j][i] in column:
return False
column[board[j][i]] = 1
rc= row_cube+j//3
cc = column_cube + j%3
if board[rc][cc] in block and board[rc][cc]!='.':
return False
block[board[rc][cc]]=1
return True
ob1 = Solution()
print(ob1.isValidSudoku([
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]))输入
[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出
true
更新于：2020-04-27
5 千+ 浏览
广告