Valid Sudoku

+10

9 karakterden oluşan 9 dizelik bir liste olan board biçiminde 9 × 9'luk bir Sudoku tahtası alırsın; her dize bir satırı temsil eder. Her karakter, 1 ile 9 arasında bir rakam veya boş bir hücre için . olur. Bir satırda, sütunda veya 3 × 3'lük kutuda hiçbir rakam iki kez görünmüyorsa true, aksi hâlde false döndür. Yalnızca doldurulmuş hücreler kontrol edilir: tahtanın çözülebilir olması gerekmez.

Fonksiyon

isValidSudoku(board: string-array) → boolean

boardstring-array: Her satırda bir dize olmak üzere 9 karakter uzunluğunda 9 dize; 1'den 9'a kadar rakamlar ve boş hücre için .
Döndürürboolean: Hiçbir satır, sütun veya 3 × 3 kutu bir rakamı tekrarlamıyorsa true, aksi takdirde false

Kısıtlar

board.length == 9 ve board[i].length == 9
board[i][j], 1 ile 9 arasında bir rakam veya . değeridir
Tahtayı tamamlamak imkânsız olabilir; yalnızca doldurulmuş hücreler arasındaki tekrarlar önemlidir.

Örnekler

Girdi: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Çıktı: true
Açıklama: 0'dan başlayarak sayılan 4. satırda, .74..89.3, 7, 4, 8, 9 ve 3 sayılarının her biri bir kez bulunur ve diğer 26 grubun hiçbirinde de bir rakam tekrarlanmaz.

Girdi: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Çıktı: false
Açıklama: 0. satır ve 7. satır 3 ile başlıyor, bu yüzden 0. sütunda iki tane 3 var. Aynı satırı veya kutuyu paylaşmıyorlar, bu nedenle bunu yalnızca sütun kontrolü yakalıyor.

Girdi: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Çıktı: false
Açıklama: 0. satır, 8. sütundaki 5 ile 2. satır, 7. sütundaki 5 aynı satırda veya sütunda değil, ancak ikisi de sağ üst kutuda yer alıyor; bu nedenle yanıt false.

Ek soru

4 × 4 kutulara ve 1'den 9'a, A'dan G'ye kadar sembollere sahip 16 × 16'lık bir tahtayı nasıl kontrol edersin? Kutu formülü neye dönüşür?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her rakam üç gruba aittir: bulunduğu satır, sütun ve 3 × 3 kutu. Satır ve sütunları indekslemek kolaydır; hataların kaynağı kutudur. Kutuları (r / 3) * 3 + c / 3 ile 0'dan 8'e kadar numaralandırın ve 81 hücrenin üzerinden tek bir geçişle 27 grubun tamamını kontrol edin.

Her satırı, sütunu ve kutuyu ayrı ayrı kontrol edin

Sezgi

Kural 27 grup adlandırır: 9 satır, 9 sütun ve 9 kutu. Her birinin dokuz hücresini toplayın ve noktaları yok sayarak yinelenen bir rakam olup olmadığına bakın. Tahta, hiçbir grupta yinelenen rakam yoksa geçerlidir.

Her rakam için bir görüldü işareti, dokuz hücre arasındaki tekrarları bulur. 81 hücrenin her biri üç grubunun her biri için bir kez okunur: sabit miktarda iş. n × n boyutundaki bir tahtada aynı yöntemin maliyeti O(n²) olur.

Algoritma

i için 0'dan 8'e kadar, i. satırı, i. sütunu ve i. kutuyu topla.
i. kutunun köşesi 3 * (i / 3). satırda, 3 * (i % 3). sütundadır; k. hücre, bu köşenin k / 3 satır aşağısında ve k % 3 sütun sağındadır.
Her grubu yeni görülme işaretleriyle dolaş ve noktaları atla. Bir rakam zaten işaretliyse false döndür.
27 grubun tamamından sonra true döndür.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

Satır, sütun ve kutu başına bir kez geçiş ve görülenler tablosu

Sezgi

