Cara Memecahkan Teka-Teki Kotak Ajaib 3×3 dalam Bahasa C & Python

Apa itu Kotak Ajaib?

Kotak ajaib adalah matriks persegi dengan susunan angka khusus. Nilai-nilai tersebut ditempatkan sedemikian rupa sehingga jumlah di setiap baris, setiap kolom, dan kedua diagonal utama tetap sama. Kotak ajaib adalah teka-teki logika sederhana yang digunakan dalam matematika rekreasi.

Contoh kotak ajaib:

Diagram di atas menunjukkan persegi ajaib berordo 3. Jumlah setiap diagonal, baris, dan kolom sama dengan 15. Bagian selanjutnya menjelaskan bagaimana total konstan ini dihasilkan.

Cara Kerja Kotak Ajaib

Persegi ajaib berordo n adalah matriks n x n yang berisi n² bilangan bulat positif. Jumlah baris atau kolom disebut ordo matriks.

Teka-teki persegi ajaib biasanya memiliki urutan ganjil dan menggunakan bilangan bulat dari 1 hingga n². Karena setiap baris, kolom, dan diagonal harus berjumlah sama, nilai tersebut disebut jumlah ajaib atau konstanta ajaib. Konstanta tersebut hanya bergantung pada n. Rumus untuk jumlah ajaib orde n adalah:

Perhatikan sebuah persegi ajaib berordo 3. Jumlah ajaibnya adalah:

Rumus ini menjelaskan perhitungan aritmatika, tetapi teka-teki ini memiliki sejarah budaya yang panjang yang memberinya nama yang mudah diingat.

Mengapa Disebut Sihir?

Para matematikawan kuno terpesona oleh kombinasi angka yang menarik, dan persegi ajaib adalah salah satunya. Bukti paling awal berasal dari Tiongkok sekitar tahun 190 SM.

Penelitian menunjukkan bukti adanya teka-teki persegi ajaib di Jepang kuno, India, dan Arab. Legenda mengaitkan susunan ini dengan dunia magis, dan nama itu pun melekat. Di luar cerita rakyat, para matematikawan juga telah mendefinisikan kategori formal yang membedakan satu persegi dari persegi lainnya.

Jenis Kotak Ajaib

Ada beberapa varian persegi ajaib dalam matematika:

• Kotak Ajaib Normal: Berisi n² bilangan asli pertama.
• Kotak Semi Ajaib: Hanya baris dan kolom yang jika dijumlahkan akan menghasilkan konstanta ajaib tersebut.
• Kotak Ajaib Sederhana: Jumlah baris, kolom, dan kedua diagonal utama sama dengan konstanta ajaib tersebut.
• Kotak Ajaib Paling Sempurna: Sebuah persegi ajaib biasa dengan dua sifat tambahan. Setiap sub-persegi 2x2 dari matriks tersebut berjumlah 2(n²+1), dan setiap pasangan angka yang berjarak n/2 sel akan berjumlah n²+1.

Terdapat lebih banyak kategori berdasarkan properti tambahan. Setiap kali istilah "persegi ajaib" digunakan tanpa kualifikasi dalam tutorial ini, yang dimaksud adalah persegi ajaib normal, sederhana, dan berordo ganjil.

Algoritma untuk Menghasilkan Persegi Ajaib

Algoritma klasik untuk menghasilkan persegi ajaib berordo ganjil, yang disebut metode Siamese, adalah sebagai berikut:

• Angka pertama (1) disimpan pada posisi (n/2, n-1), di mana koordinat pertama adalah indeks baris dan koordinat kedua adalah indeks kolom. Untuk langkah selanjutnya, sebut posisi ini (x, y).
• Angka berikutnya ditempatkan pada (x-1, y+1). Jika posisi tersebut tidak valid, terapkan aturan berikut:
  1. Jika indeks baris adalah -1, putar kembali ke n-1. Jika indeks kolom adalah n, putar kembali ke 0.
  2. Jika posisi yang dihitung sudah berisi angka, tambahkan 1 pada baris dan kurangi 2 pada kolom.
  3. Jika barisnya adalah -1 dan kolomnya adalah n pada saat yang bersamaan, maka posisi barunya adalah (0, n-2).

