Sudoku Solver
Bir sudoku tahtası, dokuz adet 3 × 3 kutuya bölünmüş 9 × 9'luk bir ızgaradır. Çözülmüş bir tahtada her satır, her sütun ve her kutu 1'den 9'a kadar olan rakamların her birini tam olarak bir kez içerir.
Bulmaca, yukarıdan aşağıya her satır için bir tane olmak üzere 9 dizge olarak verilir; . boş bir hücreyi belirtir. Tüm boş hücreleri doldur ve çözülmüş tahtayı aynı biçimde döndür. Tahtanın tam olarak bir çözümü vardır.
Fonksiyon
- boardstring-array
- bulmacanın 9 satırı, her boş hücrede bir nokta
- Döndürürstring-array
- çözülmüş tahtanın 9 satırı
Kısıtlar
board, her biri 9 karakter uzunluğunda 9 dizge tutar.- Her karakter
.veya1ile9arasındaki rakamlardan biridir. - Verilen rakamlar hiçbir satırda, sütunda veya kutuda tekrarlanmaz.
- Tahtanın tam olarak bir çözümü vardır.
Örnekler
- Girdi
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Çıktı
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Açıklama
- Üst satırda
9.7.....6zaten 9, 7 ve 6 bulunduğundan, altı boş hücreye 1, 2, 3, 4, 5 ve 8 gelir. Her birinin nereye geleceğini sütunlar ve kutular belirler ve satır957214386hâline gelir.
Ek soru
Killer sudoku'da hücre kafeslerinin toplamı da verilen değerlere eşit olmalıdır. Bu kuralı aramaya nasıl eklersin ve dalları erkenden budamak için nasıl kullanırsın?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her satırın, her sütunun ve her 3 × 3 kutunun hangi rakamları zaten içerdiğini takip edin. Böylece bir rakamın boş bir hücreye sığıp sığmadığını O(1) sürede belirleyebilirsiniz.
Boş hücreleri teker teker doldurun. Hücreye uyan her rakamı deneyin, sonraki hücreye geçin ve tahtanın geri kalanı bu rakamla tamamlanamıyorsa rakamı geri alın.
Hücrelerin sırası önemlidir. Sırada, geriye en az rakam seçeneği kalan boş hücreyi doldurun: tek seçeneği olan bir hücre dallanma gerektirmez; hiç seçeneği olmayan bir hücre ise hemen geri dönmeniz gerektiğini gösterir.
Çözüm
Geri izleme ile çöz: uyan bir rakam yerleştir, devam et ve tahta tamamlanamıyorsa bu rakamı geri al. Hücrelerin sırası hızı belirler. Zor bir tahtada, okuma sırasını izlemek yüz milyonlarca kısmi tahtayı ziyaret edebilir; en az seçeneği olan hücreyi önce doldurmak ise yaklaşık yüz tane ziyaret eder.
Okuma sırasına göre geri izleme
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Boş hücreleri okuma sırasına göre, her birine uyan en küçük rakamı yazarak doldur. Bir hücre için kullanılabilecek rakam kalmadığında önceki hücreye dön ve sıradaki rakamı dene. Kurallara uyan her kombinasyon sırayla denenir; böylece arama çözümü bulur.
Üç tablo, her uyum testini O(1) yapar: rowUsed[r][d], colUsed[c][d] ve boxUsed[b][d]; burada kutu b = (r / 3) * 3 + c / 3 şeklindedir. Bir rakam yerleştirmek üç girdiyi ayarlar, rakamı kaldırmak ise bunları temizler.
Sabit sıra zayıf noktadır: arama, bir satırı yerel olarak uyan rakamlarla doldurabilir ve daha sonra birçok hücrenin onlara yer bırakmadığını öğrenebilir. Üst sıralarında neredeyse hiç ipucu olmayan ve yanıtlarında büyük rakamlar bulunan bir tahta, aramanın 300 milyondan fazla kısmi tahtayı incelemesine yol açar.
Algoritma
- Tahtayı, boş hücreler için 0 kullanarak bir ızgaraya aktar,
rowUsed,colUsedveboxUseddeğerlerini doldur ve boş hücreleri okuma sırasına göre listele. backtrack(k):kboş hücre sayısına eşitse true döndür.- Hücre
k'nin satırında, sütununda ve kutusunda kullanılmayan 1 ile 9 arasındaki herdrakamı için rakamı yerleştir, işaretle vebacktrack(k+1)true döndürürse true döndür; aksi takdirde işareti kaldır. - Hiçbir rakam işe yaramazsa hücreyi temizle ve false döndür.
backtrack(0)çağır ve ızgarayı yeniden dizelere dönüştür.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Önce en boş hücreyi doldur
Sezgi
Çözüm, doldurma sırasına bağlı değildir; bu nedenle aramayı küçük tutan sırayı seçin: her adımda, izin verilen rakam sayısı en az olan boş hücreyi doldurun. İzin verilen tek bir rakamı olan hücre zorunludur ve yeni bir dal oluşturmaz. Hiç rakama izin verilmeyen hücre hemen seçilir; böylece yanlış bir tahta anında yakalanır.
Her adımda 81 hücre için izin verilen rakamları hızlıca saymak amacıyla her satırı, sütunu ve kutuyu bir bit maskesi olarak saklayın: rows[r] içindeki d biti, d rakamı r satırındaysa ayarlanır. Bir hücre ~(rows[r] | cols[c] | boxes[b]) & 0x3FE rakamlarına izin verir; burada 0x3FE, 1'den 9'a kadar olan bitleri tutar ve sayı, ayarlanmış bitlerin sayısıdır. d rakamını yerleştirmek üç maskede de d bitini ayarlar; özel veya işlemi bu biti kaldırır.
Algoritma
- Verilen rakamlardan ızgarayı ve
rows,colsveboxesmaskelerini oluştur. backtrack(): Tüm hücreleri tara, her boş hücre için izin verilen rakamları hesapla ve izin verilen rakam sayısı en az olan ilk hücreyi seç. Boş hücre yoksa true döndür.- Bu hücre için izin verilen her rakamı yerleştir, üç maskede de bitini ayarla ve
backtrack()true döndürürse true döndür; aksi takdirde bitleri temizle. - Hiçbir rakam işe yaramazsa hücreyi boşalt ve false döndür.
backtrack()işlevini çağır ve ızgarayı yeniden dizelere dönüştür.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Tuzaklar ve uç durumlar
- Bir rakamı geri alırken satır, sütun ve kutu kayıtlarından silmeyi unutmak. Sonraki hücreler bu rakamı kullanılmış olarak görür ve arama çözümü bulamaz.
- Kutu için
r / 3 + c / 3kullanmak.(0, 4)ve(4, 0)hücrelerinin ikisi de 1 değerine karşılık gelir; böylece iki kutu aynı kaydı paylaşır ve tahta asla doldurulamaz. Tam sayı bölmesiyle(r / 3) * 3 + c / 3kullanın. - İlk çözümde durmamak. Sonra siz tahtayı okumadan önce geri alma adımları tahtayı yeniden boşaltır.
Sıkça sorulan sorular3
Geri izlemeli bir sudoku çözücünün zaman karmaşıklığı nedir?
En kötü durumda üsteldir; O(9^m) için m boş hücre bulunur, çünkü her hücre en fazla 9 rakama dallanabilir. Gerçek bulmacalarda satır, sütun ve kutu kuralları dallanmaların çoğunu budar; önce en boş hücreyi doldurmak da geri kalanların çoğunu budar.
Bir sudokunun tam olarak bir çözümü olduğunu nasıl kontrol edersin?
Aynı geri izleme aramasını çalıştırın, ancak çözümleri sayın ve sayı 2'ye ulaştığında durun. Sayının 1 olması bulmacanın tek bir çözümü olduğu, 0 olması ise çözümü olmadığı anlamına gelir. Bulmaca oluşturucular, her ipucunu kaldırdıktan sonra bu kontrolü çalıştırır.
Sudoku çözmenin geri izleme yönteminden daha hızlı bir yolu var mı?
En hızlı çözücüler bile geri izleme yapar, ancak her tahminden önce daha fazla çıkarımda bulunur. Kısıt yayılımı, her hücreyi tek bir seçenekle ve satırında, sütununda veya kutusunda yalnızca tek bir hücreye sığan her rakamla doldurur, ardından işlemi tekrarlar. Sudoku, tam örtü problemi olarak da ifade edilebilir ve Knuth'un Algorithm X algoritmasıyla çözülebilir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def solveSudoku(board):
# Kodu buraya yazınTest #1
Argüman
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Beklenen Çıktı
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]