C&D dilinde 3x3 Sihirli Kare Bulmacası Nasıl Çözülür? Python

Sihirli kare nedir?

Sihirli kare, sayıların özel bir düzenlemeyle yerleştirildiği kare bir matristir. Değerler, her satırda, her sütunda ve her iki ana köşegende toplamın aynı kalacağı şekilde yerleştirilir. Sihirli kareler, eğlence matematiğinde kullanılan basit mantık bulmacalarıdır.

Sihirli karelere örnek:

Yukarıdaki diyagram 3. dereceden bir sihirli kareyi göstermektedir. Her köşegenin, satırın ve sütunun toplamı 15'e eşittir. Sonraki bölümde bu sabit toplamın nasıl elde edildiği açıklanmaktadır.

Sihirli Kareler Nasıl Çalışır?

n. dereceden bir sihirli kare, n² pozitif tamsayı içeren n x n boyutlu bir matristir. Matrisin satır veya sütun sayısına matrisin derecesi denir.

Tipik sihirli kare bulmacaları tek sıralıdır ve 1'den n²'ye kadar olan tamsayıları kullanır. Her satır, sütun ve köşegenin aynı değere toplanması gerektiğinden, bu değere sihirli toplam veya sihirli sabit denir. Sabit yalnızca n'ye bağlıdır. n. dereceden sihirli toplamın formülü şöyledir:

Üçüncü dereceden bir sihirli kareyi ele alalım. Bu durumda sihirli toplam şöyledir:

Bu formül aritmetiği açıklıyor, ancak bulmacanın akılda kalıcı adını veren uzun bir kültürel geçmişi var.

Onlara Neden Büyü Deniyor?

Antik çağ matematikçileri, sayıların ilginç kombinasyonlarından büyülenmişlerdi ve sihirli kare de bunlardan biriydi. En eski kanıtlar MÖ 190 civarına, Çin'e kadar uzanmaktadır.

Araştırmalar, eski Japonya, Hindistan ve Arabistan'da sihirli kare bulmacalarına dair kanıtlar olduğunu göstermektedir. Efsaneler bu düzenlemeleri sihirli dünyayla ilişkilendirmiş ve bu isim kalıcı olmuştur. Halk hikayelerinin ötesinde, matematikçiler de bir kareyi diğerinden ayıran biçimsel kategoriler tanımlamışlardır.

Sihirli Kare Türleri

Matematikte sihirli karelerin çeşitli varyantları vardır:

• Normal Sihirli Kare: İlk n² doğal sayıyı içerir.
• Yarı Sihirli Kare: Sihirli sabite yalnızca satırlar ve sütunların toplamı ulaşır.
• Basit Sihirli Kare: Satırlar, sütunlar ve her iki ana köşegenin toplamı sihirli sabiti oluşturur.
• En Mükemmel Sihirli Kare: İki ek özelliğe sahip normal bir sihirli kare. Matrisin her 2x2 alt karesinin toplamı 2(n²+1)'dir ve n/2 hücre uzaklıktaki herhangi bir sayı çiftinin toplamı n²+1'dir.

Ek özelliklere bağlı olarak daha fazla kategori mevcuttur. Bu eğitimde "sihirli kare" terimi niteleme olmaksızın kullanıldığında, tek sayılı, normal, basit bir sihirli kareyi ifade eder.

Sihirli Kare Oluşturma Algoritması

Tek sayılı sihirli kareler oluşturmak için kullanılan klasik algoritma, Siamese yöntemi olarak adlandırılır ve şu şekildedir:

• İlk sayı (1), ilk koordinatın satır indeksi, ikinci koordinatın ise sütun indeksi olduğu (n/2, n-1) konumunda saklanır. Sonraki adımlar için bu konuma (x, y) diyelim.
• Sonraki sayı (x-1, y+1) konumuna yerleştirilir. Bu konum geçersiz ise aşağıdaki kurallar uygulanır:
  1. Satır indeksi -1 ise, n-1'e kadar devam edin. Sütun indeksi n ise, 0'a kadar devam edin.
  2. Hesaplanan konumda zaten bir sayı varsa, satırı 1 artırın ve sütunu 2 azaltın.
  3. Eğer satır -1 ve sütun aynı anda n ise, yeni konum (0, n-2) olur.

Not: Bu algoritma yalnızca tek sayılı sayılar için geçerli sihirli kareler üretir. Sonuç, ilk n² doğal sayıyı içeren normal bir sihirli karedir. Aynı n için birden fazla geçerli çözüm olabilir.

1'den 9'a kadar olan sayıları kullanan 3. derece ile ilgili küçük bir örnek sayesinde kurallar daha netleşiyor.

3x3 Kare Üzerinde Nasıl Çalışır?

Uygulayarak algoritma Yukarıda belirtilen adımlar şunlardır:

) 1 Adım İlk sayı (1), (3/2, 3-1) veya (1, 2) konumuna yerleştirilir. Sonraki adımlar için x = 1 ve y = 2 olarak ayarlayın.

) 2 Adım Geri kalan sayıların konumları aşağıdaki gibi hesaplanır.

2 numaranın konumu:

Sonraki sayı (x-1, y+1) veya (0, 3) konumuna gitmelidir, ancak bu geçerli bir konum değildir. (a) kuralına göre, sütun 0'a döner ve (0, 0) verir. x = 0, y = 0 olarak ayarlayın.

3 numaranın konumu:

3 numaralı eleman (x-1, y+1) veya (-1, 1) konumunda olmalıdır, ancak bu geçerli bir konum değildir. (a) kuralına göre, satır n-1'e (yani 2'ye) döner. Bu nedenle 3 numaralı eleman (2, 1) konumuna gider. x = 2, y = 1 olarak ayarlayın.