Her hücreyi bir kez ziyaret et ve üç sorunun tümünü birlikte sor. Bayraklar için üç adet 9 × 9 tablo tut: seenRow[r][d], d+1 rakamının r satırında zaten bulunduğunu belirtir; seenCol ve seenBox da aynı şekilde çalışır.

(r, c) hücresi (r / 3) * 3 + c / 3 kutusuna aittir. İlk kısım üç kutuluk bandı seçer, c / 3 ise bandın içindeki kutuyu seçer. (4, 7) hücresi 1 * 3 + 2 = 5 kutusuna, yani ortadaki sağ kutuya düşer.

Zaten işaretlenmiş bir bayrak, rakamın o grupta tekrarlandığı anlamına gelir. Her hücre bir kez okunur ve tablolar 243 bayrak tutar: burada zaman ve bellek sabittir; n × n boyutundaki bir tahtada O(n²).

Algoritma

seenRow, seenCol ve seenBox oluşturun; her biri 9 × 9 boyutunda ve tüm değerleri false olsun.
Dolu her hücre için (r, c), d değerini rakamının 1 eksiği ve b = (r / 3) * 3 + c / 3 olarak belirleyin.
seenRow[r][d], seenCol[c][d] veya seenBox[b][d] ayarlanmışsa false döndürün; aksi hâlde üçünü de ayarlayın.
Son hücreden sonra true döndürün.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Tuzaklar ve uç durumlar

Kutuyu r / 3 + c / 3 olarak hesaplamak. Bu yalnızca 0 ile 4 arasında değerler verir; dolayısıyla kutuları farklı olsa da (0, 3) ve (3, 0) aynı sayıyı paylaşır ve oradaki iki 7 tekrar olarak bildirilir.
JavaScript, Python 3 veya Lua'da / ile bölmek; bu dillerde 4 / 3, 1.33 eder. Aşağı yuvarlayın.
. karakterini bir değer olarak ele almak. Her satırında dokuz nokta bulunan boş bir tahta geçerlidir.
Bulmacayı çözmeye çalışmak. 8. sütunda daha aşağıda bir 9 bulunan 12345678. satır 0'ı asla tamamlanamaz, ancak hiçbir şey tekrarlanmaz: true.
3×3 kutuları atlamak. Her satırı bir üst satırın bir basamak sola kaydırılmış hâli olan dolu bir ızgarada hiçbir satırda veya sütunda tekrar olmaz; ancak her kutuda tekrarlar bulunur.

Sıkça sorulan sorular3

Valid Sudoku'nun zaman karmaşıklığı nedir?

Tahtada her zaman 81 hücre bulunur; bu nedenle her iki yaklaşım da O(1) zamanda çalışır ve O(1) bellek kullanır. Genel bir n × n Sudoku için tek geçişli kontrol, n² hücrenin her birini bir kez okur ve 3n² bayrak tutar: O(n²) zaman ve bellek.

Geçerli bir Sudoku tahtasının çözülebilir olması gerekir mi?

Hayır. Burada geçerli olması, yalnızca doldurulmuş hücreler arasında aynı satırda, sütunda veya 3 × 3'lük kutuda hiçbir rakamın tekrarlanmaması anlamına gelir. Bir tahta bu denetimi geçip yine de çözümsüz olabilir. Çözülebilir olup olmadığını belirlemek, geri izleme gibi bir arama gerektirir; bu farklı bir problemdir.

Geçerli Sudoku bit maskeleriyle çözülebilir mi?

Evet. Her satıra, sütuna ve kutuya bir tamsayı ver; burada bit d, d+1 rakamının görüldüğü anlamına gelir. Dolu bir hücre için, 1 << d üç maskeden herhangi biriyle AND işleminde sıfırdan farklı bir sonuç verirse rakam tekrarlanır; aksi takdirde bunu üçünün de üzerine OR işlemiyle ekle. Bu, 243 bayrak yerine 27 tamsayı demektir.

def isValidSudoku(board):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Beklenen Çıktı

true