วิธีแก้ปริศนาตารางมหัศจรรย์ 3x3 ในภาษา C และ Python

ตารางมหัศจรรย์คืออะไร?

ตารางมหัศจรรย์ (Magic Square) คือเมทริกซ์สี่เหลี่ยมจัตุรัสที่มีการจัดเรียงตัวเลขแบบพิเศษ โดยค่าต่างๆ จะถูกจัดวางเพื่อให้ผลรวมในทุกแถว ทุกคอลัมน์ และเส้นทแยงมุมหลักทั้งสองเส้นคงที่ ตารางมหัศจรรย์เป็นปริศนาตรรกะง่ายๆ ที่ใช้ในคณิตศาสตร์เพื่อความบันเทิง

ตัวอย่างตารางวิเศษ:

แผนภาพด้านบนแสดงตารางมหัศจรรย์ลำดับที่ 3 ผลรวมของทุกแนวทแยง แถว และคอลัมน์เท่ากับ 15 ส่วนถัดไปจะอธิบายว่าผลรวมคงที่นี้เกิดขึ้นได้อย่างไร

วิธีการทำงานของตารางมหัศจรรย์

ตารางมหัศจรรย์อันดับ n คือเมทริกซ์ขนาด n x n ที่ประกอบด้วยจำนวนเต็มบวก n² ตัว จำนวนแถวหรือคอลัมน์เรียกว่าอันดับของเมทริกซ์

ปริศนาตารางมหัศจรรย์ทั่วไปจะมีลำดับเป็นเลขคี่และใช้จำนวนเต็มตั้งแต่ 1 ถึง n² เนื่องจากผลรวมของทุกแถว ทุกคอลัมน์ และทุกแนวทแยงมุมต้องมีค่าเท่ากัน ค่าดังกล่าวจึงเรียกว่าผลรวมมหัศจรรย์หรือค่าคงที่มหัศจรรย์ ค่าคงที่นี้ขึ้นอยู่กับ n เท่านั้น สูตรสำหรับผลรวมมหัศจรรย์ลำดับ n คือ:

พิจารณาตารางเวทมนตร์ลำดับที่ 3 ผลรวมเวทมนตร์จะเป็นดังนี้:

สูตรนี้อธิบายถึงหลักการทางคณิตศาสตร์ แต่ปริศนานี้มีประวัติศาสตร์ทางวัฒนธรรมอันยาวนานที่ทำให้มันมีชื่อที่น่าจดจำ

ทำไมถึงเรียกว่าเวทมนตร์?

นักคณิตศาสตร์โบราณต่างหลงใหลในชุดตัวเลขที่น่าสนใจ และตารางมหัศจรรย์ก็เป็นหนึ่งในนั้น หลักฐานที่เก่าแก่ที่สุดย้อนกลับไปถึงประเทศจีนราว 190 ปีก่อนคริสตกาล

จากการศึกษาพบหลักฐานของปริศนาตารางเวทมนตร์ในญี่ปุ่นโบราณ อินเดีย และอาหรับ ตำนานเชื่อมโยงการจัดเรียงเหล่านี้เข้ากับโลกแห่งเวทมนตร์ และชื่อนี้ก็ติดมาจนถึงปัจจุบัน นอกเหนือจากนิทานพื้นบ้านแล้ว นักคณิตศาสตร์ยังได้กำหนดหมวดหมู่ที่เป็นทางการเพื่อแยกแยะตารางแต่ละแบบออกจากกันอีกด้วย

ประเภทของเมจิกสแควร์

ในวิชาคณิตศาสตร์ มีตารางมหัศจรรย์หลายรูปแบบ:

• สแควร์เมจิกปกติ: ประกอบด้วยจำนวนธรรมชาติ n² ตัวแรก
• จัตุรัสกึ่งเวทมนตร์: มีเพียงผลรวมของแถวและคอลัมน์เท่านั้นที่เท่ากับค่าคงที่มหัศจรรย์
• สแควร์เมจิกอย่างง่าย: ผลรวมของแถว คอลัมน์ และเส้นทแยงมุมหลักทั้งสองเส้น เท่ากับค่าคงที่มหัศจรรย์
• เมจิกสแควร์ที่สมบูรณ์แบบที่สุด: ตารางเวทมนตร์ปกติที่มีคุณสมบัติพิเศษสองประการ คือ ผลรวมของช่องย่อยขนาด 2x2 ทุกช่องในตารางจะเท่ากับ 2(n²+1) และผลรวมของตัวเลขสองจำนวนใดๆ ที่อยู่ห่างกัน n/2 ช่อง จะเท่ากับ n²+1

