magic square (마방진) [일반해] by 바죠

magic square (마방진)

http://en.wikipedia.org/wiki/Magic_square
http://mathworld.wolfram.com/MagicSquare.html

가로줄 합= 세로줄 합= 주 대각선 줄(2개) 합 = magic constant가 되는 n x n 행렬( 여기서 n >2)

마방진은 1에서 N제곱까지 모든 숫자들을 한 번씩만 사용해서 N행 N열의 배열을 만들었을 때,
어떤 행이나, 어떤 열이나, 두 대각선 방향이나,  숫자들의 합이 항상 같아지는 배열을 말한다.

n x n matrix에 1부터 n x n 까지의 숫자를 채워넣어서 위의 조건을 만족하게 배열할 수 있을까?
아래 경우와 같이 1,2,...9 숫자들을 한 번씩만 사용해서 가로줄 합=세로줄 합=대각선 줄 합=15가 되게하는 3x3 matrix를 만들수 있다.

이 때, n>= 3 일 경우에 적용하면 magic constant= (n x n x n+n)/2
15, 34, 65, 111, 175, 260과 같은 수들을 얻을 수 있다.

n 값이 홀수 일때, 즉, 3, 5, 7, 9.... 일반적인 답안이 존재한다.

n 값이 4의 배수 일 때, 즉, doubly even(4, 8, 12,....), 역시 컴퓨터 프로그램을 활용하면 쉽게 만들 수 있다. 일반적인 해이다.

n 값이 2의 배수 일 때, 즉, singly even(6, 10, 14,....), 역시 컴퓨터 프로그램을 활용하면 쉽게 만들 수 있다. 일반적이 해이다. 

     


-----------------------------------------------------------------------------------------------------------------    
    15    12     2     5
     6     1    11    16
     9    14     8     3
     4     7    13    10


     2    20    23    13    21    32
    31     5    14    35     4    22
    36     7    19    11    29     9
    24    15    28    25    16     3
    12    30     1    17    33    18
     6    34    26    10     8    27
-----------------------------------------------------------------------------------------------------------------    
!      Written by In-Ho Lee, KRISS, January 24, 2017
       program magicsquare_generator
       implicit none
       integer ms0
       integer, allocatable :: mat(:,:),kprod(:),iprod(:),jprod(:)
       integer i,j,k0
       logical lmagic
       real*8 var

       write(6,*)'Enter matrix order: > 2 '
       read(5,*) ms0
       allocate(mat(ms0,ms0))
       allocate(kprod(2),iprod(ms0),jprod(ms0))
       if(mod(ms0,2) == 1)then
       call oddmagicsquare(ms0,mat)
                          else
       if(mod(ms0,4) == 0)then
       call dbeven(ms0,mat)
                          else
       call sgeven(ms0,mat)
                          endif
                          endif
       call comp1(ms0,mat,iprod,jprod,kprod)
       call comp3(ms0,mat,lmagic,iprod,jprod,kprod)
       call comp4(ms0,mat,var,iprod,jprod,kprod)
       write(6,*) lmagic,var
       write(6,'(90i9)') kprod(1),kprod(2),(iprod(i),i=1,ms0),(jprod(i),i=1,ms0)
       do i=1,ms0
       write(6,'(90i6)') (mat(i,j),j=1,ms0)
       enddo
       k0=(ms0**3+ms0)/2
       write(6,*) k0,' magic constatnt, order ',ms0
       deallocate(mat) ; deallocate(iprod,jprod,kprod)
       end program magicsquare_generator
!234567890
!      Written by In-Ho Lee, KRISS, January 24, 2017
       subroutine dbeven(n,mat)
       integer n,mat(n,n)
       integer i,j,id
       integer, allocatable :: imat(:,:),jmat(:,:)

       allocate(imat(n,n),jmat(n,n))
       id=1
       do i=1,n
       do j=1,n
       imat(i,j)=(mod(i,4))/2
       jmat(j,i)=(mod(i,4))/2
       mat(i,j)=id
       id=id+1
       enddo
       enddo
       do i=1,n
       do j=1,n
       if(imat(i,j) == jmat(i,j)) mat(i,j)=n*n+1-mat(i,j)
       enddo
       enddo
       deallocate(imat,jmat)
       return
       end
