Leetcode 36 Valid Sudoku

Soru

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

Örnek 1

Input: board = 
[["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"]]
Output: true

Örnek 2

Input: board = 
[["8","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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Çözüm

• Bu problem, 9x9’lik bir Sudoku tahtasının geçerli olup olmadığını kontrol etmenizi ister. Geçerli bir Sudoku tahtası, her satırda, her sütunda ve her 3x3’lük alt-karede 1’den 9’a kadar rakamların tekrarlanmadan yer almasını gerektirir.

• Bu problemi çözmek için, her satır, her sütun ve her 3x3 alt-karedeki sayıların tekrarlanıp tekrarlanmadığını kontrol etmek gerekiyor. Python’da bu kontrolü set kullanarak ve her birinin bir defaultdict içinde saklanmasını sağlayarak yapabiliriz.

• Data Yapıları Hazırlama:cols, rows, squares adında üç defaultdict(set) oluşturulur. Bunlar sırasıyla her sütun, satır ve 3x3 alt-kare için geçerli sayıları saklar.

• Tahta Üzerinde Dolaşma:9x9 tahtanın her bir hücresi (r, c) koordinatlarıyla dolaşılır.

• Boş Hücre Kontrolü:board[r][c] == “.” kontrolü ile boş hücreler atlanır.

• Geçerlilik Kontrolü:Her hücre için, o hücredeki değerin mevcut satır, sütun veya 3x3 alt-karede olup olmadığı kontrol edilir. Eğer değer zaten mevcutsa, Sudoku tahtası geçerli değildir ve fonksiyon False döndürür.

• Setlere Değer Ekleme:Çakışma tespit edilmediyse, ilgili değer ilgili satırın, sütunun ve alt-karenin setine eklenir.

• Sonuç:Eğer tahtada herhangi bir çakışma yoksa, döngüler tamamlandıktan sonra Sudoku geçerli kabul edilir ve True döndürülür.

• Not : key = (r /3, c /3) Örneğin, hücre (4, 7) için:(4 // 3) = 1 ve (7 // 3) = 2 hesaplanır.Bu yöntem, her bir hücrenin hangi 3x3 alt-kare içinde bulunduğunu kolayca saptamak için etkili bir yol sağlar. Bu da, her 3x3 alt-karedeki sayıların tekrarlanmadığını kontrol etmeyi basit ve hızlı hale getirir. Bu hesaplama, her bir alt-karenin kendine özgü bir set içermesini ve dolayısıyla her birinin içindeki değerlerin benzersiz olmasını sağlar.

Code

class Solution:
    def isValidSudoku(board):
        # Satır, sütun ve 3x3 alt-kareleri takip etmek için dictionary'ler
        cols = defaultdict(set)
        rows = defaultdict(set)
        squares = defaultdict(set)  # key = (r /3, c /3)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue  # Boş hücreler dikkate alınmaz
                if (
                    board[r][c] in rows[r]  # Satırda aynı değerden var mı kontrol et
                    or board[r][c] in cols[c]  # Sütunda aynı değerden var mı kontrol et
                    or board[r][c] in squares[(r // 3, c // 3)]  # İlgili 3x3 alt-karede kontrol et
                ):
                    return False  # Eğer tekrar eden bir değer varsa, Sudoku geçersizdir

                # Çakışma yoksa, değeri ilgili setlere ekle
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])

        return True  # Tüm hücreler geçerliyse, Sudoku geçerlidir
        

Complexity

• Time complexity (Zaman Karmaşıklığı): O(1), çünkü tahta her zaman 9x9’dur ve sabit sayıda işlem yapılmaktadır.
• Space complexity (Alan Karmaşıklığı): O(1), çünkü yalnızca sabit miktarda ekstra hafıza kullanılmaktadır (27 set için).