마방진이란...
n행과 n열을 가진 정사각형에 1에서 n^2까지의 정수를 나열하여 가로 셀의 합, 세로 셀의 합, 대각선 셀의 합이 동일한 숫자를 가진 경우를 마방진(Magic Square)이라 부른다. 아래 그림은 3차 마방진의 예이다. 아래의 그림에서 2,3,4번째 그림은 첫 번째 마방진을 90도씩 반시계방향으로 회전시켜서 얻은 결과이다.
마방진은 2x2형태 즉, 1~4까지의 정수를 배열하는 2차 마방진은 성립하지 않지만, 그 외 1x1형태의 완벽한 마방진과 3x3 4x4.... nxn으로 이어지는 모든 경우의 마방진은 존재하는 걸로 알려져 있다. 짝수 마방진과 홀수 마방진을 만드는 방법은 서로 다르며, 숫자를 나열하는 방법은 한 가지가 아니라 여러 가지 방법이 존재하는 걸로 알려져 있다.
위의 3차 마방진의 경우 가로 셀의 합, 세로 셀의 합, 대각선 셀의 합은 각각 15가 됨을 알 수 있다. 첫 번째 세로줄에 있는 숫자의 합은 6+7+2=15 이고 두 번째 세로줄에 있는 숫자의 합은 1+5+9=15이다. 가로줄도 같은 방식으로 계산해 보면 15가 됨을 알 수 있다. 그럼 두개의 대각선 셀의 합은 어떨까? 6+5+4=15와 8+5+2=15로 역시 합이 15가 되는걸 알 수 있다.
그렇다면 마방진을 구하기 이전에 이 가로, 세로, 대각선의 합을 미리 알 수는 없을까? 이를 구하는 공식이 존재한다. 방진의 가로세로 셀이 n개이고 각각의 합이 c라고 한다면, 공식은 아래와 같다.
![]()
이 공식을 이용하면 숫자를 나열해 보지 않고도 홀수 마방진의 가로 셀, 세로 셀, 대각선 셀의 합을 미리 알 수가 있다. 예를 들어 15를 위의 공식에 대입해 보면 15차 마방진의 가로, 세로, 대각선의 합은 각각 1695가 됨을 알 수 있다. 15차 마방진에 들어가는 숫자의 최소 값은 1이다. 그럼 최대 값은 얼마일까? 최대 값을 구하는 공식은 아래와 같다.
![]()
즉, 가로 또는 세로 셀 개수의 자승임을 쉽게 알 수 있다.
위의 예로든 3차 마방진의 경우 아무런 사전 지식이 없이도 몇 차례의 시행착오를 거치면 누구나 1,2분 안에 숫자를 정확하게 배치할 수 있을 것이다. 왜냐면 배열해야 하는 숫자가 1~9까지로 몇 개 되지 않기 때문이다. 그렇다면, 15차 또는 30차와 같은 큰 마방진을 구한다고 하면 단순히 시행착오를 거치며 숫자를 배열해서 마방진을 만들 수 있을까? 가능은 하다. 하지만 쉽지 않을 것이다. 그럼 컴퓨터의 도움을 받아 쉽게 마방진을 구하는 프로그램을 제작해 보면 어떨까? 그러나 여기에도 문제가 있다. 컴퓨터가 무작위로 숫자를 배치해서 가로, 세로, 대각선의 합을 구하고, 결과 값들이 일치하지 않으면 다시 재배치하는 방식으로 무한루프를 돌린다면 마방진을 만들 수도 있을 것이다. 왜냐하면 컴퓨터의 처리속도가 매우빠르기 때문이다. 그러나 이 방법은 그리 효과적적인 방법이 될 수 없다.
그렇다면, 가로, 세로, 대각선의 합이 같은 결과가 나오도록 숫자를 배치하는데 특별한 규칙이 존재 하지는 않을까? 만일 어떤 규칙이 존재한다면, 사람 손으로도 쉽게 큰 마방진을 구할 수도 있을 것이고 프로그래밍을 하는데도 보다 효율적일 수 있을 것이다. 여기까지 읽었다면 벌써 짐작하였을 것이다. 맞다. 마방진내에 숫자를 배치하는 규칙들이 존재한다. 이는 많은 사람들이 오래전부터 이러한 규칙들을 찾아냈고, 아직 알려지지 않은 다른 규칙들도 존재할 수도 있다. 그리고 그 규칙대로 숫자들을 배열만 한다면 마방진의 크기는 문제가 되지 않는다.
자 그럼 홀수마방진에 숫자를 배열하는 규칙을 알아보자. 규칙은 의외로 매우 단순하다.
생성규칙
첫 번째 그림처럼 1을 첫줄 중간에 배치시킨다. 그리고 1아 위치한 곳에서 위로 한 칸, 좌로 한 칸 이동 후 다음 숫자인 2를 배치시킨다. 그런데 그림에서 보이는 바와 같이 2(녹색)를 배치시켜야할 곳은 마방진의 범위 밖이다. 이렇게 상단으로 범위가 벗어날 경우 해당 숫자를 세로방향 끝으로 이동시켜서 배치시킨다. 그림에서 붉은색으로 표시된 2가 이동 후 배치시킨 곳이다.
두 번째 그림처럼 2가 위치한 곳에서 다시 위로 한 칸, 좌로 한 칸 이동 후 다음 숫자인 3을 배치시킨다. 그런데 여기서도 3(녹색)을 배치시켜야 할 곳이 마방진 범위를 벗어났다. 이렇게 좌측으로 범위를 벗어난 경우는 우측 끝(붉은색 3)으로 이동 후 숫자를 배치시키면 된다.
세 번째 그림을 보자. 3이 위치한 곳에서 위로 한 칸, 좌로 한 칸 이동 후 4를 배치해야 되지만 그곳은 이미 1(노란색)이 위치하고 있다. 이런 경우는 3이 위치한 곳의 바로 아래 칸에 4(갈색)를 배치시키면 된다. 4를 배치시킨 후 다시 위로 한 칸, 좌로 한 칸 이동해서 5를 배치시킨다. 다시 위로 한 칸, 좌로 한 칸 이동 후 6을 배치시키자.
이제 위로 한 칸, 좌로 한 칸 이동 후 7(녹색)을 배치해야 되는데, 이 경우는 7이 위치해야 할 자리가 마방진의 상단경계와 좌측경계를 동시에 벗어난 경우이다. 이 경우는 3이후 4를 배치한 경우와 동일한 룰이 적용되어, 6이 위치한 곳에서 한 칸 아래로 이동 후 7(붉은색)을 배치시키면 된다.
8은 두 번째 그림의 경우와 같은 룰이 적용되고, 9는 첫 번째 그림의 경우와 같은 룰이 적용된다.
이제 3차 마방진이 완성되었다. 다시 정리하면 룰은 3가지다.
1)상단경계를 벗어난 경우(첫 번째 그림)
2)좌측경계를 벗어난 경우(두 번째 그림)
3)수치를 넣어야 할 곳에 이미 숫자가 들어가 있거나, 상단과 좌측의 경계를 동시에 벗어난 경우(3번째 그림)
이 룰을 적용하면 홀수 마방진은 n의 범위에 관계없이 아무리 큰 숫자라도 쉽게 구할 수 있다. 1부터 시작해서 n^2까지의 숫자를 위의 룰대로 순서대로 배치해 나가면 완성이 된다.
(4배수 마방진 만들기를 보시려면 링크를 참고 하세요.)
자 이제 이 룰을 적용해서 자바로 프로그램을 만들어 보자. 아래에 소스가 있다.
자바 소스코드001 package org.elseif.magicsquare;
002
003 public class OddMagicSquare {
004 int[][] magicSquare;
005 int coordinateX;
006 int coordinateY;
007 int totalSquare;
008 int dimension;
009 int expectedSum;
010
011 // initialize square
012 void initSquare() {
013 coordinateX = dimension / 2;
014 coordinateY = 0;
015 totalSquare = dimension * dimension;
016 expectedSum = dimension * (dimension * dimension + 1) / 2;
017 magicSquare = new int[dimension][dimension];
018 }
019
020 // make MagicSquare
021 void makeSquare(int n) {
022 dimension = n;
023 initSquare();
024
025 for(int i = 0; i < totalSquare; i++){
026 if(coordinateX >= 0 && coordinateY < 0) {
027 coordinateY = dimension - 1;
028 }
029 if(coordinateX < 0 && coordinateY >= 0) {
030 coordinateX = dimension - 1;
031 }
032 if((coordinateX < 0 && coordinateY <0 ) || magicSquare[coordinateY][coordinateX] != 0){
033 coordinateX++;
034 coordinateY += 2;
035 }
036 magicSquare[coordinateY][coordinateX] = i + 1;
037 coordinateX--;
038 coordinateY--;
039 }
040 }
041
042 // checking Magic Square
043 boolean isMagicSquare() {
044 int checkSumAbs;
045 int checkSumOrd;
046 // check Abscissa and Ordinate
047 for(int i = 0; i < dimension; i++) {
048 checkSumAbs = 0;
049 checkSumOrd = 0;
050 for(int j = 0; j < dimension; j++) {
051 checkSumAbs += magicSquare[i][j];
052 checkSumOrd += magicSquare[j][i];
053 }
054 if(checkSumAbs != expectedSum || checkSumOrd != expectedSum) return false;
055 }
056 // check Diagonal
057 checkSumAbs = 0;
058 checkSumOrd = 0;
059 for(int i = 0; i < dimension; i++) {
060 checkSumAbs += magicSquare[i][i];
061 checkSumOrd += magicSquare[(dimension - 1) - i][i];
062 }
063 if(checkSumAbs != expectedSum || checkSumOrd != expectedSum) return false;
064 return true;
065 }
066
067 // Print Out to Console
068 void printToConsole() {
069 System.out.println("Magic Square");
070 System.out.println("Dimension : " + dimension);
071 System.out.println("Scope of Number : 1 ~ " + totalSquare);
072 System.out.println("Expected Sum = " + expectedSum);
073 System.out.println();
074 for(int i = 0; i < dimension; i++){
075 for(int j = 0; j < dimension; j++){
076 System.out.format("%5d", magicSquare[i][j]);
077 }
078 System.out.println();
079 }
080 System.out.println();
081 if(isMagicSquare() == true) {
082 System.out.println("TEST PASSED: It is a Magic Square");
083 }
084 else {
085 System.out.println("TEST FAILED: It is not a Magic Square");
086 }
087 }
088
089 public static void main(String[] args) {
090 if (args.length == 1 && Integer.parseInt(args[0]) >= 3 && (Integer.parseInt(args[0]) % 2) == 1) {
091 OddMagicSquare ms = new OddMagicSquare();
092 ms.makeSquare(Integer.parseInt(args[0]));
093 ms.printToConsole();
094 }
095 else {
096 System.out.println("Usage: Square n");
097 System.out.println("n must be an integral odd number");
098 }
099 }
100 }
소스에서 실제 마방진을 구하는 메소드는 21~40라인 까지의 makeSquare이다. 3개의 if문이 위의 3가지 룰을 각각 적용한 것이다. 잘 살펴보면 쉽게 이해가 되리라 믿는다. isMagicSquare는 마방진의 가로, 세로, 대각선의 합을 각각 계산하여 만들어진 마방진이 진짜 마방진인가를 검증하기 위한 메소드인데 위에서 정한 규칙대로 정확하게 코딩이 됐다면 굳이 없어도 상관은 없을 것 이다. 왜냐하면 만들어진 마방진은 100% 검증을 통과할 것이기 때문이다.
자 이제 프로그램의 실행 결과를 보자.
실행 결과OddMagicSquare 5
Magic Square
Dimension : 5
Scope of Number : 1 ~ 25
Expected Sum = 65
15 8 1 24 17
16 14 7 5 23
22 20 13 6 4
3 21 19 12 10
9 2 25 18 11
TEST PASSED: It is a Magic Square
OddMagicSquare 9
Magic Square
Dimension : 9
Scope of Number : 1 ~ 81
Expected Sum = 369
45 34 23 12 1 80 69 58 47
46 44 33 22 11 9 79 68 57
56 54 43 32 21 10 8 78 67
66 55 53 42 31 20 18 7 77
76 65 63 52 41 30 19 17 6
5 75 64 62 51 40 29 27 16
15 4 74 72 61 50 39 28 26
25 14 3 73 71 60 49 38 36
35 24 13 2 81 70 59 48 37
TEST PASSED: It is a Magic Square
OddMagicSquare 15
Magic Square
Dimension : 15
Scope of Number : 1 ~ 225
Expected Sum = 1695
120 103 86 69 52 35 18 1 224 207 190 173 156 139 122
121 119 102 85 68 51 34 17 15 223 206 189 172 155 138
137 135 118 101 84 67 50 33 16 14 222 205 188 171 154
153 136 134 117 100 83 66 49 32 30 13 221 204 187 170
169 152 150 133 116 99 82 65 48 31 29 12 220 203 186
185 168 151 149 132 115 98 81 64 47 45 28 11 219 202
201 184 167 165 148 131 114 97 80 63 46 44 27 10 218
217 200 183 166 164 147 130 113 96 79 62 60 43 26 9
8 216 199 182 180 163 146 129 112 95 78 61 59 42 25
24 7 215 198 181 179 162 145 128 111 94 77 75 58 41
40 23 6 214 197 195 178 161 144 127 110 93 76 74 57
56 39 22 5 213 196 194 177 160 143 126 109 92 90 73
72 55 38 21 4 212 210 193 176 159 142 125 108 91 89
88 71 54 37 20 3 211 209 192 175 158 141 124 107 105
104 87 70 53 36 19 2 225 208 191 174 157 140 123 106
TEST PASSED: It is a Magic Square
덧글|신고