Valid Sudoku

Q: Bir hücrenin hangi 3 × 3 kutuda olduğunu nasıl bulursun?

Tamsayı bölmesiyle, r / 3 satır bandını (0, 1 veya 2), c / 3 ise sütun yığınını belirtir. (r / 3) * 3 + c / 3 , kutuları soldan sağa ve yukarıdan aşağıya 0'dan 8'e kadar numaralandırır. (7, 1) hücresi, sol alttaki 2 * 3 + 0 = 6 numaralı kutudadır.

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

Evet. Her satıra, sütuna ve kutuya bir tam sayı verin ve d bitinin d+1 rakamının görüldüğü anlamına gelmesini sağlayın. Dolu bir hücre için 1 << d hesaplayın; bu değer üç maskeden herhangi biriyle AND işleminden sonra sıfırdan farklıysa rakam tekrarlanmıştır, aksi hâlde üçünün de içine OR işlemiyle ekleyin. Böylece aynı tek geçiş mantığıyla 243 bayrak yerine 27 tam sayı kullanılır.

OrtaHashing

+10

Sana board olarak 9 karakterden oluşan 9 dizelik bir liste, yani 9 × 9'luk bir Sudoku tahtası verilir; her dize bir satırı temsil eder. Her karakter 1 ile 9 arasında bir rakam ya da boş bir hücre için . karakteridir. Aynı satırda, aynı sütunda veya aynı 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 tane olmak üzere, 9 karakterden oluşan 9 dize; 1'den 9'a kadar rakamlar ve boş hücre için .
Döndürürboolean: Hiçbir satırda, sütunda veya 3 × 3 kutuda bir rakam tekrarlanmıyorsa true, aksi halde 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: Her satır, sütun ve kutuda her rakam en fazla bir kez bulunur. 0'dan başlayarak sayıldığında 4. satırdaki .74..89.3 içinde 7, 4, 8, 9 ve 3'ün her biri bir kez bulunur; diğer 26 grup için de aynısı geçerlidir, bu nedenle yanıt true olur.

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ın ikisi de 3 ile başlıyor; bu nedenle 0. sütunda iki tane 3 bulunuyor. İki hücre farklı satırlarda ve farklı kutularda; 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 farklı satırlarda ve farklı sütunlardadır, ancak ikisi de sağ üst kutudadır; bu nedenle yanıt false olur.

Gönderirken +16 gizli test

Ek soru

Kontrolü, 4 × 4 kutulara sahip 16 × 16'lık bir tahtaya ve 1'den 9'a, A'dan G'ye kadar olan sembollere genelleştirin. Kodunuzdaki hangi sayılar tahta boyutuna bağlıdır ve 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 aynı anda üç gruba aittir: satırına, sütununa ve 3 × 3 kutusuna. Satırları ve sütunları indekslemek kolaydır; hataların çoğu kutuda ortaya çıkar. Kutuları (r / 3) * 3 + c / 3 ile 0'dan 8'e kadar numaralandırabilir ve 81 hücrenin üzerinde tek bir geçişle 27 grubun tümünü birlikte kontrol edebilirsin.

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

Sezgi

Kurallar 27 grup tanımlar: 9 satır, 9 sütun ve 9 kutu. Her grubun dokuz hücresini toplayın ve noktaları yok sayarak aralarında bir rakamın tekrarlanıp tekrarlanmadığını kontrol edin. Hiçbir grupta tekrar yoksa tahta geçerlidir.

i satırı board[i][0..8], i sütunu ise board[0..8][i] şeklindedir. Tam sayı bölmesiyle i kutusu 3 * (i / 3) satırında ve 3 * (i % 3) sütununda başlar; dolayısıyla 5. kutu 3. satırda, 6. sütunda başlar. Bu kutudaki k hücresi, köşeden k / 3 satır aşağıda ve k % 3 sütun sağdadır.

Dokuz hücre arasında tekrar bulmak için her rakam için bir görülme bayrağı tutun ve bayrağı zaten ayarlanmış olan ilk rakamda durun. 81 hücrenin her biri, ait olduğu her grup için bir kez olmak üzere üç kez okunur: 243 okuma, sabit miktarda iş. n × n boyutundaki bir tahtada aynı yöntem O(n²) maliyetindedir.

Algoritma

i için 0'dan 8'e kadar, i. satırı, i. sütunu ve i. kutuyu, her biri dokuz hücre olacak şekilde topla.
i. kutu top = 3 * (i / 3) ve left = 3 * (i % 3) konumunda başlar; k. hücresi top + k / 3. satırda, left + k % 3. sütundadır.
Her grup için, noktaları atlayarak hücrelerini yeni görüldü işaretleriyle dolaş.
Bir rakam zaten işaretlenmişse false döndür.
27 grubun tümü tamamlandıktan 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çilenler tablosu

