Sudoku Bulmacasını Cebirsel Geometri ile Çözmek

Giriş: Sudoku ve Matematik

Sudoku, dünya çapında popüler olan basit kurallara sahip bir mantık bulmacasıdır. 9x9’luk bir ızgarada, her satır, her sütun ve her 3x3’lük alt kare 1’den 9’a kadar rakamları tam olarak bir kez içermelidir. Genellikle bu bulmacalar deneme yanılma veya daha sistematik geri izleme (backtracking) algoritmalarıyla çözülür.

Peki ya Sudoku’yu daha soyut matematiksel araçlarla, örneğin cebirsel geometri ile modelleyip çözebileceğimizi söylesem? Bu yazıda, Sudoku kısıtlarını polinom denklemlerine dönüştürerek ve bilgisayar cebiri tekniklerini kullanarak bu bulmacaya nasıl farklı bir bakış açısı getirebileceğimizi inceleyeceğiz. Ayrıca, teorik yaklaşımın aksine pratik bir Python çözücüsüne de göz atacağız.

Sudoku Kurallarını Polinomlara Dönüştürmek

Temel fikir, 9x9=81 hücrenin her birini bir x_i değişkeni (burada i 1’den 81’e kadar) olarak temsil etmektir. Amacımız, bu değişkenlerin Sudoku kurallarına uymasını sağlayan bir denklem sistemi kurmaktır.

Cebirsel Model: İdealler ve Varyeteler

Tüm Sudoku kısıtlarını bir araya getiren cebirsel yapıyı ideal kullanarak tanımlarız. K[x_1, ..., x_81] polinom halkasında (burada K genellikle Q (rasyonel sayılar) veya C (karmaşık sayılar) gibi bir cisimdir) şu ideali oluştururuz:

I ideali, tüm F_i(x_i) = 0 denklemleri ve her (i,j) E kümesindeki çift için y_ij * (x_i - x_j) - 1 = 0 denklemleri tarafından üretilir.

Bu idealin sıfırlarının kümesi, yani varyetesi V(I), tüm Sudoku kısıtlarını sağlayan (x_1, ..., x_81) vektörlerinin kümesidir. Sudoku bulmacasının çözümleri tam olarak V(I) içindeki tamsayı koordinatlı noktalardır.

Belirli Bir Bulmacayı Çözmek

Genellikle bir Sudoku bulmacasında bazı hücreler başlangıçta doldurulmuştur. Diyelim ki L, {1, …, 81}‘in bir alt kümesi olmak üzere, L içindeki i indisli hücreler için başlangıç değerleri a_i verilmiş olsun. Bu ek bilgiyi modele katmak için ideali genişletiriz:

I_S ideali, I idealine x_i = a_i başlangıç koşullarının (i L’de olmak üzere) eklenmesiyle oluşturulur.

Eğer Sudoku bulmacasının tek bir çözümü (a_1, ..., a_81) varsa, I_S idealinin indirgenmiş Gröbner bazı (reduced Gröbner basis) şu şekilde olacaktır:

\{x_1 - a_1, x_2 - a_2, ..., x_81 - a_81\}

Gröbner bazları, polinom denklem sistemlerini çözmek için güçlü bir araçtır ve bilgisayar cebiri sistemleri (CAS) kullanılarak hesaplanabilir.

Teori vs. Pratik: Hesaplama Maliyeti

Bu cebirsel yaklaşım teorik olarak çok şık olsa da, 81 değişkenli bir sistem için Gröbner bazı hesaplamak hesaplama açısından aşırı pahalıdır. Pratikte, Sudoku çözmek için çok daha verimli algoritmalar mevcuttur.

En yaygın ve etkili yöntemlerden biri geri izleme (backtracking) algoritmasıdır.

Pratik Bir Yaklaşım: Python ile Geri İzleme Algoritması

Aşağıda, standart bir geri izleme tekniği kullanarak Sudoku çözen basit bir Python programı örneği bulunmaktadır:

1
N = 9
2
EMPTY = 0
3

4
def print_board(board):
5
    """Sudoku tahtasını formatlı yazdırır."""
6
    print("-------------------------")
7
    for i in range(N):
8
        print("| ", end="")
9
        for j in range(N):
10
            if board[i][j] == EMPTY:
11
                print(". ", end="")
12
            else:
13
                print(f"{board[i][j]} ", end="")
14
            if (j + 1) % 3 == 0:
15
                print("| ", end="")
16
        print()
17
        if (i + 1) % 3 == 0:
18
            print("-------------------------")
19

20
def is_valid(board, row, col, num):
21
    """Bir sayının belirli bir hücreye yerleştirilip yerleştirilemeyeceğini kontrol eder."""
22
    # Satır kontrolü
23
    if num in board[row]:
24
        return False
25

26
    # Sütun kontrolü
27
    if num in [board[i][col] for i in range(N)]:
28
        return False
29

30
    # 3x3 blok kontrolü
31
    start_row, start_col = row - row % 3, col - col % 3
32
    for i in range(3):
33
        for j in range(3):
34
            if board[i + start_row][j + start_col] == num:
35
                return False
36

37
    return True
38

39
def find_empty_cell(board):
40
    """Boş bir hücrenin konumunu bulur (satır, sütun)."""
41
    for r in range(N):
42
        for c in range(N):
43
            if board[r][c] == EMPTY:
44
                return r, c
45
    return None # Boş hücre yoksa
46

47
def solve_sudoku(board):
48
    """Sudoku'yu çözen ana geri izleme fonksiyonu."""
49
    find = find_empty_cell(board)
50
    if not find:
51
        return True # Bulmaca çözüldü
52
    else:
53
        row, col = find
54

55
    for num in range(1, 10): # 1-9 arası sayıları dene
56
        if is_valid(board, row, col, num):
57
            board[row][col] = num # Geçerliyse yerleştir
58

59
            if solve_sudoku(board): # Özyinelemeli olarak devam et
60
                return True
61

62
            # Çözüme götürmediyse geri al (backtrack)
63
            board[row][col] = EMPTY
64

65
    return False # Bu hücre için geçerli sayı bulunamadı
66

67
# Ana Kısım (Örnek Kullanım)
68
if __name__ == "__main__":
69
     board = [
70
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
71
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
72
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
73
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
74
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
75
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
76
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
77
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
78
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
79
    ]
80

81
     print("Başlangıçtaki Sudoku:")
82
     print_board(board)
83
     print("\nÇözülüyor...\n")
84

85
     if solve_sudoku(board):
86
         print("Çözülmüş Sudoku:")
87
         print_board(board)
88
     else:
89
         print("Çözüm bulunamadı.")

Bu algoritma, boş bir hücre bulur, 1’den 9’a kadar geçerli bir sayı yerleştirmeyi dener ve özyinelemeli olarak devam eder. Eğer bir noktada tıkanırsa (geçerli sayı bulunamazsa), önceki adıma döner ve farklı bir sayı dener.

Sonuç

Sudoku bulmacasını cebirsel geometri kullanarak modellemek, probleme farklı ve matematiksel olarak zengin bir bakış açısı sunar. Polinomlar, idealler ve Gröbner bazları gibi kavramlar, Sudoku’nun yapısını derinlemesine anlamamızı sağlar. Ancak, hesaplama verimliliği açısından bu teorik yaklaşım, geri izleme gibi standart algoritmik yöntemlerin gerisinde kalır. Yine de, basit bir mantık bulmacasının ardındaki soyut matematiksel yapıları görmek oldukça etkileyicidir!