Magic Square – แก้ปริศนา 3×3 โดยใช้ C & Python ตัวอย่าง
ซาราห์ เฉิน
เมจิกสแควร์คืออะไร?
ตารางวิเศษคือเมทริกซ์ตารางที่มีการจัดเรียงตัวเลขพิเศษ ตัวเลขเหล่านี้จะถูกจัดเรียงเพื่อให้ผลรวมของตัวเลขในแต่ละแนวทแยง แถว และคอลัมน์ยังคงเท่าเดิม เกมตารางวิเศษเป็นปริศนาตรรกะง่ายๆ ที่ใช้ในคณิตศาสตร์เพื่อการพักผ่อนหย่อนใจ
ตัวอย่างตารางวิเศษ:
แผนภาพข้างต้นเป็นตัวอย่างของกำลังสองวิเศษของลำดับที่ 3 ผลรวมของเส้นทแยงมุม แถว และคอลัมน์แต่ละคอลัมน์คือ 15
Magic Square ทำงานอย่างไร
เมทริกซ์จัตุรัสวิเศษคือเมทริกซ์ n*n ที่ประกอบด้วยจำนวนเต็มบวก n^2 จำนวนแถวหรือคอลัมน์ของเมทริกซ์จัตุรัสเรียกว่าลำดับของเมทริกซ์
โดยทั่วไป ปริศนาเกี่ยวกับตารางวิเศษจะมีลำดับคี่และมีจำนวนเต็มตั้งแต่ 1 ถึง n^2 ผลรวมของเส้นทแยงมุม แถว และคอลัมน์แต่ละอันจะเท่ากัน ตัวเลขนี้เรียกว่าผลรวมวิเศษหรือค่าคงที่วิเศษ โดยทั่วไป ผลรวมวิเศษนี้ขึ้นอยู่กับลำดับของเมทริกซ์ สูตรของตารางวิเศษสำหรับผลรวมวิเศษของลำดับ n คือ
ลองยกตัวอย่างกำลังสองมหัศจรรย์ที่มีจำนวนเต็ม 3 กัน ดังนั้น ผลรวมมหัศจรรย์จะเป็น-
ทำไมพวกเขาถึงเรียกว่าเวทย์มนตร์?
นักคณิตศาสตร์ในสมัยโบราณหลงใหลในธรรมชาติของชุดตัวเลขที่น่าสนใจหลายชุด โดยชุดตัวเลขวิเศษเป็นหนึ่งในชุดตัวเลขเหล่านั้น หลักฐานที่เก่าแก่ที่สุดของชุดตัวเลขวิเศษย้อนไปถึงประเทศจีนเมื่อ 190 ปีก่อนคริสตศักราช
การศึกษาวิจัยบางกรณีแสดงให้เห็นหลักฐานของปริศนาสี่เหลี่ยมวิเศษในญี่ปุ่น อินเดีย และอาหรับโบราณ โดยอิงจากตำนานบางเรื่อง สันนิษฐานว่ารูปแบบตัวเลขพิเศษเหล่านี้มีความเกี่ยวข้องกับโลกแห่งเวทมนตร์ ดังนั้น จึงเรียกสี่เหลี่ยมวิเศษเหล่านี้ว่าสี่เหลี่ยมวิเศษ
ประเภทของเมจิกสแควร์
คณิตศาสตร์มีรูปแบบต่างๆ ของตารางวิเศษ
- สแควร์เมจิกปกติ: ตารางมหัศจรรย์ประเภทนี้ประกอบด้วยตัวเลข n^2 แรก
- จัตุรัสกึ่งเวทมนตร์: ในประเภทนี้ เฉพาะแถวและคอลัมน์เท่านั้นที่รวมกันเป็นค่าคงที่เวทย์มนตร์
- สแควร์เมจิกอย่างง่าย: ตรงกันข้ามกับประเภทก่อนหน้า แถว คอลัมน์ และเส้นทแยงมุมทั้งสองจะรวมกันเป็นค่าคงที่เวทย์มนตร์
- เมจิกสแควร์ที่สมบูรณ์แบบที่สุด: นี่คือตารางมหัศจรรย์ปกติที่มีคุณสมบัติพิเศษ 2 ประการ โดยที่ตารางย่อยขนาด 2x2 ของเมทริกซ์แต่ละตารางจะรวมกันได้ 2(n^1+2) และคู่ตัวเลขใดๆ ที่เป็นตาราง n/2 นอกเหนือจากตารางจะรวมกันได้ n^1+XNUMX
หากพิจารณาจากคุณสมบัติแล้ว จะเห็นได้ว่ามีตารางวิเศษหลายประเภท แต่เมื่อใดก็ตามที่เราพูดถึงตารางวิเศษ เราจะถือว่ามันเป็นตารางวิเศษปกติที่มีลำดับคี่และแบบธรรมดา
อัลกอริทึมในการสร้าง Magic Square
อัลกอริทึมสำหรับการสร้างสี่เหลี่ยมวิเศษลำดับคี่คือ:
- ตัวเลขแรกหรือ 1 จะถูกเก็บไว้ที่ (n/2, n-1) โดยที่พิกัดแรกคือตำแหน่งแถว และพิกัดที่สองคือตำแหน่งคอลัมน์ สำหรับขั้นตอนต่อไป เราจะแสดงตำแหน่งนี้ด้วย (x, y)
- ตัวเลขถัดไปจะถูกเก็บไว้ที่ (x-1, y+1) หากตำแหน่งไม่ถูกต้องเราจะพิจารณาเงื่อนไขต่อไปนี้
- หากตำแหน่งของแถวเป็น -1 มันจะวาร์ปไปที่ n-1 ในทำนองเดียวกัน หากตำแหน่งคอลัมน์จากการคำนวณเป็น n ตำแหน่งจะบิดเบี้ยวเป็น 0
- ตำแหน่งแถวจะเพิ่มขึ้น 1 และตำแหน่งคอลัมน์จะลดลง 2 หากตำแหน่งที่คำนวณมีตัวเลขอยู่แล้ว
- ถ้าตำแหน่งแถวคือ -1 และตำแหน่งคอลัมน์ที่สอดคล้องกันคือ n ตำแหน่งใหม่จะเป็น (0, n-2
หมายเหตุ อัลกอริทึมนี้จะสร้างเฉพาะค่ากำลังสองวิเศษที่มีลำดับคี่เท่านั้น นอกจากนี้ เรายังถือว่าค่ากำลังสองวิเศษนี้เป็นค่ากำลังสองวิเศษปกติที่มีจำนวน n^2 ตัวแรก นอกจากนี้ ยังมีวิธีแก้ไขหลายวิธีสำหรับค่า n เดียวกัน
มาดูตัวอย่างและดูว่ามันทำงานอย่างไร สมมติว่าเราต้องการหาค่ากำลังสองวิเศษลำดับที่ 3 เนื่องจากค่าดังกล่าวเป็นค่ากำลังสองวิเศษแบบธรรมดาและคี่ ค่าดังกล่าวจึงประกอบด้วยตัวเลขทั้งหมดตั้งแต่ 1 ถึง 3^2 หรือ 9
ใช้อย่างไร
ตามที่เรา ขั้นตอนวิธีขั้นตอนจะเป็นดังต่อไปนี้:
ขั้นตอน 1) ตัวเลขแรกหรือ 1 จะอยู่ที่ตำแหน่ง (3/2, 3-1) หรือ (1, 2) ตามธรรมเนียม ให้พิจารณา x= 1 และ y= 2 สำหรับขั้นตอนถัดไป
ขั้นตอน 2) ตำแหน่งของตัวเลขที่เหลือจะถูกคำนวณดังนี้
ตำแหน่งของหมายเลข 2:
ตัวเลขถัดไปจะอยู่ที่ (x-1, y+1) หรือ (0, 3) ซึ่งไม่ใช่ตำแหน่งที่ถูกต้อง โดยการใช้เงื่อนไข (a) ตำแหน่งที่ถูกต้องที่สอดคล้องกันจะเป็น (0,0) ดังนั้น x= 0, y= 0
ตำแหน่งของหมายเลข 3:
หมายเลข 3 จะอยู่ที่ (x-1, y+1) หรือ (-1, 1) ซึ่งไม่ใช่ตำแหน่งที่ถูกต้อง เมื่อใช้เงื่อนไข (a) ตำแหน่งแถวที่ถูกต้องจะเป็น n-1 หรือ 2 ดังนั้น จำนวน 3 จะอยู่ที่ (2, 1) สำหรับจำนวนถัดไป x= 2, y= 1
ตำแหน่งของหมายเลข 4:
หมายเลข 4 ควรอยู่ที่ (x-1, y+1) หรือ (1, 2) ซึ่งเป็นตำแหน่งที่ถูกต้อง แต่ตำแหน่งนั้นมีตัวเลขอยู่แล้ว ตามเงื่อนไข (b) ตำแหน่งที่ถูกต้องจะเป็น (1+1, 2-2) หรือ (2,0) สำหรับจำนวนถัดไป x= 2, y= 0
ตำแหน่งของหมายเลข 5:
หมายเลข 5 ควรอยู่ที่ (x-1, y+1) หรือ (1, 1) ซึ่งเป็นตำแหน่งที่ถูกต้อง สำหรับจำนวนถัดไป x= 1, y= 1
ตำแหน่งของหมายเลข 6:
หมายเลข 6 ควรอยู่ที่ (x-1, y+1) หรือ (0, 2) ซึ่งเป็นตำแหน่งที่ถูกต้อง สำหรับจำนวนถัดไป x= 0, y= 2
ตำแหน่งของหมายเลข 7:
หมายเลข 7 ควรอยู่ที่ (x-1, y+1) หรือ (-1, 3) ซึ่งไม่ใช่ตำแหน่งที่ถูกต้อง ตามเงื่อนไข (c) ตำแหน่งที่ถูกต้องจะเป็น (0, n-2) หรือ (0, 1) สำหรับจำนวนถัดไป x= 0, y= 1
ตำแหน่งของหมายเลข 8:
หมายเลข 8 ควรอยู่ที่ (x-1, y+1) หรือ (-1, 2) ซึ่งไม่ใช่ตำแหน่งที่ถูกต้อง เมื่อใช้เงื่อนไข (a) ตำแหน่งที่ถูกต้องจะเป็น (2, 2) สำหรับจำนวนถัดไป x= 2, y= 2
ตำแหน่งของหมายเลข 9:
หมายเลข 9 ควรอยู่ที่ (x-1, y+1) หรือ (1, 3) ซึ่งไม่ใช่ตำแหน่งที่ถูกต้อง โดยใช้เงื่อนไข (a) ตำแหน่งที่ถูกต้องจะเป็น (1, 0)
รหัสเทียม
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++ รหัสเมจิกสแควร์
Input:
/*
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;
}
ผลลัพธ์ของตัวอย่าง:
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 รหัสเมจิกสแควร์
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)
ผลลัพธ์ของตัวอย่าง:
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
การวิเคราะห์ความซับซ้อน
- ความซับซ้อนของอวกาศ: เพื่อรักษาเมทริกซ์สี่เหลี่ยมวิเศษ เราจำเป็นต้องมีอาร์เรย์ n ดังนั้นความซับซ้อนของพื้นที่จะเท่ากับ O(n^2)
- ความซับซ้อนของเวลา: โค้ดที่เราใช้สร้างคณิตศาสตร์แบบ Magic Squares ประกอบด้วยลูป 2 ลูป ลูปด้านนอกทำงาน n ครั้ง และลูปด้านในก็ทำงาน n ครั้งเช่นกัน ความซับซ้อนของเวลาคือ O(n^XNUMX)