!234567890
!      Written by In-Ho Lee, KRISS, January 24, 2017
       subroutine sgeven(n,mat)
       integer n,mat(n,n)
       integer, allocatable :: matodd(:,:),mat0(:,:),matodd0(:,:)
       integer, allocatable :: iqf(:)
       integer nsquare,n2,n4,nl,nr,itmp,i,j

       nsquare=n*n ; n2=n/2 ; n4=nsquare/4
       allocate(matodd(n2,n2)) ; allocate(matodd0(0:n2-1,0:n2-1))
       call oddmagicsquare(n2,matodd)
       do i=1,n2
       do j=1,n2
       matodd0(i-1,j-1)=matodd(i,j)
       enddo
       enddo
       allocate(mat0(0:n-1,0:n-1)) ; allocate(iqf(0:3))
       iqf(0)=0 ; iqf(1)=2 ; iqf(2)=3 ; iqf(3)=1
       do i=0,n-1
       do j=0,n-1
       iq=(i/n2)*2+(j/n2)
       mat0(i,j)=matodd0(mod(i,n2),mod(j,n2))
       mat0(i,j)=mat0(i,j)+iqf(iq)*n4
       enddo
       enddo
       nl=n2/2 ; nr=nl-1
       do i=0,n2-1
       do j=0,n-1
       if(j < nl .or. j >= n-nr .or. (j == nl .and. i == nl))then
       if(j == 0 .and. i == nl) cycle
       itmp=mat0(i,j) ; mat0(i,j)=mat0(i+n2,j) ; mat0(i+n2,j)=itmp
                                                             endif
       enddo
       enddo
       do i=1,n
       do j=1,n
       mat(i,j)=mat0(i-1,j-1)
       enddo
       enddo
       deallocate(matodd,matodd0) ; deallocate(mat0,iqf)
       return
       end
!234567890
!      Written by In-Ho Lee, KRISS, January 24, 2017
       subroutine oddmagicsquare(n,mat)
       integer n,mat(n,n)
       integer i,j

       do i=1,n
       do j=1,n
       mat(i,j)=n*mod(i+j-1+(n/2),n)+mod(i+2*j-2,n)+1
       enddo
       enddo
       return
       end
!234567890
!      Written by In-Ho Lee, KRISS, January 24, 2017
       subroutine comp1(ms,mat,iprod,jprod,kprod)
       implicit none
       integer ms,mat(ms,ms)
       integer iprod(ms),jprod(ms),kprod(2)
       integer i,j

       do j=1,ms
       iprod(j)=0
       do i=1,ms
       iprod(j)=iprod(j)+mat(i,j)
       enddo
       enddo
       do i=1,ms
       jprod(i)=0
       do j=1,ms
       jprod(i)=jprod(i)+mat(i,j)
       enddo
       enddo
       kprod(1)=0 ; kprod(2)=0
       do i=1,ms
       kprod(1)=kprod(1)+mat(i,i) ; kprod(2)=kprod(2)+mat(i,ms-i+1)
       enddo
       end
!234567890
!      Written by In-Ho Lee, KRISS, January 24, 2017
       subroutine comp3(ms,mat,lmagic,iprod,jprod,kprod)
       implicit none
       integer ms,mat(ms,ms)
       integer iprod(ms),jprod(ms),kprod(2)
       logical lmagic
       integer i,j

       lmagic=.false.
       if(kprod(1) /= kprod(2)) return
       do i=1,ms
       if(kprod(1) /= iprod(i)) return
       if(kprod(1) /= jprod(i)) return
       enddo
       do i=1,ms
       do j=1,ms
       if(iprod(i) /= jprod(j)) return
       enddo
       enddo
       lmagic=.true.
       end
!234567890
!      Written by In-Ho Lee, KRISS, January 24, 2017
       subroutine comp4(ms,mat,var,iprod,jprod,kprod)
       implicit none
       integer ms,mat(ms,ms)
       integer iprod(ms),jprod(ms),kprod(2)
       real*8 var
       integer i
       real*8 avg

       avg=kprod(1)+kprod(2)
       do i=1,ms
       avg=avg+iprod(i)
       enddo
       do i=1,ms
       avg=avg+jprod(i)
       enddo
       avg=avg/float(2*ms+2)
       var=(kprod(1)-avg)**2+(kprod(2)-avg)**2
       do i=1,ms
       var=var+(iprod(i)-avg)**2
       enddo
       do i=1,ms
       var=var+(jprod(i)-avg)**2
       enddo
       var=var/float(2*ms+2)
       end
!234567890
 
