『魔方陣ヌルヌル』別の解法
はじめに
CodeIQ で出題された『魔方陣ヌルヌル』について、公式のまとめ記事が出た後で解説を書こうと思って構想を温めていたのですが、公式まとめ記事に全部書かれてしまったため、ほとんど書くことがなくなってしまいました。
公式まとめ記事
https://codeiq.jp/magazine/2014/06/11455/
一応、問題の内容を大雑把に言うと、
といったところです。また、ここから暗黙にわかることとして、
- 数は正の整数でなくてもよい。
- 数は連続していなくてもよい。
ということが言えます(そうでないと作れない)。
素直な解法
公式まとめ記事では、通常の魔方陣を元に、各マスの数から一定の数を引く方法が紹介されています。私も 3×3 と 5×5 はこの方法で作りました。通常の魔方陣の作り方は、 Wikipedia の魔方陣の記事で非常に詳しく説明されています。
Wikipedia : 魔方陣
http://ja.wikipedia.org/wiki/%E9%AD%94%E6%96%B9%E9%99%A3
4×4 については、公式まとめ記事には「全体を2倍してから 17 を引く」方法と「9 以上の数だけから 17 を引く」方法が解説されていますが、私は「1~16 を -8~8 (ただし途中 0 を飛ばす)にマッピングする」という方法を採りました。まあ、結果的には「9 以上の数だけから 17 を引く」方法と大して変わりません。
別の解法
公式まとめ記事にも Wikipedia にも紹介されていない、別の解法を1つ紹介したいと思います。例として 5×5 のサイズを作りますが、他のサイズにも応用可能です。
まず、和が 0 になるように、中央の1行を次のように作ります。
-2 | -1 | 0 | 1 | 2 |
これを左右に巡回させながら、上下の行に並べます。
0 | 1 | 2 | -2 | -1 |
-1 | 0 | 1 | 2 | -2 |
-2 | -1 | 0 | 1 | 2 |
2 | -2 | -1 | 0 | 1 |
1 | 2 | -2 | -1 | 0 |
これで、タテ・ヨコ・ナナメの和が 0 の行列を作ることができました。しかし、このままでは、同じ数が使われてしまっています。
次に、これと同じようなものを、もう1つ作ります。ただし、中央の行は
-10 | -5 | 0 | 5 | 10 |
とし、巡回の向きも逆になるようにします。
5 | 10 | -10 | -5 | 0 |
10 | -10 | -5 | 0 | 5 |
-10 | -5 | 0 | 5 | 10 |
-5 | 0 | 5 | 10 | -10 |
0 | 5 | 10 | -10 | -5 |
もちろん、この行列も、タテ・ヨコ・ナナメの和が 0 になっていますね。
最後に、この2つの行列を加えます。
|
+ |
|
= |
|
これで 5×5 ヌルヌル魔方陣の完成です!
めでたし、めでたし。
ちなみに、サイズが奇数×奇数の場合には、この方法で数が連続するヌルヌル魔方陣を作ることができるので、最小の数が 1 になるように全体に一定の数を加えれば、普通の魔方陣になります。