Как решить головоломку с магическим квадратом 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), что не является допустимой позицией. Согласно правилу (а), столбец переносится до 0, в результате чего получается (0, 0). Установите x = 0, y = 0.

Позиция номера 3:

Число 3 должно находиться в позиции (x-1, y+1) или (-1, 1), что не является допустимой позицией. Согласно правилу (а), строка переносится на 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), что недопустимо. По правилу (а) строка переносится на 2, что дает (2, 2). Установите x = 2, y = 2.

Позиция номера 9:

Число 9 должно находиться в точке (x-1, y+1) или (1, 3), что недопустимо. Согласно правилу (а), столбец переносится до 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 для Магического квадрата

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

/*
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²).

Часто задаваемые вопросы (FAQ)