[Algorithms] Magic Square | 마방진

Magic Square

마방진

각 행의 합, 각 열의 합, 주대각선의 합이 모두 같은 n X n Matrix를 의미한다.
- n X n Matrix는 1부터 \(n^2\)까지의 정수로 채워진다.

Example. 5 X 5 Magic Square

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

---

Implementation in C++

void Magic(const int n) {
    const int MaxSize = 51;
    int square[MaxSize][MaxSize], k, l;
    
    if( (n < MaxSize) || (n < 1) )
        throw "Error! n out of range";
    else if( !(n%2) )
        throw "Error! n is even";
        
    for(int i = 0; i < n; i++)
        fill(square[i], square[i]+n, 0);
    square[0][(n-1/2)] = 1;
    
    int key = 2;
    int i = 0;
    int j = (n - 1) / 2;
    
    while(key <= n * n) {
        if(i - 1 < 0)
            k = n - 1;
        else
            k = i - 1;
        
        if(j - 1 < 0)
            l = n - 1;
        else
            l = j - 1;
        
        if(square[k][l])
            i = (i + 1) % n;
        else {
            i = k;
            j = l;
        }
        
        square[i]j[] = key;
        key++;
    }
    
    std::cout << "Magic Square of Size " << n << std::endl;
    for(int i; i < n; i++) {
        copy(square[i], square[i] + n, ostream_iterator<int>(cout, " "));
        std::cout << std::endl;
    }
}          

- 첫 번째 행의 중앙에 1을 삽입한다.
- 빈 정방형에 1씩 큰 수를 할당하며 왼쪽 대각선 방향으로 올라간다.
- 만약 정방형 밖으로 벗어나게 된다면, 정방형의 반대편 자리에서 계속한다.
  (즉, 상단을 벗어나면 같은 열 최하단으로, 왼쪽으로 벗어나면 같은 행의 제일 오른쪽으로 이동한다.)
- 정방형이 어떠한 숫자로 이미 채워져있는 경우, 밑으로 움직여서 수를 할당한다.

---

Reference: Fundamentals of Data Structure in C++ (Horowitz, Sahni, Mehta 저, Silicon Press, 2006)