นอกจากนี้ยังมีหมวดหมู่เพิ่มเติมตามคุณสมบัติอื่นๆ อีกด้วย เมื่อใดก็ตามที่ใช้คำว่า "ตารางเวทมนตร์" โดยไม่มีคำอธิบายเพิ่มเติมในบทเรียนนี้ จะหมายถึงตารางเวทมนตร์แบบธรรมดาที่มีลำดับเป็นเลขคี่

อัลกอริทึมสำหรับสร้างตารางมหัศจรรย์

อัลกอริทึมแบบคลาสสิกสำหรับการสร้างตารางเวทมนตร์ลำดับคี่ ซึ่งเรียกว่าวิธีสยาม มีดังนี้:

• ตัวเลขแรก (1) จะถูกเก็บไว้ที่ตำแหน่ง (n/2, n-1) โดยที่พิกัดแรกคือดัชนีแถวและพิกัดที่สองคือดัชนีคอลัมน์ สำหรับขั้นตอนต่อไป ให้เรียกตำแหน่งนี้ว่า (x, y)
• ตัวเลขถัดไปจะอยู่ที่ตำแหน่ง (x-1, y+1) หากตำแหน่งนั้นไม่ถูกต้อง ให้ใช้กฎต่อไปนี้:
  1. ถ้าดัชนีแถวเป็น -1 ให้วนกลับไปที่ n-1 ถ้าดัชนีคอลัมน์เป็น n ให้วนกลับไปที่ 0
  2. หากตำแหน่งที่คำนวณได้มีตัวเลขอยู่แล้ว ให้เพิ่มค่าในแถวขึ้น 1 และลดค่าในคอลัมน์ลง 2
  3. ถ้าค่าในแถวเป็น -1 และค่าในคอลัมน์เป็น n ในเวลาเดียวกัน ตำแหน่งใหม่จะเป็น (0, n-2)

หมายเหตุ อัลกอริทึมนี้สร้างเฉพาะตารางเวทมนตร์ที่ถูกต้องที่มีลำดับเป็นเลขคี่เท่านั้น ผลลัพธ์ที่ได้คือตารางเวทมนตร์ปกติที่ประกอบด้วยจำนวนธรรมชาติ n² ตัวแรก อาจมีคำตอบที่ถูกต้องมากกว่าหนึ่งคำตอบสำหรับค่า n เดียวกัน

กฎต่างๆ จะชัดเจนยิ่งขึ้นผ่านตัวอย่างเล็กๆ เกี่ยวกับลำดับที่ 3 ซึ่งใช้ตัวเลข 1 ถึง 9

วิธีการทำงานบนพื้นที่สี่เหลี่ยมจัตุรัสขนาด 3x3

การใช้ ขั้นตอนวิธี ขั้นตอนข้างต้นมีดังนี้:

ขั้นตอน 1) ตัวเลขแรก (1) จะถูกวางไว้ที่ (3/2, 3-1) หรือ (1, 2) สำหรับขั้นตอนถัดไป ให้ตั้งค่า x = 1 และ y = 2

ขั้นตอน 2) ตำแหน่งของตัวเลขที่เหลือจะคำนวณได้ดังนี้

ตำแหน่งของหมายเลข 2:

ตัวเลขถัดไปควรอยู่ที่ (x-1, y+1) หรือ (0, 3) ซึ่งไม่ใช่ตำแหน่งที่ถูกต้อง ตามกฎ (a) คอลัมน์จะวนกลับไปที่ 0 ทำให้ได้ (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) ซึ่งถูกต้องแต่มีค่า 1 อยู่แล้ว ตามกฎ (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, 2) กำหนดให้ x = 2, y = 2

ตำแหน่งของหมายเลข 9:

หมายเลข 9 ควรอยู่ที่ (x-1, y+1) หรือ (1, 3) ซึ่งไม่ถูกต้อง ตามกฎ (a) คอลัมน์จะวนกลับไปที่ 0 ทำให้ได้ (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++ และ Python.

C++ Code สำหรับตารางเวทมนตร์

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 เวอร์ชันด้านล่างใช้กฎแถวและคอลัมน์ที่เหมือนกัน

Python Code สำหรับตารางเวทมนตร์

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 x n ดังนั้นความซับซ้อนของพื้นที่จัดเก็บจึงเป็น O(n²)
• ความซับซ้อนของเวลา: ตัวสร้างใช้ลูปซ้อนกันสองลูป ลูปภายนอกทำงาน n ครั้ง และลูปภายในก็ทำงาน n ครั้งเช่นกัน ดังนั้นความซับซ้อนของเวลาโดยรวมคือ O(n²)

คำถามที่พบบ่อย