Kotak Ajaib – Pecahkan Puzzle 3×3 menggunakan C & Python contoh
Sarah Chen
Apa itu Magic Square?
Kotak ajaib adalah matriks persegi dengan susunan angka khusus. Angka-angka ini disusun sedemikian rupa sehingga jumlah angka pada setiap diagonal, baris, dan kolom tetap sama. Permainan kotak ajaib adalah teka-teki logika sederhana yang digunakan dalam matematika rekreasi.
Contoh kotak ajaib:
Diagram di atas adalah contoh persegi ajaib berorde 3. Jumlah diagonal, baris, dan kolomnya adalah 15.
Cara kerja Kotak Ajaib
Kotak ajaib adalah matriks n*n yang terdiri dari n^2 bilangan bulat positif. Jumlah baris atau kolom matriks persegi disebut orde matriks.
Biasanya, teka-teki kotak ajaib memiliki urutan ganjil dan memuat bilangan bulat dari 1 hingga n^2. Jumlah setiap diagonal, baris, dan kolom adalah sama. Angka ini disebut jumlah ajaib atau konstanta ajaib. Umumnya, jumlah ajaib ini bergantung pada urutan matriks. Rumus kotak ajaib untuk jumlah ajaib orde n adalah-
Mari kita ambil contoh kotak ajaib dengan bilangan bulat 3. Jadi, jumlah ajaibnya adalah-
Mengapa disebut Ajaib?
Matematikawan kuno terpesona oleh sifat beberapa kombinasi angka yang menarik. Kotak ajaib adalah salah satunya. Bukti paling awal mengenai kotak ajaib berasal dari Tiongkok pada tahun 190 SM.
Beberapa penelitian menunjukkan bukti adanya teka-teki kotak ajaib di Jepang, India, dan Arab kuno. Berdasarkan beberapa legenda, diasumsikan bahwa formasi angka khusus tersebut terhubung dengan dunia magis. Oleh karena itu, kotak-kotak tersebut dinamakan kotak ajaib.
Jenis Kotak Ajaib
Ada beberapa varian matematika kotak ajaib –
- Kotak Ajaib Normal: Kotak ajaib jenis ini berisi n^2 angka pertama.
- Kotak Semi Ajaib: Pada tipe ini, hanya baris dan kolom yang berjumlah konstanta ajaib.
- Kotak Ajaib Sederhana: Berbeda dengan tipe sebelumnya, baris, kolom, dan kedua diagonal dijumlahkan dengan konstanta ajaib.
- Kotak Ajaib Paling Sempurna: Ini adalah kotak ajaib biasa dengan dua sifat khusus. Di sini, setiap subkotak 2x2 dari matriks berjumlah total 2(n^2+1). Dan setiap pasangan angka yang berjarak n/2 kotak dari kisi berjumlah n^2+1.
Berdasarkan sifatnya, ada banyak jenis kotak ajaib. Namun, setiap kali kita hanya menyebutkan kotak ajaib, kita berasumsi bahwa kotak ajaib tersebut adalah kotak ajaib normal dan sederhana dengan orde ganjil.
Algoritma untuk Menghasilkan Kotak Ajaib
Algoritma untuk menghasilkan kotak ajaib berorde ganjil adalah:
- Angka pertama atau 1 akan disimpan di (n/2, n-1), di mana koordinat pertama adalah posisi baris, dan koordinat kedua adalah posisi kolom. Untuk langkah selanjutnya, mari kita nyatakan posisi ini sebagai (x, y).
- Angka-angka berikutnya akan disimpan di (x-1, y+1). Jika posisinya tidak valid, maka kami akan mempertimbangkan kondisi berikut.
- Jika posisi baris -1 maka akan melengkung ke n-1. Demikian pula, jika posisi kolom terhitung adalah n, maka akan melengkung ke 0.
- Posisi baris akan bertambah 1, dan posisi kolom akan berkurang 2 jika posisi terhitung sudah berisi angka.
- Jika posisi baris adalah -1 dan posisi kolom yang bersangkutan adalah n, maka posisi barunya adalah (0, n-2.
Catatan: Algoritma ini hanya menghasilkan kotak ajaib yang valid dengan urutan ganjil. Kami juga menganggap kotak ajaib ini sebagai kotak ajaib normal dengan n^2 angka pertama. Selain itu, dapat ada beberapa solusi untuk nilai n yang sama.
Mari kita ambil contoh dan lihat cara kerjanya. Katakanlah kita ingin mencari persegi ajaib berorde 3. Karena persegi ajaib tersebut merupakan persegi ajaib sederhana dan normal berorde ganjil, maka persegi tersebut akan memuat semua angka dari 1 hingga 3^2 atau 9.
Bagaimana cara kerjanya?
menurut kami algoritma, langkah-langkahnya adalah sebagai berikut:
Langkah 1) Angka pertama atau 1 akan berada di posisi (3/2, 3-1) atau (1, 2). Berdasarkan konvensi, pertimbangkan x= 1 dan y= 2 untuk langkah selanjutnya.
Langkah 2) Posisi untuk sisa angka akan dihitung dengan cara berikut-
Posisi nomor 2:
Angka berikutnya berada di (x-1, y+1) atau (0, 3), yang bukan merupakan posisi valid. Dengan menggunakan kondisi (a), posisi valid yang bersangkutan adalah (0,0). Jadi, x= 0, y= 0.
Posisi nomor 3:
Angka 3 akan berada pada (x-1, y+1) atau (-1, 1), yang bukan merupakan posisi yang valid. Dengan menggunakan kondisi (a), posisi baris yang valid adalah n-1 atau 2. Jadi, angka 3 berada di (2, 1). Untuk bilangan berikutnya, x= 2, y= 1.
Posisi nomor 4:
Angka 4 harus berada pada (x-1, y+1) atau (1, 2) yang merupakan posisi yang valid. Namun posisi itu sudah memuat angka. Berdasarkan kondisi (b), posisi yang valid adalah (1+1, 2-2) atau (2,0). Untuk bilangan berikutnya x= 2, y= 0.
Posisi nomor 5:
Angka 5 harus berada pada (x-1, y+1) atau (1, 1) yang merupakan posisi yang valid. Untuk bilangan berikutnya x= 1, y= 1.
Posisi nomor 6:
Angka 6 harus berada pada (x-1, y+1) atau (0, 2) yang merupakan posisi yang valid. Untuk bilangan berikutnya x= 0, y= 2.
Posisi nomor 7:
Angka 7 seharusnya berada pada (x-1, y+1) atau (-1, 3) yang bukan merupakan posisi yang sah. Berdasarkan kondisi (c), posisi yang valid adalah (0, n-2) atau (0, 1). Untuk bilangan berikutnya x= 0, y= 1.
Posisi nomor 8:
Angka 8 harusnya berada pada (x-1, y+1) atau (-1, 2) yang bukan merupakan posisi yang sah. Dengan menggunakan kondisi (a), posisi yang valid adalah (2, 2). Untuk bilangan berikutnya x= 2, y= 2.
Posisi nomor 9:
Angka 9 seharusnya berada pada (x-1, y+1) atau (1, 3) yang bukan merupakan posisi yang sah. Dengan menggunakan kondisi (a), posisi yang valid adalah (1, 0).
Kode semu
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
C++ Kode 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
Python Kode 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
Analisis Kompleksitas
- Kompleksitas Ruang: Untuk mempertahankan matriks persegi ajaib, kita memerlukan array *n. Jadi, kompleksitas ruangnya adalah O(n^2).
- Kompleksitas Waktu: Kode yang kami gunakan untuk menghasilkan kotak ajaib terdiri dari dua putaran. Putaran luar berjalan selama n kali, dan putaran dalam juga berjalan selama n kali. Pada akhirnya, kompleksitas waktunya adalah O(n^2).
