Magic Square – C &를 사용하여 3×3 퍼즐 풀기 Python 예
사라 첸
매직스퀘어란?
매직 스퀘어는 특별한 숫자 배열을 가진 정사각형 행렬입니다. 이 숫자들은 각 대각선, 행, 열의 숫자의 합이 동일하게 유지되도록 배열됩니다. 매직 스퀘어 게임은 오락 수학에 사용되는 간단한 논리 퍼즐입니다.
마법의 사각형 예:
위 다이어그램은 3차 마방진의 예입니다. 각 대각선, 행, 열의 합은 15입니다.
매직스퀘어 작동 원리
매직 스퀘어는 n^2개의 양의 정수로 구성된 n*n 행렬입니다. 정사각 행렬의 행 또는 열의 수를 행렬의 차수라고 합니다.
일반적으로 매직 스퀘어 퍼즐은 홀수 순서를 가지고 있으며 1에서 n^2까지의 정수를 갖습니다. 각 대각선, 행, 열의 합은 같습니다. 이 숫자를 매직 합 또는 매직 상수라고 합니다. 일반적으로 이 매직 합은 행렬의 순서에 따라 달라집니다. n차 매직 합에 대한 매직 스퀘어 공식은 다음과 같습니다.
정수 3을 갖는 마방진의 예를 들어보겠습니다. 따라서 마방진의 합은 다음과 같습니다.
왜 매직이라고 불리는가?
고대 수학자들은 여러 가지 흥미로운 숫자 조합의 본질에 매료되었습니다. 마법의 사각형은 그 중 하나였습니다. 마법의 사각형에 대한 가장 초기의 증거는 기원전 190년 중국으로 거슬러 올라갑니다.
일부 연구에서는 고대 일본, 인도, 아라비아에서 매직 스퀘어 퍼즐의 증거를 보여줍니다. 일부 전설에 따르면, 이러한 특별한 숫자의 형태가 마법의 세계와 연결되어 있다고 가정했습니다. 따라서 이러한 사각형은 매직 스퀘어라고 명명되었습니다.
매직스퀘어의 종류
마법의 사각형 수학에는 다양한 변형이 있습니다.
- 일반 마방진: 이 유형의 마법진에는 처음 n^2개의 숫자가 포함됩니다.
- 세미 매직 스퀘어: 이 유형에서는 행과 열의 합만 마법 상수가 됩니다.
- 심플 매직 스퀘어: 이전 유형과 달리 행, 열 및 두 대각선의 합이 마법 상수에 해당합니다.
- 가장 완벽한 마법진: 이것은 두 가지 특별한 속성을 가진 일반적인 매직 스퀘어입니다. 여기서, 행렬의 각 2 x 2 부분 정사각형은 총 2(n^2+1)이 됩니다. 그리고 그리드에서 n/2 정사각형 떨어진 모든 숫자 쌍은 합산하여 n^2+1이 됩니다.
속성에 따라 더 많은 유형의 매직 스퀘어가 있습니다. 하지만 매직 스퀘어에 대해 언급할 때마다 우리는 그것이 홀수차 정상적이고 간단한 매직 스퀘어라고 가정합니다.
마방진 생성 알고리즘
홀수차 마법진을 생성하는 알고리즘은 다음과 같습니다.
- 첫 번째 숫자 또는 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++ 코드 매직스퀘어
입력:
/*
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)가 됩니다.
- 시간 복잡성 : 우리가 마법의 사각형 수학을 생성하는 데 사용한 코드는 두 개의 루프로 구성되어 있습니다. 바깥쪽 루프는 n번 실행되고, 안쪽 루프도 n번 실행됩니다. 궁극적으로 시간 복잡도는 O(n^2)입니다.
