마방진의 풀이 여러가지가 있다.
대표적인 풀이방법은 홀수차와 짝수차에 따라 다르고 짝수차는 4의 배수와 아닌 수에 따라 달라진다.
예를들어 3차 마방진은 3x3의 정방행렬형태다.
가장 간단한 형태는 홀수 마방진이고, 짝수차 중 4의 배수가 아닌 마방진 형태가 가장 복잡하다.
여기서는 간단히 홀수 마방진을 푸는 방법과 알고리즘을 c언어로 작성해 보겠다.
마방진의 정의
우리에게 친숙한 김홍도의 작품 씨름이다. 이 그림에는 마방진의 원리가 숨어있다.
x자 마방진이라고 하는 이 마방진은 대각선에 늘어선 사람의 합이 12명이 된다.
우리가 흔히 말하는 마방진은 규격은 다음과 같다.
N차 마방진의 경우 1부터 NxN까지의 자연수를 NxN칸에 나열 했을 경우 가로와 세로 대각선의 어느 방향으로도 수의 합이 같아야 한다.
홀수 마방진의 풀이법
1.(첫 번째 행, 가운데 열) 위치에서 1부터 시작한다.
2. 이동 방향은 행은 감소하는 방향, 열은 증가(또는 감소)하는 방향이다.(위 그림은 오른쪽 위 방향)
3. 이동 중 행렬의 범위를 벗어날 경우.
- 행이 벗어난 경우, 행을 마지막 행으로 옮김
- 열이 벗어난 경우, 열을 처음 열로 옮김
4. 다른 수에 막히는 경우(이 경우는 N차일 경우 N의 배수 다음 수에서 막히게 된다. 위 그림에서는 3 다음 수 4에서 막힘)
다음 행부터 시작한다.
이 네 가지 규칙을 알고리즘으로 표현한다.
매끄러운 알고리즘을 위해 4번의 경우를 먼저 생각하는 것이 좋다. 4번의 경우면 4번을 시행, 4번이 아닌 경우 2번으로 돌아간 뒤 3번의 조건을 수행하는 것이 가장 이상적이다.
알고리즘 난이도 : 중-하
다음은 7차마방진을 구한 결과다.
홀수 마방진의 경우 중앙의 열과, 중앙의 행을 중심으로 좌우 또는 아래위로 대칭인 형태기 때문에 이런 방법이 가능하다. 짝수 마방진의경우는 중앙에 위치한 수가 없다. 그래서 중앙의 값을 짝수 개를 묶어 합이 같은 중앙값을 만들어, 이 값을 중심으로 전체 모양이 대칭되게 형태를 바꾸어야 한다. 하지만 단순이 이런 논리로 다 해결되지 않는다. 짝수의 경우 4의 배수인 경우와 아닌 경우의 풀이 법이 약간 달라지게 된다. 짝수마방진-작성중...