Python 中有效的数独

pythonserver side programmingprogramming更新于 2025/10/25 16:12:17

假设我们有一个 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"]]