[알고리듬] #77 홀수 마방진

[key word] 매직 스퀘어, 드라루벨, 샴 방식 , 마법 상수 

파이썬 실습창을 열 수 있습니다.실습창 열기

 

 

홀수 마방진

• 중국  하나라의 우 임금 시절 (약 4000년 전) 우왕은 매년 범람하는 황하의 물길을 정비할 때 이상한 그림이 새겨진 거북의 등 껍데기를 발견했습니다. 등 껍데기에는 1부터 9까지의 숫자가 있었는데 가로, 세로, 대각선의 어느 방향으로 더해도 그 합이 15였습니다(황하 낙수). 여기서 유래하여 오늘날 마방진(magic square)이 생겼습니다. 
  마방진( 魔方陣 )의 '마'는 마법, '방'은 4각형, '진'은 배치한다는것으로 '신비로운 4각형 배열'아리는 뜻입니다. 
• 마방진은 정사각형(정방행렬)에 1부터 차례로 숫자를 적되, 중복하거나 빠뜨리지 않고 가로, 세로, 대각선에 있는 수들의 합이 모두 같도로 만든 배열입니다.  
• 3*3 행렬은 3차 마방진, 4*4 행렬은 4차 마방진 등으로 부르며, 한 줄에 있는 수들의 합을  마법 상수(magic constant)라고 합니다. 3차 마방진의 마법 상수는 15입니다. 마법 상수는 차수 n으로 결정되는데 다음의 값을 가집니다.
        M = n*(n *n + 1) // 2
• 홀수 마방진의 숫자 배열 방법은 연구되어 있습니다. 그러나 짝수 마방진은 4의 배수인 배열에 대해서만 연구되어있습니다. 홀수 마방진의 숫자 배열 방법 몇가지 중에서 드.라.루벨( de la Loubère 또는 Siamese method , 샴 방식)의 방법이 코딩하기 쉽습니다.

 

1. 드.라.루벨의 방법

드.라.루벨의 방법은 다음과 같습니다

• 1은 첫째 줄 가운데 쓴다.
• 배수 다음은 아래에
• 첫째 줄 다음에는 오른쪽 가장 아래
• 가장 오른쪽 다음에는 위의 줄 첫 칸
• 그 외는 한 줄 위, 한 칸 오른쪽

구체적으로 설명합니다.

 

 

1. 가로 3칸, 세로 3칸의 모눈을 그립니다.
2. 맨 위의 줄 가운데에 1을 적습니다.
3. 맨 위의 줄이므로, 맨 아래 줄로 가서 한 칸 오른쪽에 2를 적습니다.
4. 2는 3의 배수가 아니고, 가장 위쪽 줄이 아니고, 가장 오른쪽 칸이므로,
   한 줄 위, 가장 왼쪽 칸으로 가서 3을 적습니다. (배수 판단을 가장 먼저 해야 합니다)
5. 3은 3의 배수이므로 한 줄 아래(칸은 그대로)로 가서 4를 적습니다.
6.  4는 3의 배수 아니고, 가장 위의 줄 아니고, 가장 오른쪽 칸 아니므로
    한 줄 위, 한 칸 오른쪽으로 가서 5를 적습니다.
7.  5도 해당 사항 없으므로 한 줄 위, 한 칸 오른쪽으로 가서 6을 적습니다.
8. 6은 3의 배수이므로 한 줄 아래(칸은 그대로)에 7을 적습니다.
    6은 3의 배수, 맨 위, 가장 오른쪽 모두 해당 되지만 배수를 먼저 판단합니다.
    위와 오른쪽은 판단 순서에 관계가 없습니다.
9. 7은 가장 오른쪽. 그러므로 위의 중 처음으로 가서 8.
10. 8은 가장 위의 줄. 맨 밑의 줄, 한 칸 오른쪽 9.
11. 9는 3의 제곱이므로 끝.

 

5차 마방진을 만들어 보세요.

1부터 25까지(= 5*5)의 수를 드.라.루벨의 방법으로 배치하면 됩니다.

 

  17  24   1   8  15
  23   5   7  14  16
   4   6  13  20  22
  10  12  19  21   3
  11  18  25   2   9

 

2. 코딩하기

다음 코드를 분석하고, 안보고 코딩하여 보세요.

n=5                                #마방진 차원
a=[[0]*n for i in range(n)]        # 2차원배열
i,j=0,n//2
a[i][j]=1                          # 첫줄 가운데 1
for k in range(2,n*n+1):           # 2부터 n*n까지 기록
    if (k-1)%n==0: i+=1            # 배수이면 아래
    elif i==0: i=n-1; j+=1         # 가장 윗줄이면
    elif j==n-1: i-=1; j=0         # 가장 오른쪽이면
    else:i-=1; j+=1                # 그 외는 오른쪽 위 
    a[i][j]=k
for i in a:
    print(i)
    
'''
칸을 맞추고 싶으면 다음과 같이 코딩할 수 있습니다.
11번 줄, 12번 줄 대신에
for i in a:
    for j in i:
        print(f'{j:4}',end='')
    print() 
    
실습창에서는 다음과 같이 할 수 있습니다.
for i in a:
    s=''
    for j in i:
       s+='{0:>4}'.format(j)
    print(s)
    
'''

 

이 방법은 홀수 마방진에서 사용할 수 있습니다.

n을 홀수인 다른 수로 바꾸어 즐겨보세요.

안보고 코딩할 수 있습니까?

안보고 코딩할 수 있으면 오늘 끝.

수고하셨습니다.

안녕!