Solusi: Forming a Magic Square

Intro

Kali ini kita akan menyelesaikan sebuah permasalahan algoritma matematika yang bernama magic square, kita akan membuat program yang akan menghitung dan menyelesaikan permasalahan ini secara otomatis dan efisien. Referensi permasalahan ini bisa di lihat melalui link ini.

Apa itu Magic Square?

Magic square adalah persegi yang berisi angka/bilangan di setiap kotaknya dan jika bilangan tersebut dijumlahkan pada setiap baris, kolom, dan diagonalnya menghasilkan angka yang sama. Lebih jelas lihat gambar berikut

Magic Square

Permasalahan Magic Square

Kita diberikan sebuah kotak yang direpresentasikan dengan matriks 3x3 dengan angka yang terdiri dari 1-9, kita bisa mengubah angka pada setiap matrik tersebut dengan angka apapun agar hasilnya menjadi Magic Square dengan cost yang terendah. Cost disini maksudnya nilai perubahan terkecil, contoh jika 5 diganti 3, 4 diganti 7 maka nilai cost-nya adalah 5

|5-3| + |4-7| = 5

Contoh Permasalahan

Diberikan nilai matriks 3x3 dengan nilai

$s = [[5, 3, 4], [1, 5, 8], [6, 4, 2]]

Jadi jika dalam bentuk kotak akan terlihat seperti ini

Kotak persegi ini masih belum bisa dikatakan magic square karena penjumlahan setiap baris, kolom, dan diagonalnya tidak sama jadi perlu diubah menjadi magic square dengan mengganti beberapa angka/bilangan pada kotak tersebut.

Berikut adalah hasil perubahan yang sudah menjadi magic square

Jika diperhatikan ada beberapa perubahan angka dari 5 -> 8, 8 -> 9, dan 4 -> 7. Kemudian kita hitung cost yang dibutuhkan untuk melakukan perubahan tersebut

|5-8| + |8-9| + |4-7| = 7

Maka hasilnya adalah 7.

Contoh Lainnya

Input:

$s = [[4, 9, 2], [3, 5, 7], [8, 1, 5]]

Output: 1

Penjelasan: 5 diganti 6

|5-6| = 1

Kemudian bagaimana cara menyelesaikan permasalahan ini?

Solusi Magic Square

Coba perhatikan cara kerja magic square penjumlahan setiap baris, kolom, dan diagonal selalu menghasilkan angka 15. Dan untuk kasus ini kita hanya diberikan angka 1-9. Jadi kita bisa tulis penjumlahan 3 angka yang menghasilkan 15. Hasilnya sebagai berikut:

# 1 + 5 + 9 = 15
# 3 + 5 + 7 = 15
# 2 + 5 + 8 = 15
# 4 + 5 + 6 = 15
# 1 + 8 + 6 = 15
# 2 + 4 + 9 = 15
# 2 + 6 + 7 = 15
# 3 + 8 + 4 = 15

Setelah semua peluang ditulis dari bilangan 1-9 yang bisa menghasilkan penjumlahan bernilai 15, kita bisa tau apa saja peluang terbentuknya magic square dari bilangan 1-9. Kita gunakan daftar ini untuk membentuk baris, kolom, dan diagonal. Contoh angka 8, 5, 2 jika dalam kotak akan bisa berada di posisi:

# 8 * *
# * 5 *
# * * 2

# * * 8
# * 5 *
# 2 * *

Dan hasilnya ada 8 kemungkinan magic square yang bisa terbentuk, daftarnya adalah sebagai berikut:

# 8 3 4
# 1 5 9
# 6 7 2
# [[8,3,4], [1,5,9], [6,7,2]]

# 6 7 2
# 1 5 9
# 8 3 4
# [[6,7,2], [1,5,9], [8,3,4]]

# 4 3 8 
# 9 5 1
# 2 7 6
# [[4,3,8], [9,5,1], [2,7,6]]

# 2 7 6 
# 9 5 1
# 4 3 8
# [[2,7,6], [9,5,1], [4,3,8]]

# 8 1 6
# 3 5 7
# 4 9 2
# [[8,1,6], [3,5,7], [4,9,2]]

# 6 1 8
# 7 5 3
# 2 9 4
# [[6,1,8], [7,5,3], [2,9,4]]

# 4 9 2
# 3 5 7
# 8 1 6
# [[4,9,2], [3,5,7], [8,1,6]]

# 2 9 4
# 7 5 3
# 6 1 8
# [[2,9,4], [7,5,3], [6,1,8]]

Selanjutnya lakukan perbandingan semua kemungkinan ini dengan input nilai matriks 3x3 yang diberikan dan hitung cost yang diberikan pada setiap bilangannya, jika hasil cost-nya terkecil maka gunakan angka itu sebagai output.

Hasil code-nya akan seperti ini:

def formingMagicSquare(s):
    
    possible_square = [
        [[8,3,4], [1,5,9], [6,7,2]],
        [[6,7,2], [1,5,9], [8,3,4]],
        [[4,3,8], [9,5,1], [2,7,6]],
        [[2,7,6], [9,5,1], [4,3,8]],
        [[8,1,6], [3,5,7], [4,9,2]],
        [[6,1,8], [7,5,3], [2,9,4]],
        [[4,9,2], [3,5,7], [8,1,6]],
        [[2,9,4], [7,5,3], [6,1,8]]
    ]
    
    cost = None
    
    for a in range(8):
        temp = 0
        temp = abs(s[0][0] - possible_square[a][0][0]) + abs(s[0][1] - possible_square[a][0][1]) + abs(s[0][2] - possible_square[a][0][2])
        temp += abs(s[1][0] - possible_square[a][1][0]) + abs(s[1][1] - possible_square[a][1][1]) + abs(s[1][2] - possible_square[a][1][2])
        temp += abs(s[2][0] - possible_square[a][2][0]) + abs(s[2][1] - possible_square[a][2][1]) + abs(s[2][2] - possible_square[a][2][2])
        
        if cost is None:
            cost = temp
        
        if cost is not None:
            if temp < cost:
                cost = temp 
                           
    return cost

Pada bagian code berikut ini:

temp = abs(s[0][0] - possible_square[a][0][0]) + abs(s[0][1] - possible_square[a][0][1]) + abs(s[0][2] - possible_square[a][0][2])
temp += abs(s[1][0] - possible_square[a][1][0]) + abs(s[1][1] - possible_square[a][1][1]) + abs(s[1][2] - possible_square[a][1][2])
temp += abs(s[2][0] - possible_square[a][2][0]) + abs(s[2][1] - possible_square[a][2][1]) + abs(s[2][2] - possible_square[a][2][2])

Dilakukan proses perhitungan cost dari perbandingan 8 kemungkinan magic square. Selanjutnya pada bagian:

if cost is None:
	cost = temp

if cost is not None:
	if temp < cost:
		cost = temp

Jika ditemukan nilai cost lebih kecil maka akan dijadikan nilai output.

Proses perhitungan cost dan perbandingan tadi diulang-ulang hingga 8 kemungkinan magic square tadi telah dibandingkan semua.

Voila hasilnya solve!

Thank you for reading, have a great day!