Sudoku Çözücü

#Nasıl çalışır?

Sudoku, geri izlemenin en tanıdık örneklerinden biridir. n × n bir tabloda her satır, her sütun ve her kutu 1'den n'e kadar rakamları birer kez içermelidir. Bu derste animasyon okunabilir kalsın diye 4 × 4'lük, 2 × 2 kutulu bir bulmaca kullanılıyor; yöntem 9 × 9 için de aynıdır.

Algoritma ilk boş hücreyi bulur ve sırayla 1, 2, … rakamlarını dener. Aynı satırda, sütunda ya da kutuda zaten bulunan bir rakam atlanır. Uygun bir rakam yazılır ve bir sonraki boş hücreye geçilir.

Bir hücre için hiçbir rakam uymazsa önceki bir seçim yanlıştır: son yazılan rakam silinir ve o hücre için sıradaki rakam denenir. Örnek bulmaca tek çözümlüdür ve çözülürken iki kez geri dönmek gerekir.

#Kendin dene

#Adım adım

1. 01İlk boş hücreyi bul; yoksa bulmaca çözüldü.
2. 02Hücreye 1'den n'e kadar rakamları sırayla dene.
3. 03Rakam satır, sütun ve kutu kurallarına uyuyorsa yaz ve bir sonraki boş hücreye geç.
4. 04Hiçbir rakam uymazsa geri dön: önceki hücredeki rakamı sil ve onun sıradaki rakamını dene.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

N, BOX = 4, 2  # a 4 x 4 puzzle with 2 x 2 boxes; the same code solves 9 x 9 with N, BOX = 9, 3

grid = [
    [0, 0, 0, 0],
    [0, 0, 1, 2],
    [2, 0, 0, 4],
    [0, 4, 0, 0],
]


def fits(r: int, c: int, d: int) -> bool:
    if d in grid[r] or any(grid[k][c] == d for k in range(N)):
        return False
    br, bc = r - r % BOX, c - c % BOX
    return all(grid[br + i][bc + j] != d for i in range(BOX) for j in range(BOX))


def solve() -> bool:
    for r in range(N):
        for c in range(N):
            if grid[r][c] == 0:  # the first empty cell
                for d in range(1, N + 1):
                    if fits(r, c, d):
                        grid[r][c] = d
                        if solve():
                            return True
                        grid[r][c] = 0  # dead end: backtrack
                return False
    return True  # no empty cell left


solve()
for row in grid:
    print(" ".join(map(str, row)))

#Karmaşıklık

Teoride üsteldir; pratikte kurallar dalları o kadar erken keser ki 9 × 9 bulmacalar milisaniyeler içinde çözülür. En az seçeneği olan hücreyi önce doldurmak (MRV sezgisi) ve her satır/sütun/kutu için kullanılan rakam kümeleri tutmak aramayı çok hızlandırır.

#Ne zaman kullanılır?

Sudoku ve benzeri bulmacalar (KenKen, Kakuro), kısıt sağlama problemleri, ders ve sınav programları, graf boyama ve kaynak atama problemleri aynı "dene, kontrol et, gerekirse geri al" kalıbıyla çözülür.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.