Kiểm tra Sudoku hợp lệ trong Python

Giả sử chúng ta có một bàn cờ Sudoku 9x9. Chúng ta phải kiểm tra xem bàn cờ đó có hợp lệ hay không. Chỉ các ô đã điền 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 9 ô con (3x3) của lưới phải chứa các chữ số từ 1-9 không lặp lại.

Ví dụ lưới Sudoku như sau (dấu chấm đại diện cho ô trống):

Bàn cờ này là hợp lệ.

Để giải quyết, chúng ta làm theo các bước sau:

• Với i từ 0 đến 8:
  • Tạo từ điển rỗng row, col và block, row_cube := 3 * (i // 3), và col_cube := 3 * (i % 3).
  • Với j từ 0 đến 8:
    • Nếu board[i][j] không trống và board[i][j] trong row, trả về false.
    • row[board[i][j]] := 1.
    • Nếu board[j][i] không trống và board[j][i] trong col, trả về false.
    • col[board[j][i]] := 1.
    • rc := row_cube + j//3 và cc := col_cube + j%3.
    • Nếu board[rc][cc] trong block và board[rc][cc] không trống, trả về false.
    • block[board[rc][cc]] := 1.
• Trả về true.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

class Solution(object):
    def isValidSudoku(self, board):
        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