C 언어로 3×3 마방진 퍼즐 푸는 방법 Python
사라 첸
⚡ 스마트 요약
마법 정사각형 퍼즐은 n x n 격자 안에 연속된 숫자를 배열하여 모든 행, 열, 대각선의 합이 모두 같은 값(마법 상수)을 내도록 하는 퍼즐로, 오락 수학 및 알고리즘적 사고력을 기르는 고전적인 연습 문제입니다.
마법의 정사각형이란 무엇일까요?
마방진은 특별한 방식으로 숫자가 배열된 정사각형 행렬입니다. 각 행, 각 열, 그리고 두 개의 주대각선의 합이 항상 같도록 숫자가 배치됩니다. 마방진은 오락 수학에서 사용되는 간단한 논리 퍼즐입니다.
마법의 사각형 예:
위 그림은 3차 마방진을 보여줍니다. 모든 대각선, 행, 열의 합은 15입니다. 다음 절에서는 이처럼 일정한 합계가 어떻게 생성되는지 설명합니다.
마법진의 작동 원리
n차 마방진은 n²개의 양의 정수로 이루어진 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이면 n-1로, 열 인덱스가 n이면 0으로 래핑합니다.
- 계산된 위치에 이미 숫자가 포함되어 있으면 행을 1만큼 증가시키고 열을 2만큼 감소시킵니다.
- 행이 -1이고 열이 n인 경우 새 위치는 (0, n-2)입니다.
참고 : 이 알고리즘은 홀수 차수의 유효한 마방진만 생성합니다. 결과는 처음 n²개의 자연수를 포함하는 일반 마방진입니다. 동일한 n에 대해 여러 개의 유효한 해가 존재할 수 있습니다.
1부터 9까지의 숫자를 사용하는 3차 순서의 간단한 예시를 통해 규칙이 더 명확해집니다.
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 매직 스퀘어의 경우
입력:
/* 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
The 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²)입니다.
