Algoritmalar
tr

Sudoku Çözücü

Geri İzleme O(9^m) O(m)

Boş hücreleri teker teker doldurur; 1–9 rakamlarını dener ve bir rakam kuralları bozduğunda geri izler.

5
6
7
8
9
1
6
7
1
9
5
3
4
8
1
9
8
3
4
5
6
7
5
9
7
6
1
4
2
3
4
6
8
5
3
7
9
7
1
3
9
2
4
8
5
6
9
6
1
5
3
7
2
8
4
8
7
1
9
6
3
5
3
4
5
8
6
1
7
9
Hazır bir bulmaca çözülüyor — rakamların denenip yerleştirilip geri alınışını izleyin.
1/94

(0, 1) konumunda boş göz — doldurulmaya çalışılıyor.

DeğişmezDolu her göz satır, kolon ve kutu kuralını sağlar. Bir rakam ancak kural hâlâ geçerliyken yerleştirilir.

sudoku.c
int valid(int g[9][9], int r, int c, int d) {
    for (int i = 0; i < 9; i++) {
        if (g[r][i] == d || g[i][c] == d)
            return 0;
        if (g[3*(r/3) + i/3][3*(c/3) + i%3] == d)
            return 0;
    }
    return 1;
}
 
int solve(int g[9][9]) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            for (int d = 1; d <= 9; d++) {
                if (valid(g, r, c, d)) {
                    g[r][c] = d;
                    if (solve(g)) return 1;
                    g[r][c] = 0;   /* backtrack */
                }
            }
            return 0;
        }
    }
    return 1;
}

Sudoku Çözücü nasıl çalışır?

Sıradaki boş hücreyi bul, 1–9 rakamlarını dene, kalan ızgarada özyinele ve çıkmaz kanıtlanınca rakamı sil. Kısıt kontrolleri dallanmayı küçük tutar.

Ne zaman kullanılır?

Kısıt sağlama bulmacaları; aynı iskelet planlama ve boyama örneklerini de çözer.