Sudoku hợp lệ bằng Python

Giả sử chúng ta có một bảng Sudoku 9x9. Chúng tôi phải kiểm tra xem điều đó có hợp lệ hay không. Chỉ các ô đã điền mới cần được xác thực theo các quy tắc sau -

• Mỗi hàng phải chứa các chữ số từ 1-9 không lặp lại.
• Mỗi cột phải chứa các chữ số từ 1-9 không lặp lại.
• Mỗi ô trong số 9 ô con (3x3) của lưới phải chứa các chữ số từ 1-9 không lặp lại.

Giả sử lưới Sudoku giống như -

Điều này hợp lệ.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• cho tôi trong phạm vi từ 0 đến 8
  • tạo một số từ điển trống có tên là row, col và block, row_cube:=3 * (i / 3) và col_cube:=3 * (i mod 3)
  • cho j trong phạm vi từ 0 đến 8
    • nếu bảng [i, j] không trống và bảng [i, j] liên tiếp, thì trả về false
    • row [board [i, j]]:=1
    • nếu bảng [j, i] không trống và bảng [j, i] bằng col, thì trả về false
    • col [board [j, i]]:=1
    • rc:=row_cube + j / 3 và cc:=col_cube + j mod 3
    • nếu bảng [rc, cc] trong khối và bảng [rc, cc] không trống, thì trả về false
    • khối [board [rc, cc]]:=1
• trả về true

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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"]]))

Đầu vào

[["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"]]

Đầu ra

true