「魔方陣ヌルヌル」解答と解説
こんにちは、Ozyです。
タテ・ヨコ・ナナメ、すべての合計が0（null）になる魔方陣を作る問題「魔方陣ヌルヌル」を出題しました。まずはご参加いただいた114名の皆さん、どうもありがとうございます。
通常の魔方陣とは少し違いますが、全体から同じ数だけ差し引いてしまえば、簡単に作ることができます。通常の魔方陣は、簡単な作り方が知られています。情報もたくさん出ていますので、ここでは省略しておきます。知らないという方は、 Wikipediaの魔方陣 をご覧ください。
ヌルヌル魔方陣の作り方
3×3のヌルヌル魔方陣
| 2 | 7 | 6 |
| 9 | 5 | 1 |
| 4 | 3 | 8 |
をベースに作ってみます。
この魔方陣は、各列の合計が15になっていますので、15÷3で各マス目から5を引いてしまえば、3×3のヌルヌル魔方陣を作ることができます。
| -3 | 2 | 1 |
| 4 | 0 | -4 |
| -1 | -2 | 3 |
4×4のヌルヌル魔方陣
| 16 | 2 | 3 | 13 |
| 5 | 11 | 10 | 8 |
| 9 | 7 | 6 | 12 |
| 4 | 14 | 15 | 1 |
をベースに作ります。各列の和は34ですが、34÷4は割り切れません。そこで、まず全体を2倍してしまいます。
| 32 | 4 | 6 | 26 |
| 10 | 22 | 20 | 16 |
| 18 | 14 | 12 | 24 |
| 8 | 28 | 30 | 2 |
全体を2倍すれば、各列の和は68となり、4で割り切れます。68÷4の17を全体から差し引くことで、
| 15 | -13 | -11 | 9 |
| -7 | 5 | 3 | -1 |
| 1 | -3 | -5 | 7 |
| -9 | 11 | 13 | -15 |
が得られます。
挑戦者のiehnさんの解答では、2倍せずに「9以上のところから17引く」という方法で、1から8の数字のみを使ったヌルヌル魔方陣を得ています。これは綺麗ですね。
| -1 | 2 | 3 | -4 |
| 5 | -6 | -7 | 8 |
| -8 | 7 | 6 | -5 |
| 4 | -3 | -2 | 1 |
5×5のヌルヌル魔方陣
| 3 | 16 | 9 | 22 | 15 |
| 20 | 8 | 21 | 14 | 2 |
| 7 | 25 | 13 | 1 | 19 |
| 24 | 12 | 5 | 18 | 6 |
| 11 | 4 | 17 | 10 | 23 |
をベースに、3×3の場合とまったく同じように作ってみます。各列の和が65ですから、65÷5で13ずつ差し引いてあげます。
| -10 | 3 | -4 | 9 | 2 |
| 7 | -5 | 8 | 1 | -11 |
| -6 | 12 | 0 | -12 | 6 |
| 11 | -1 | -8 | 5 | -7 |
| -2 | -9 | 4 | -3 | 10 |
簡単ですね？
プログラミングでの解答
魔方陣の生成ルールはすでに知られていますので、それをそのまま利用し、汎用的なプログラムを作成した方も、算術的な考えはあまりせず、純粋に探索プログラムを書いてくださった方も結構いらっしゃいました。
算術的に生成する方法はあえて説明する必要がないと思いますので、探索プログラムについて少し説明しておきます。
全探索の場合、3×3の魔方陣を作る場合は9! = 362880通り、4×4では16! = 20922789888000通り、5×5では25! = 15511210043330985984000000通りと、頑張っても4×4辺りが限度になってしまいます。5×5まで解が得られている方は、何らかの方法で計算量を減らすことに成功しています。
単純な枝刈りとして、すべてのマスを埋める前の段階、たとえば1列が埋まった段階で、合計値が条件を満たしているかどうかのような計算を行い、条件を満たしていなければそこから先の探索は行わないようなルールにしておけば、それだけでかなり計算量を落とすことができます。
しかしその方法では、4×4あたりまでは解が得られますが、5×5になると計算が終わりません。そこで、探索順序を工夫します。左上のマス目から1行ずつ探索する場合、次のようなイメージになります。
このような探索順序ではなく、次のように、対角線上のマス目から探索します。対角線上以外の順序もある程度影響はありますが、対角線上と比べると重要ではありませんので、まずは適当に決めておきましょう。
このような探索順序で、1列埋まるごとに枝刈りしてやるだけで、劇的に速くなります。解をいくつか見つけるだけでしたら、この方法だけで十分です。全列挙となると、もう少し探索順序を工夫するとか、回転等の考慮が必要になりますが、工夫すればするだけ、目に見えて速くなるはずです。
探索プログラムを書いてみたけど、すべてのサイズで解が得られなかった、という方は参考にしてみてください。
ちなみに、探索順序を適当に変えてみたところ、次のような探索順序にすると非常に高速になりました。まだまだ速くなるかもしれませんね。
興味のある方は こちら に、探索順序を自由に変更するプログラムがあります。試してみてください。
解き方・使用言語
最初に述べた方法で解を得ることはできますので、手計算で解答という方が多数でしたが、プログラムを書いて6×6以上の大きな魔方陣を作ったり、探索プログラムを書いたり乱数を利用したプログラムを書いてくださった方もいらっしゃいました。
| 言語 | 人数 |
|---|---|
| C/C++ | 11 |
| Python | 7 |
| Ruby | 5 |
| Java | 4 |
| JavaScript | 3 |
| C# | 2 |
| Haskell | 2 |
| PHP | 2 |
| Scala | 2 |
| Alloy | 1 |
| Awk | 1 |
| Forth | 1 |
| Fortran | 1 |
| Maxima | 1 |
| Octave | 1 |
| Perl | 1 |
| Prolog | 1 |
| VBA | 1 |
| 手計算・その他 | 67 |
勝手に表彰！
何も賞品はありませんが、採点していて印象に残った解答者をご紹介します。
ハイクオリティ賞（debiruさん）
debiruさんの解答 は、解法の説明・証明・コードすべてが非常に丁寧に書かれていて、この記事も「debiruさんの解答をコピペした方が手っ取り早いんじゃないか」と思ったほどです。素晴らしかったです。
がっつりコード賞（19名・敬称略）
手計算の多い中、探索プログラムをしっかり組んで解答された方や、一般的な魔方陣の作り方を実装し、ある程度汎用性のあるプログラムをご提出くださった方です。’Code’IQ感満載です！
sapics, ciel, alluser, rotary-o, gkyy20,
mamekin, tomwot, じゃい, robert, kuuso,
Mu, himox_x, naoki_kp, EEL733, NeoCat,
tsuno202, 24D, ふじいり, knightrogen, mmuraki,
tochukaso, てるてるぼーず, Chatnoir, にぃちぇ, 春日太郎,
resterror, thr88, okasho-hato, gasbombe
言語パワー賞（6名・敬称略）
言語の特性とか、ソルバを利用してさらりと解いた方にこの賞を。
ソルバもいろいろあるんですね。
ushsh, キャロットフレーク, autotaker,
KTazakik, electrolysis, tmpvar
ショートコード書いちゃった賞（tmftakeさん）
コードを書くこと自体結構大変なので、まさかとは思っていましたが、やはりいましたショートコーダー。ここでコードを晒してしまおうかとも思いましたが、将来的にショートコーディング問題として出題するかもしれないので、コードは載せないことにしておきます。
興味のある方はチャレンジしてみてください。
最後に
魔方陣は有名だけど、ちょっと難しいかな？と思っておりましたが、正解者・解答内容を見る限り全く問題なさそうでしたね。CodeIQで出題を始めてから、優秀な方が日増しに増えているように感じます。問題のレベルもさらに上げていかなければいけませんね！
それではまた。
CodeIQ運営事務局より
Ozyさん著の元祖ショートコーディング本の復刻版『ショートコーディング 職人達の技法』を、この「魔方陣ヌルヌル」問題に正解した方の中から抽選で3名さまにプレゼントします！
当選者はCodeIQ運営事務局よりCodeIQに登録しているメールアドレス宛に連絡をいたします。 挑戦された方は、ぜひメールをチェックしてみてください！
※本の中身については、Ozyさんからの寄稿記事をご覧ください。