Как да решите пъзел 3×3 магически квадрат на C & Python

Какво е магически квадрат?

Магическият квадрат е квадратна матрица със специално подреждане на числата. Стойностите са разположени така, че сумата във всеки ред, всяка колона и двата главни диагонала да остане една и съща. Магическите квадрати са прости логически пъзели, използвани в развлекателната математика.

Пример за магически квадрати:

Диаграмата по-горе показва магически квадрат от ред 3. Сумата от всеки диагонал, ред и колона е равна на 15. Следващият раздел обяснява как се получава тази постоянна сума.

Как работят магическите квадрати

Магически квадрат от ред n е матрица с размери n x n, съдържаща n² положителни цели числа. Броят на редовете или колоните се нарича ред на матрицата.

Типичните пъзели с магически квадрати имат нечетен ред и използват числа от 1 до n². Тъй като всеки ред, колона и диагонал трябва да се сумират до една и съща стойност, тази стойност се нарича магическа сума или магическа константа. Константата зависи само от n. Формулата за магическата сума от ред n е:

Да разгледаме магически квадрат от ред 3. Тогава магическата сума е:

Тази формула обяснява аритметиката, но пъзелът има дълга културна история, която му дава запомнящото се име.

Защо се наричат ​​Магия?

Древните математици са били очаровани от интересни комбинации от числа, а магическият квадрат е бил една от тях. Най-ранните доказателства датират от Китай около 190 г. пр.н.е.

Проучвания показват доказателства за съществуването на магически квадратни пъзели в древна Япония, Индия и Арабия. Легендите свързвали тези подредби с магическия свят и името се запазило. Освен фолклора, математиците са дефинирали и формални категории, които разграничават един квадрат от друг.

Видове магически квадрат

В математиката има няколко варианта на магически квадрати:

• Нормален магически квадрат: Съдържа първите n² естествени числа.
• Полумагически квадрат: Само редовете и колоните се сумират до магическата константа.
• Прост магически квадрат: Редовете, колоните и двата главни диагонала се сумират до магическата константа.
• Най-съвършеният магически квадрат: Нормален магически квадрат с две допълнителни свойства. Всеки подквадрат 2 x 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 x n, така че пространствената сложност е O(n²).
• Времева сложност: Генераторът използва два вложени цикъла. Външният цикъл се изпълнява n пъти, а вътрешният цикъл също се изпълнява n пъти, така че общата времева сложност е O(n²).

Въпроси и Отговори