目次
奇数次の魔法陣を解くアルゴリズムをPythonで実装
魔法陣とは「N✕Nの正方陣に、1~Nの数字を埋めて、縦横斜めの数字の和をすべて同じにする」ものです。
いろいろ、解法もあります。
今回はプログラムで解いてみます。
こちらの本に「N次(奇数)の魔法陣を解く」アルゴリズムなるものが紹介されていましたので、このC言語のプログラムをPythonで書き直してみます。
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
- 作者: 奥村晴彦
- 出版社/メーカー: 技術評論社
- 発売日: 2018/04/19
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
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に移し替えてみると。
うん、魔法陣だ。
だから・・どうした・・ですけど。
ではでは。