Sezgi

Grupları toplamak yerine her hücreyi bir kez ziyaret edip üç soruyu da aynı anda sor. 9 × 9 boyutunda üç bayrak tablosu tut: seenRow[r][d], d+1 rakamının r satırında zaten bulunduğunu belirtir; seenCol ve seenBox da sütunlar ve kutular için aynı şekilde çalışır.

(r, c) hücresi (r / 3) * 3 + c / 3 kutusuna aittir. İlk kısım üç kutudan oluşan bandı seçer (0–2 satırları 0. bandı, 3–5 satırları 1. bandı, 6–8 satırları 2. bandı verir) ve c / 3 bandın içindeki kutuyu seçer. (4, 7) hücresi 1 * 3 + 2 = 5 kutusuna, yani orta-sağ kutuya düşer.

Dolu her hücre için, üç bayraktan herhangi biri zaten işaretliyse rakam o grupta tekrarlanıyordur ve hemen false döndürürsün. Aksi takdirde üçünü de işaretlersin. Her hücre bir kez okunur ve tablolar 243 bayrak tutar; bu nedenle 9 × 9'luk bir tahta için zaman ve bellek kullanımı sabittir, n × n boyutundaki bir tahta içinse O(n²) olur.

Algoritma

seenRow, seenCol ve seenBox oluştur; her biri 9 × 9 boyutunda ve tüm değerleri false olsun.
Her (r, c) hücresini ziyaret et; nokta içeriyorsa atla.
d, rakam eksi 1 olsun ve b = (r / 3) * 3 + c / 3.
seenRow[r][d], seenCol[c][d] veya seenBox[b][d] true ise false döndür.
Aksi hâlde üçünü de true olarak ayarla. Son hücreden sonra true döndür.

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

Satır ve sütun kontrollerinde nadiren hata olur. Hatalar kutu indeksinde ve neyin tekrar sayıldığında ortaya çıkar.

Kutuyu r / 3 + c / 3 olarak hesaplamak. Bu yalnızca 0 ile 4 arasında değerler verir; dolayısıyla (0, 3) ve (3, 0) hücreleri farklı kutularda olmalarına rağmen aynı sayıyı alır ve bu kutulardaki iki 7 tekrar olarak bildirilir. (r / 3) * 3 + c / 3 kullanın.
4 / 3 işleminin kutu numarası değil 1.33 olduğu JavaScript, Python 3 veya Lua'da / ile bölme yapmak. Math.floor, // veya math.floor kullanın.
. karakterini bir değer olarak kabul etmek. Boş bir tahtada her satırda dokuz nokta bulunur ve tahta geçerlidir.
Bulmacayı çözmeye çalışmak. Satır 0 12345678. ise ve 8. sütunda daha aşağıda bir 9 varsa, satır 0'ın son hücresi doldurulamaz; ancak hiçbir grupta bir rakam tekrarlanmadığından yanıt true olur.
Satırları ve sütunları kontrol edip kutuları kontrol etmemek. Her satırın bir öncekinin bir konum sola kaydırılmış hâli olduğu dolu bir ızgarada hiçbir satırda veya sütunda tekrar yoktur; ancak her kutuda tekrarlar bulunur.

Sıkça sorulan sorular4

Geçerli Sudoku'nun zaman karmaşıklığı nedir?

Tahtada her zaman 81 hücre vardır, 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² işaret tutar; dolayısıyla zaman ve bellek karmaşıklığı O(n²)'dir.

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 kutuda hiçbir rakamın tekrarlanmaması anlamına gelir. Bir tahta bu kontrolden geçip yine de çözümsüz olabilir. Çözülebilir olup olmadığını belirlemek, geri izleme gibi bir arama gerektirir; bu farklı bir problemdir.

Bir hücrenin hangi 3 × 3 kutuda olduğunu nasıl bulursun?

Tamsayı bölmesiyle, r / 3 satır bandını (0, 1 veya 2), c / 3 ise sütun yığınını belirtir. (r / 3) * 3 + c / 3, kutuları soldan sağa ve yukarıdan aşağıya 0'dan 8'e kadar numaralandırır. (7, 1) hücresi, sol alttaki 2 * 3 + 0 = 6 numaralı kutudadır.

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

Evet. Her satıra, sütuna ve kutuya bir tam sayı verin ve d bitinin d+1 rakamının görüldüğü anlamına gelmesini sağlayın. Dolu bir hücre için 1 << d hesaplayın; bu değer üç maskeden herhangi biriyle AND işleminden sonra sıfırdan farklıysa rakam tekrarlanmıştır, aksi hâlde üçünün de içine OR işlemiyle ekleyin. Böylece aynı tek geçiş mantığıyla 243 bayrak yerine 27 tam sayı kullanılır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen

true