奇数次の魔法陣を解くアルゴリズムをPythonで実装／Pythonサンプル

目次

奇数次の魔法陣を解くアルゴリズムをPythonで実装

魔法陣とは「N✕Nの正方陣に、1～Nの数字を埋めて、縦横斜めの数字の和をすべて同じにする」ものです。 

いろいろ、解法もあります。

arakan-pgm-ai.hatenablog.com

今回はプログラムで解いてみます。

こちらの本に「N次（奇数）の魔法陣を解く」アルゴリズムなるものが紹介されていましたので、このC言語のプログラムをPythonで書き直してみます。 

[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)

pythonのプログラムソースです

まずは、ソースから。

#
# 魔法陣
# n次（n*n）の魔法陣とは、1からN二乗までの整数を正方形上に並べて
# どの行の和も（N三乗＋N)/2　に等しくなるようにしたもの
#

import numpy as np
import math


def magic_square(order):
    if(order % 2 == 0):
        print("奇数のみです")
    lim = order * order
    k = 0
    tm = np.zeros(lim)
    m_square = tm.reshape([order, order])
    for i in range(-(order - 1) // 2, (order + 1) // 2):
        for j in range(order):
            k = k + 1
            m_square[(j - i + order) % order][(j + i + order) % order] = k
    if(check(m_square, order)):
        print(m_square)


def check(m_square, order):
    ok = (math.pow(order, 3) + order) // 2
    t1 = t2 = t3 = t4 = 0
    for i in range(order):
        t1 += m_square[i][i]
        t2 += m_square[i][order - 1 - i]
    t3 = np.sum(m_square, axis=0)
    t4 = np.sum(m_square, axis=1)
    if(t1 != ok):
        return False
    if(t2 != ok):
        return False
    for x in t3:
        if(x != ok):
            return False
    for y in t4:
        if(y != ok):
            return False
    return True

ちょっとだけ補足 

上記のアルゴリズム事典のC言語のプログラムを、そのままpythonに置き換えました。

ただ、「def check(m,n):」 は、自分が追加しています。

この関数で、できあがった魔法陣の縦・横・斜めのの合計が「ok = (math.pow(n,3) + n) // 2」と等しいかどうかをチェックして、ひとつでも一致しないものがあれば、魔法陣を表示させないようにしてます。

元になったC言語版だと、できあがった魔法陣が正しいかどうか、手作業で縦横斜めの計算をして確認する必要がありました。

でも。

かなり面倒くさいので、検算のロジックとして追加したものです。

実行してみます

magic_square（7）のように、引数に奇数を渡して処理します。

偶数はだめです。

まず「3」から

[4. 3. 8.]
[9. 5. 1.]
[2. 7. 6.]

次は「7」。

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

次は「13」とか。

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

おおーー。

試しに、EXCELに移し替えてみると。

うん、魔法陣だ。

だから・・どうした・・ですけど。

ではでは。