----------------------------------------------------------------------------------------------------------------------

     8     1     6
     3     5     7
     4     9     2
         

    16     2     3    13
     5    11    10     8
     9     7     6    12
     4    14    15     1
        

    17    24     1     8    15
    23     5     7    14    16
     4     6    13    20    22
    10    12    19    21     3
    11    18    25     2     9
         

    35     1     6    26    19    24
     3    32     7    21    23    25
    31     9     2    22    27    20
     8    28    33    17    10    15
    30     5    34    12    14    16
     4    36    29    13    18    11
        

    30    39    48     1    10    19    28
    38    47     7     9    18    27    29
    46     6     8    17    26    35    37
     5    14    16    25    34    36    45
    13    15    24    33    42    44     4
    21    23    32    41    43     3    12
    22    31    40    49     2    11    20
       

    64     2     3    61    60     6     7    57
     9    55    54    12    13    51    50    16
    17    47    46    20    21    43    42    24
    40    26    27    37    36    30    31    33
    32    34    35    29    28    38    39    25
    41    23    22    44    45    19    18    48
    49    15    14    52    53    11    10    56
     8    58    59     5     4    62    63     1
       

    47    58    69    80     1    12    23    34    45
    57    68    79     9    11    22    33    44    46
    67    78     8    10    21    32    43    54    56
    77     7    18    20    31    42    53    55    66
     6    17    19    30    41    52    63    65    76
    16    27    29    40    51    62    64    75     5
    26    28    39    50    61    72    74     4    15
    36    38    49    60    71    73     3    14    25
    37    48    59    70    81     2    13    24    35
         

    92    99     1     8    15    67    74    51    58    40
    98    80     7    14    16    73    55    57    64    41
     4    81    88    20    22    54    56    63    70    47
    85    87    19    21     3    60    62    69    71    28
    86    93    25     2     9    61    68    75    52    34
    17    24    76    83    90    42    49    26    33    65
    23     5    82    89    91    48    30    32    39    66
    79     6    13    95    97    29    31    38    45    72
    10    12    94    96    78    35    37    44    46    53
    11    18   100    77    84    36    43    50    27    59
        

    68    81    94   107   120     1    14    27    40    53    66
    80    93   106   119    11    13    26    39    52    65    67
    92   105   118    10    12    25    38    51    64    77    79
   104   117     9    22    24    37    50    63    76    78    91
   116     8    21    23    36    49    62    75    88    90   103
     7    20    33    35    48    61    74    87    89   102   115
    19    32    34    47    60    73    86    99   101   114     6
    31    44    46    59    72    85    98   100   113     5    18
    43    45    58    71    84    97   110   112     4    17    30
    55    57    70    83    96   109   111     3    16    29    42
    56    69    82    95   108   121     2    15    28    41    54
         

   144     2     3   141   140     6     7   137   136    10    11   133
    13   131   130    16    17   127   126    20    21   123   122    24
    25   119   118    28    29   115   114    32    33   111   110    36
   108    38    39   105   104    42    43   101   100    46    47    97
    96    50    51    93    92    54    55    89    88    58    59    85
    61    83    82    64    65    79    78    68    69    75    74    72
    73    71    70    76    77    67    66    80    81    63    62    84
    60    86    87    57    56    90    91    53    52    94    95    49
    48    98    99    45    44   102   103    41    40   106   107    37
   109    35    34   112   113    31    30   116   117    27    26   120
   121    23    22   124   125    19    18   128   129    15    14   132
    12   134   135     9     8   138   139     5     4   142   143     1


    93   108   123   138   153   168     1    16    31    46    61    76    91
   107   122   137   152   167    13    15    30    45    60    75    90    92
   121   136   151   166    12    14    29    44    59    74    89   104   106
   135   150   165    11    26    28    43    58    73    88   103   105   120
   149   164    10    25    27    42    57    72    87   102   117   119   134
   163     9    24    39    41    56    71    86   101   116   118   133   148
     8    23    38    40    55    70    85   100   115   130   132   147   162
    22    37    52    54    69    84    99   114   129   131   146   161     7
    36    51    53    68    83    98   113   128   143   145   160     6    21
    50    65    67    82    97   112   127   142   144   159     5    20    35
    64    66    81    96   111   126   141   156   158     4    19    34    49
    78    80    95   110   125   140   155   157     3    18    33    48    63
    79    94   109   124   139   154   169     2    17    32    47    62    77


   177   186   195     1    10    19    28   128   137   146    99   108    68    77
   185   194   154     9    18    27    29   136   145   105   107   116    76    78
   193   153   155    17    26    35    37   144   104   106   115   124    84    86
     5   161   163   172    34    36    45   103   112   114   123   132    85    94
   160   162   171    33    42    44     4   111   113   122   131   140    93    53
   168   170   179    41    43     3    12   119   121   130   139   141    52    61
   169   178   187    49     2    11    20   120   129   138   147   100    60    69
    30    39    48   148   157   166   175    79    88    97    50    59   117   126
    38    47     7   156   165   174   176    87    96    56    58    67   125   127
    46     6     8   164   173   182   184    95    55    57    66    75   133   135
   152    14    16    25   181   183   192    54    63    65    74    83   134   143
    13    15    24   180   189   191   151    62    64    73    82    91   142   102
    21    23    32   188   190   150   159    70    72    81    90    92   101   110
    22    31    40   196   149   158   167    71    80    89    98    51   109   118


   122   139   156   173   190   207   224     1    18    35    52    69    86   103   120
   138   155   172   189   206   223    15    17    34    51    68    85   102   119   121
   154   171   188   205   222    14    16    33    50    67    84   101   118   135   137
   170   187   204   221    13    30    32    49    66    83   100   117   134   136   153
   186   203   220    12    29    31    48    65    82    99   116   133   150   152   169
   202   219    11    28    45    47    64    81    98   115   132   149   151   168   185
   218    10    27    44    46    63    80    97   114   131   148   165   167   184   201
     9    26    43    60    62    79    96   113   130   147   164   166   183   200   217
    25    42    59    61    78    95   112   129   146   163   180   182   199   216     8
    41    58    75    77    94   111   128   145   162   179   181   198   215     7    24
    57    74    76    93   110   127   144   161   178   195   197   214     6    23    40
    73    90    92   109   126   143   160   177   194   196   213     5    22    39    56
    89    91   108   125   142   159   176   193   210   212     4    21    38    55    72
   105   107   124   141   158   175   192   209   211     3    20    37    54    71    88
   106   123   140   157   174   191   208   225     2    19    36    53    70    87   104


   256     2     3   253   252     6     7   249   248    10    11   245   244    14    15   241
    17   239   238    20    21   235   234    24    25   231   230    28    29   227   226    32
    33   223   222    36    37   219   218    40    41   215   214    44    45   211   210    48
   208    50    51   205   204    54    55   201   200    58    59   197   196    62    63   193
   192    66    67   189   188    70    71   185   184    74    75   181   180    78    79   177
    81   175   174    84    85   171   170    88    89   167   166    92    93   163   162    96
    97   159   158   100   101   155   154   104   105   151   150   108   109   147   146   112
   144   114   115   141   140   118   119   137   136   122   123   133   132   126   127   129
   128   130   131   125   124   134   135   121   120   138   139   117   116   142   143   113
   145   111   110   148   149   107   106   152   153   103   102   156   157    99    98   160
   161    95    94   164   165    91    90   168   169    87    86   172   173    83    82   176
    80   178   179    77    76   182   183    73    72   186   187    69    68   190   191    65
    64   194   195    61    60   198   199    57    56   202   203    53    52   206   207    49
   209    47    46   212   213    43    42   216   217    39    38   220   221    35    34   224
   225    31    30   228   229    27    26   232   233    23    22   236   237    19    18   240
    16   242   243    13    12   246   247     9     8   250   251     5     4   254   255     1


----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------

관련 이미지
----------------------------------------------------------------------------------------------------------------------

def magic_square(matrix):
   size=len(matrix[0])
   sum_list=[]
   for col in range(size): #Vertical sum
       sum_list.append(sum(row[col] for row in matrix))
   sum_list.extend([sum(lines) for lines in matrix])#Horizontal sum
   result1=0
   for i in range(0,size):
       result1+=matrix[i][i]
   sum_list.append(result1)
   result2=0
   for i in range(size-1,-1,-1):
       result2+=matrix[i][i]
   sum_list.append(result2)
   if len(set(sum_list))>1:
       return False
   return True


print(magic_square( [[1, 2, 3], [ 4, 5, 6], [7, 8, 9]]))
print(magic_square( [[2, 7, 6], [ 9, 5, 1], [4, 3, 8]]))


----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------


덧글

댓글 입력 영역

최근 포토로그



MathJax