Як розв'язати головоломку "Магічний квадрат 3×3" на C& Python

Що таке магічний квадрат?

Магічний квадрат — це квадратна матриця зі спеціальним розташуванням чисел. Значення розміщуються таким чином, щоб сума в кожному рядку, кожному стовпці та обох головних діагоналях залишалася однаковою. Магічні квадрати — це прості логічні головоломки, що використовуються в розважальній математиці.

Приклад магічних квадратів:

Наведена вище діаграма показує магічний квадрат порядку 3. Сума кожної діагоналі, рядка та стовпця дорівнює 15. У наступному розділі пояснюється, як отримується ця константа суми.

Як працюють магічні квадрати

Магічний квадрат порядку n — це матриця розміром n на n, що містить n² додатних цілих чисел. Кількість рядків або стовпців називається порядком матриці.

Типові головоломки з магічними квадратами мають непарний порядок і використовують цілі числа від 1 до n². Оскільки кожен рядок, стовпець і діагональ повинні давати однакове значення, це значення називається магічною сумою або магічною константою. Константа залежить лише від n. Формула для магічної суми порядку n така:

Розглянемо магічний квадрат порядку 3. Тоді магічна сума буде:

Ця формула пояснює арифметичні дії, але головоломка має довгу культурну історію, яка й дала їй таку запам'ятовувану назву.

Чому їх називають магічними?

Стародавніх математиків захоплювали цікаві комбінації чисел, і магічний квадрат був однією з них. Найдавніші свідчення датуються Китаєм приблизно 190 роком до нашої ери.

Дослідження показують існування головоломок з магічними квадратами у стародавній Японії, Індії та Аравії. Легенди пов'язували ці розстановки з магічним світом, і назва закріпилася. Окрім фольклору, математики також визначили формальні категорії, які відрізняють один квадрат від іншого.

Види магічного квадрата

У математиці існує кілька варіантів магічних квадратів:

• Звичайний магічний квадрат: Містить перші n² натуральних чисел.
• Напівмагічний квадрат: Тільки рядки та стовпці складають магічну константу.
• Простий магічний квадрат: Рядки, стовпці та обидві головні діагоналі в сумі дають магічну константу.
• Найідеальніший магічний квадрат: Звичайний магічний квадрат із двома додатковими властивостями. Кожен підквадрат матриці розміром 2 на 2 дає в сумі 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.

Як це працює на квадраті 3 на 3

Застосування алгоритм вище, кроки такі:

Крок 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).

З кожною заповненою коміркою та сама логіка безпосередньо перетворюється на псевдокод.

Псевдокод для Magic Square

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 для Магічного квадрата

Вхідний сигнал:

/*
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 на n, тому просторова складність дорівнює O(n²).
• Складність часу: Генератор використовує два вкладені цикли. Зовнішній цикл виконується n разів, а внутрішній цикл також виконується n разів, тому загальна часова складність становить O(n²).

Поширені запитання