알고리즘 - 마방진

마방진(Magic Square)

마방진 : 행과 열, 대각선 숫자의 합이 모두 같은 정사각형 행렬
행렬(Matrix) : 직사각형의 행(row)과 열(column)에 숫자를 배치
이미지 출처 : https://ko.wikipedia.org/wiki/%EB%A7%88%EB%B0%A9%EC%A7%84

---

마방진을 코드로 구현하려면 이차원 배열을 사용해야 한다.

• 이차원 배열(2-dimensional array) : 1차원 배열의 배열(파이썬에서는 리스트의 리스트)
• 이차원 배열의 인덱싱 : array[row][col]
• 이차원 배열을 이용한 마방진의 예시

      magicSquare = [
          [1, 14, 14, 4], --> row
          [11, 7, 6, 9],
          [8, 10, 10, 5],
          [13, 2, 3, 15]
      ]    ㅣ
         column
         
      magicSquare[1] = [11, 7, 6, 9]
      magicSquare[2][3] = 5

---

1. 이차원 배열이 마방진인지 확인

• 이차원 배열의 로우의 값을 더해서 값이 같은지 확인

def checkRow(square):
    for row in range(len(square)):
        sum = 0
        for col in range(len(square)):
            sum += square[row][col]   # 각 로우의 컬럼 값을 더한다.
        print(sum, end=' ')

• 이차원 배열의 칼럼의 값을 더해서 값이 같은지 확인

def checkCol(square):
    for col in range(len(square)):
        sum = 0
        for row in range(len(square)):
            sum += square[col][row]   # 각 컬럼의 로우 값을 더한다.
        print(sum, end=' ')

• 이차원 배열의 대각선의 값을 더해서 값이 같은지 확인

def checkDiagonal(square):
    sum = 0
    for d in range(len(square)):
        sum += square[d][d]   # 왼쪽 시작 대각선은 [0][0]처럼 같은 로우의 같은 컬럼 값이다.
    print(sum, end=' ')
    
    sum = 0   # 오른쪽 시작 대각선 값을 구하기 위해 초기화
    for d in range(len(square)):
        d2 = len(square) -1 -d   # 오른쪽 시작 대각선을 구해야하기 때문에 d2값을 지정해준다.
        sum += square[d][d2]   # [0][3], [1][2],,, 처럼 로우값은 늘리고 컬럼값을 줄여나가며 값을 더해준다. 
    print(sum)

• 마방진 확인

def checkMagic(square):
    magic = 0
    for i in range(len(square)):
        magic += square[0][i]   # 로우, 칼럼, 대각선의 길이가 다 같은지 확인하기 위한 설정값
        
    for i in range(len(square)):
        rsum = 0   # 로우 값
        csum = 0   # 칼럼 값
        for j in range(len(square)):
            rsum += square[i][j]   # 각 로우의 칼럼 값을 더한다.
            csum += square[j][i]   # 각 칼럼의 로우 값을 더한다.
        if rsum != magic or csum != magic:   # 더한값이 앞에서 구한 설정값과 다르면 마방진이 아니다.
            return False
        
    dsum = 0
    d2sum = 0
    for d in range(len(square)):
        d2 = len(square) -1 -d
        dsum += square[d][d]   # 왼쪽 시작 대각선 값을 더한다.
        d2sum += square[d][d2]   # 오른쪽 시작 대각선 갑을 더한다.
        
    if dsum != magic or d2sum != magic:   # 더한값이 앞에서 구한 설정값과 다르면 마방진이 아니다.
        return False
    
    return True   # 더한 값이 앞에서 구한 설정값과 다 같다면 마방진이다.

---

2. 마방진 만들기

• $n$ x $n$ 마방진 만들기 ($n$은 홀수)
  • 첫번째 열의 가운데 행을 1로 채움
  • 해당 위치에서 한 칸 왼쪽, 한 칸 위쪽으로 이동
    • 칸을 벗어나면 그 줄의 반대쪽으로 이동
  • 이동할 위치에 숫자가 이미 있으면 한 칸 아래로 이동
    • 이동할 위치에 숫자가 없으면 이동해서 숫자를 채움
  • 위 과정을 반복
  • 만약 5x5 마방진이면 1 부터 25까지의 숫자로 채움

def makeMagicSquare(n):
    square = [[0] * n for _ in range(n)]   # n x n 마방진 초기값 설정
    
    # 처음 1의 위치 설정값
    row = 0
    col = n // 2
    
    for k in range(1, n*n+1):
        square[row][col] = k
        # 해당 위치에서 한 칸 왼쪽, 한 칸 위쪽으로 이동
        row -= 1
        col -= 1
        
        # 칸을 벗어나면 그 줄의 반대쪽으로 이동
        if row < 0:
            row += n
            
        if col < 0:
            col += n
        
        # 이동할 위치에 숫자가 이미 있으면 한 칸 아래로 이동
        if square[row][col] != 0:
            row = (row + 2) % n   # 인덱스를 벗어나지 않게 설정
            col = (col + 1) % n
            
    return square
    
makeMagicSquare(5)
checkMagic(makeMagicSquare(5))

->
[[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]]
 
True

** 출처

• 주니온TV 아무거나연구소 - 코린아, 코딩하자 (with 파이썬)
• https://ko.wikipedia.org/wiki/%EB%A7%88%EB%B0%A9%EC%A7%84