4 numaranın konumu:

4 numaralı sayı (x-1, y+1) veya (1, 2) konumunda olmalıdır; bu geçerlidir ancak zaten 1'i içermektedir. (b) kuralına göre, yeni konum (1+1, 2-2) veya (2, 0)'dır. x = 2, y = 0 olarak ayarlayın.

5 numaranın konumu:

5 numaralı nokta (x-1, y+1) veya (1, 1) konumunda olmalıdır; bu geçerli bir boş konumdur. x = 1, y = 1 olarak ayarlayın.

6 numaranın konumu:

6 numaralı nokta (x-1, y+1) veya (0, 2) konumunda olmalıdır; bu geçerli bir boş konumdur. x = 0, y = 2 olarak ayarlayın.

7 numaranın konumu:

7 numaralı nokta (x-1, y+1) veya (-1, 3) konumunda olmalıdır, bu geçerli değildir. (c) kuralına göre yeni konum (0, n-2) veya (0, 1)'dir. x = 0, y = 1 olarak ayarlayın.

8 numaranın konumu:

8 numaralı nokta (x-1, y+1) veya (-1, 2) konumunda olmalıdır, bu geçerli değildir. (a) kuralına göre, satır 2'ye döner ve (2, 2) verir. x = 2, y = 2 olarak ayarlayın.

9 numaranın konumu:

9 numaralı nokta (x-1, y+1) veya (1, 3) konumunda olmalıdır, bu geçerli değildir. (a) kuralına göre, sütun 0'a döner ve (1, 0) verir.

Her hücre doldurulduğunda, aynı mantık doğrudan sözde koda çevrilir.

Sihirli Kare için Sözde Kod

Begin
    Declare an array of size n*n
    Initialize the array to 0
    Set row = n/2
    Set column = n-1
    For all number i: from 1 to n*n
        If the row = -1 and column = n
            row = 0
            column = n-2
        Else
            If row = -1
                row = n-1
            If column = n
                column = 0
        If the position already contains a number
            decrement column by 2
            increment row by 1
            continue until the position is not 0
        Else
            put the number i into the calculated position
            increment i
        Increment column value
        Decrement row value
End

Sözde kod, aşağıda gösterildiği gibi derlenmiş ve yorumlanmış dillere doğrudan karşılık gelir. C++ hem de Python.

C++ Code Sihirli Kare için

Giriş:

/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;

void GenerateMagicSquare(int n)
{
    int magic[n][n];
    //initializing the array
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            magic[i][j] = 0;
    //setting row and column value
    int i = n / 2;
    int j = n - 1;
    for (int k = 1; k <= n * n;)
    {
        //checking condition (c)
        if (i == -1 && j == n)
        {
            j = n - 2;
            i = 0;
        }
        else
        {
            //checking condition (a)
            if (j == n)
                j = 0;
            if (i < 0)
                i = n - 1;
        }
        //checking condition (b)
        if (magic[i][j])
        {
            j -= 2;
            i++;
            continue;
        }
        else
        {
            //placing the number into the array
            magic[i][j] = k;
            k++;
        }
        //for the next number setting (i-1, j+1)
        j++;
        i--;
    }
    //printing the matrix
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << magic[i][j] << "  ";
        cout << endl;
    }
}
int main()
{
    //This code works for only odd numbers
    int n = 7;
    cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
    GenerateMagicSquare(n);
    return 0;
}

Örnek Çıktısı:

The magic sum is 175

20  12  4  45  37  29  28
11  3  44  36  35  27  19
2  43  42  34  26  18  10
49  41  33  25  17  9  1
40  32  24  16  8  7  48
31  23  15  14  6  47  39
22  21  13  5  46  38  30

MKS Python Aşağıdaki sürüm aynı satır ve sütun kurallarını kullanır.

Python Code Sihirli Kare için

def GenerateMagicSquare(n):
    #initializing the array
    magic = [[0 for x in range(n)]
                for y in range(n)]
    #setting row and column value
    i = n // 2
    j = n - 1
    k = 1
    while k <= (n * n):
        #checking condition (c)
        if i == -1 and j == n:
            j = n - 2
            i = 0
        else:
            #checking condition (a)
            if j == n:
                j = 0
            if i < 0:
                i = n - 1
        #checking conditon (b)
        if magic[i][j]:
            j = j - 2
            i = i + 1
            continue
        else:
            #placing the number into the array
            magic[i][j] = k
            k = k + 1
        #for the next number setting (i-1, j+1)
        j = j + 1
        i = i - 1
    #printing the matrix
    for i in range(0, n):
        for j in range(0, n):
            print('%2d ' % (magic[i][j]),end='')
            if j == n - 1:
                print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)

Örnek Çıktısı:

The magic sum is  175

20 12  4 45 37 29 28
11  3 44 36 35 27 19
 2 43 42 34 26 18 10
49 41 33 25 17  9  1
40 32 24 16  8  7 48
31 23 15 14  6 47 39
22 21 13  5 46 38 30

Her iki uygulama da aynı şekilde çalışır, bu da maliyetlerini karşılaştırmayı kolaylaştırır.

Karmaşıklık Analizi

• Uzay Karmaşıklığı: Sihirli kare n x n'lik bir dizide saklandığı için alan karmaşıklığı O(n²)'dir.
• Zaman Karmaşıklığı: Üretici iki iç içe döngü kullanır. Dış döngü n kez, iç döngü de n kez çalışır, bu nedenle genel zaman karmaşıklığı O(n²)'dir.

SSS