[알고리즘] 홀수 마방진

2009. 05. 11 (月)

 중국 전설의 주인공인 한나라 우임금은 홍수를 다스리려고 황하강의 지류에서 물길을 고치다가 거북 등껍질에 새겨진 이상한 그림을 얻었다고 합니다. 낙서라 불려지는 이 그림은 1부터 9까지의 숫자가 3X3의 정사각형에 배열돼 있었다고 한다.

신기한 것은 늘어선 숫자들이 가로, 세로, 대각선 어느 방향으로 더해도 그 합이 15가 되는 것이었습니다. 그래서 고대 중국에서는 이 낙서가 우주의 원리를 포함 하고 있다고 여기고 신비한 힘을 가지고 있다고 생각되었습니다.

 이처럼 1부터 연이은 숫자로 사각형 모양으로 배열해 가로 세로 대각선 방향의 합이 모두 같도록 배열한 것을 마방진 이라고 합니다.

 

 

1.     홀수 마방진 풀이

①     첫 번째 숫자를 1행의 중앙열에 넣는다.

②     대각선 방향(한 칸 위와 한 칸 옆)으로 이동한 곳에 다음 숫자를 넣는다. 만약 위치가 영역을 벗어날 경우 반대 행이나 열에 숫자를 넣는다.

③     위의 단계를 이미 숫자가 저장되어 있는 칸을 만날 때까지 n회 만큼 반복한다.

④     3단계의 마지막 숫자를 넣은 곳에서 바로 아래칸에 다음 숫자를 넣고 위의 2단계부터 다시 반복한다.

 

2.     소스

#include "stdafx.h"

#include <stdio.h>

#define MAX 10

 

int Square[MAX][MAX] = {0, };

 

void GetOddSquare(int n);

void InitSquare();

void PrintSquare(int n);

int _tmain(int argc, _TCHAR* argv[])

{

        InitSquare();

        GetOddSquare(3);

        PrintSquare(3);

 

        InitSquare();

        GetOddSquare(5);

        PrintSquare(5);

 

        InitSquare();

        GetOddSquare(7);

        PrintSquare(7);

 

        return 0;

}

 

void GetOddSquare(int n)

{

        int row = 0, col = 0;

        int nValue = 1;

 

        row = 0;

        col = n/2;

 

        while(nValue <= n*n)

        {

               Square[row][col] = nValue;

 

               if(nValue % n == 0)

               {

                       row++;

               }

               else

               {

                       row--;

                       col++;

               }

 

               if(row < 0)

                       row = n-1;

 

               if(row >= n)

                       row = 0;

 

               if(col < 0)

                       col = n-1;

 

               if(col >= n)

                       col = 0;

 

               nValue++;

        }

 

}

 

void InitSquare()

{

        for(int i=0 ; i<MAX ; i++)

        for(int j=0 ; j<MAX ; j++)

        {

               Square[i][j] = 0;

        }

}

void PrintSquare(int n)

{

        for(int i=0 ; i<n ; i++)

        {

               for(int j=0 ; j<n ; j++)

               {

                       printf(" %d ", Square[i][j]);

               }

 

               printf("\n");

        }

}