Catatan: Algoritma ini hanya menghasilkan kotak ajaib valid berordo ganjil. Hasilnya adalah kotak ajaib biasa yang berisi n² bilangan asli pertama. Mungkin ada lebih dari satu solusi valid untuk n yang sama.

Aturan-aturan tersebut menjadi lebih jelas melalui contoh kecil dengan urutan 3, yang menggunakan angka 1 hingga 9.

Cara Kerjanya pada Persegi 3x3

Menerapkan algoritma Berikut langkah-langkahnya:

Langkah 1) Angka pertama (1) ditempatkan pada (3/2, 3-1) atau (1, 2). Untuk langkah selanjutnya, tetapkan x = 1 dan y = 2.

Langkah 2) Posisi angka-angka yang tersisa dihitung sebagai berikut.

Posisi nomor 2:

Angka berikutnya seharusnya berada di (x-1, y+1) atau (0, 3), yang bukan posisi yang valid. Berdasarkan aturan (a), kolom akan kembali ke 0, sehingga menjadi (0, 0). Tetapkan x = 0, y = 0.

Posisi nomor 3:

Nomor 3 seharusnya berada di (x-1, y+1) atau (-1, 1), yang bukan posisi yang valid. Berdasarkan aturan (a), baris tersebut akan kembali ke n-1 (yaitu 2). Jadi nomor 3 berada di (2, 1). Tetapkan x = 2, y = 1.

Posisi nomor 4:

Nomor 4 seharusnya berada di (x-1, y+1) atau (1, 2), yang valid tetapi sudah berisi 1. Berdasarkan aturan (b), posisi barunya adalah (1+1, 2-2) atau (2, 0). Tetapkan x = 2, y = 0.

Posisi nomor 5:

Nomor 5 seharusnya berada di (x-1, y+1) atau (1, 1), yang merupakan posisi kosong yang valid. Tetapkan x = 1, y = 1.

Posisi nomor 6:

Nomor 6 seharusnya berada di (x-1, y+1) atau (0, 2), yang merupakan posisi kosong yang valid. Tetapkan x = 0, y = 2.

Posisi nomor 7:

Nomor 7 seharusnya berada di (x-1, y+1) atau (-1, 3), yang tidak valid. Berdasarkan aturan (c), posisi barunya adalah (0, n-2) atau (0, 1). Tetapkan x = 0, y = 1.

Posisi nomor 8:

Nomor 8 seharusnya berada di (x-1, y+1) atau (-1, 2), yang tidak valid. Berdasarkan aturan (a), baris tersebut melingkar ke 2, sehingga menjadi (2, 2). Tetapkan x = 2, y = 2.

Posisi nomor 9:

Nomor 9 seharusnya berada di (x-1, y+1) atau (1, 3), yang tidak valid. Berdasarkan aturan (a), kolom tersebut akan kembali ke 0, sehingga menghasilkan (1, 0).

Dengan setiap sel terisi, logika yang sama dapat diterjemahkan langsung ke dalam kode semu.

Kode semu untuk Kotak Ajaib

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

Kode semu tersebut dipetakan langsung ke bahasa yang dikompilasi dan diinterpretasikan, seperti yang akan ditunjukkan selanjutnya pada C++ ke Python.

C++ Code untuk Kotak Ajaib

Memasukkan:

/*
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;
}

Keluaran Contoh:

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

The Python Versi di bawah ini menggunakan aturan baris dan kolom yang identik.

Python Code untuk Kotak Ajaib

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)

Keluaran Contoh:

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

Kedua implementasi tersebut berperilaku identik, sehingga mudah untuk membandingkan biayanya.

Analisis Kompleksitas

• Kompleksitas Ruang: Kotak ajaib tersebut disimpan dalam array n x n, sehingga kompleksitas ruangnya adalah O(n²).
• Kompleksitas Waktu: Generator ini menggunakan dua loop bersarang. Loop luar berjalan n kali, dan loop dalam juga berjalan n kali, sehingga kompleksitas waktu keseluruhannya adalah O(n²).

Pertanyaan Umum Demo Slot