Kitajima Akimasa, Kikuchi Macoto
Research and Legislative Reference Bureau, National Diet Library, Chiyoda-ku, Tokyo, Japan; Department of Physics, Graduate School of Science, Osaka university, Toyonaka, Osaka, Japan.
Large-Scale Computational Science Division, Cybermedia center, Osaka University, Toyonaka, Osaka, Japan; Department of Physics, Graduate School of Science, Osaka university, Toyonaka, Osaka, Japan.
PLoS One. 2015 May 14;10(5):e0125062. doi: 10.1371/journal.pone.0125062. eCollection 2015.
How rare are magic squares? So far, the exact number of magic squares of order n is only known for n ≤ 5. For larger squares, we need statistical approaches for estimating the number. For this purpose, we formulated the problem as a combinatorial optimization problem and applied the Multicanonical Monte Carlo method (MMC), which has been developed in the field of computational statistical physics. Among all the possible arrangements of the numbers 1; 2, …, n(2) in an n × n square, the probability of finding a magic square decreases faster than the exponential of n. We estimated the number of magic squares for n ≤ 30. The number of magic squares for n = 30 was estimated to be 6.56(29) × 10(2056) and the corresponding probability is as small as 10(-212). Thus the MMC is effective for counting very rare configurations.
幻方有多罕见？到目前为止，仅知道n≤5时n阶幻方的确切数量。对于更大的方阵，我们需要用统计方法来估计数量。为此，我们将该问题表述为一个组合优化问题，并应用了在计算统计物理领域中发展起来的多正则蒙特卡罗方法（MMC）。在n×n方阵中数字1、2、…、n²的所有可能排列中，找到幻方的概率下降速度比n的指数还要快。我们估计了n≤30时幻方的数量。n = 30时幻方的数量估计为6.56(29)×10²⁰⁵⁶，相应的概率小至10⁻²¹²。因此，MMC对于计算非常罕见的构型很有效。
