カメヲラボ

主にプログラミングとお勉強全般について書いてます

魔方陣ヌルヌル【解説】

本稿はCodeIQで2014年5月12日~同年6月2日に出題された「魔方陣ヌルヌル」という問題の解法に関する記事です。

問題文はこちら

方陣ヌルヌル【解説】

通常の魔方陣とは少し違いますが、全体から同じ数だけ差し引いてしまえば、簡単に作ることができます。通常の魔方陣は、簡単な作り方が知られています。情報もたくさん出ていますので、ここでは省略しておきます。知らないという方は、 Wikipediaの魔方陣 をご覧ください。

◆ヌルヌル魔方陣の作り方

  • 3×3のヌルヌル魔方陣
276
951
438

をベースに作ってみます。 この魔方陣は、各列の合計が15になっていますので、15÷3で各マス目から5を引いてしまえば、3×3のヌルヌル魔方陣を作ることができます。

-321
40-4
-1-23
  • 4×4のヌルヌル魔方陣
162313
511108
97612
414151

をベースに作ります。各列の和は34ですが、34÷4は割り切れません。そこで、まず全体を2倍してしまいます。

324626
10222016
18141224
828302

全体を2倍すれば、各列の和は68となり、4で割り切れます。68÷4の17を全体から差し引くことで、

15-13-119
-753-1
1-3-57
-91113-15

が得られます。

挑戦者のiehnさんの解答では、2倍せずに「9以上のところから17引く」という方法で、1から8の数字のみを使ったヌルヌル魔方陣を得ています。これは綺麗ですね。

-123-4
5-6-78
-876-5
4-3-21
  • 5×5のヌルヌル魔方陣
31692215
20821142
72513119
24125186
114171023

をベースに、3×3の場合とまったく同じように作ってみます。各列の和が65ですから、65÷5で13ずつ差し引きます。

簡単ですね?

◆プログラミングでの解答

方陣の生成ルールはすでに知られていますので、それをそのまま利用し、汎用的なプログラムを作成した方も、算術的な考えはあまりせず、純粋に探索プログラムを書いてくださった方も結構いらっしゃいました。

算術的に生成する方法はあえて説明する必要がないと思いますので、探索プログラムについて少し説明しておきます。

全探索の場合、3×3の魔方陣を作る場合は9! = 362880通り、4×4では16! = 20922789888000通り、5×5では25! = 15511210043330985984000000通りと、頑張っても4×4辺りが限度になってしまいます。5×5まで解が得られている方は、何らかの方法で計算量を減らすことに成功しています。

単純な枝刈りとして、すべてのマスを埋める前の段階、たとえば1列が埋まった段階で、合計値が条件を満たしているかどうかのような計算を行い、条件を満たしていなければそこから先の探索は行わないようなルールにしておけば、それだけでかなり計算量を落とすことができます。

しかしその方法では、4×4あたりまでは解が得られますが、5×5になると計算が終わりません。そこで、探索順序を工夫します。左上のマス目から1行ずつ探索する場合、次のようなイメージになります。

このような探索順序ではなく、次のように、対角線上のマス目から探索します。対角線上以外の順序もある程度影響はありますが、対角線上と比べると重要ではありませんので、まずは適当に決めておきましょう。

このような探索順序で、1列埋まるごとに枝刈りしてやるだけで、劇的に速くなります。解をいくつか見つけるだけでしたら、この方法だけで十分です。全列挙となると、もう少し探索順序を工夫するとか、回転等の考慮が必要になりますが、工夫すればするだけ、目に見えて速くなるはずです。

探索プログラムを書いてみたけど、すべてのサイズで解が得られなかった、という方は参考にしてみてください。

ちなみに、探索順序を適当に変えてみたところ、次のような探索順序にすると非常に高速になりました。まだまだ速くなるかもしれませんね。

興味のある方は こちら に、探索順序を自由に変更するプログラムがあります。試してみてください。

-103-492
7-581-11
-6120-126
11-1-85-7
-2-94-310