2D マップ上の最短パスを求める新しいアルゴリズム S* の提案
はじめに
ゲームのキャラクタを自動で移動させる場合などに、 2D マップ上の２点間の最短パスを求めることが行われます。
典型的なやり方としては、マップを格子状のマス目に分割し、マス目ごとに通れるか通れないかを決定しておき、キャラクタの現在地である開始点と、目的地となる終了点との２点間のパス（経路）を A* アルゴリズムで求める、という方法が一般的かと思います。
しかし、マップをマス目に分割するのは、本当に必要なことなのでしょうか？ もっと直接的に、幾何学的な最短パスを A* で求めればいいのではないでしょうか？ ちょっと実装して実験してみました。
デモ
未署名の Java アップレットですすんません。 Java の設定でセキュリティを下げて実行してくださいすんません。
線の色は、パスの長さを表しています。パスが切り替わったときにも線の色が不連続には変化していないことから、等しい長さのパスの間で切り替わっていることが確認できます。
２点を変化させながらリアルタイムに探索していますが、 CPU をほとんど使っていないことがわかります。
S* アルゴリズム
上のデモで実装したアルゴリズムを、とりあえず「S*」と呼ぶことにします。「 Saito の A*」 の略です。単純なアルゴリズムなので、考え付いたのは私が最初というわけでもないでしょうし、既にちゃんとした名前があるようにも思いますが、知りません。
アルゴリズムの内容は、上のデモから一目瞭然なのですが、次のような感じです。
準備
- マップ上の障害物を、多角形で近似する。（上のデモでは、障害物の形状自体を三角形にしています。）
- 多角形の頂点同士を結ぶ線分のうち、多角形の内部を通過しないもののリスト（頂点間リスト）を作成する。
探索
- 頂点間リストに、開始点と終了点を一時的に追加する。
- 開始点から終了点に向かって、頂点間リストに A* アルゴリズムを適用する。このとき、 A* のヒューリスティック関数には、終了点までのユークリッド距離を用いる。
以上です。とてもシンプルですね！
マス目 A* との比較
従来の探索方法を、ここでは「マス目 A* 」と呼ぶことにします。
S* の利点
- マス目に分割する必要がない。（マス目 A* では、マス目の分割のパラメータ（特にマス目の大きさ）で探索結果が変化しうるが、 S* はそのようなパラメータの影響がない。）
- 常にユークリッド距離での最短パスが求まる。（マス目 A* では、通過するマス目の数が最小になるようなパスが求まるが、必ずしもユークリッド距離で最短とはならない…ですよね？）
- パスが最初から折れ線で求まるので、折れ線化するための後工程が不要。（マス目 A* では、折れ線化が必要。）
S* の欠点
- 見晴らしの良い広大なマップでは、頂点間リストを素朴に作ると、遠くの多角形同士の頂点間で無駄に多い線分が頂点間リストに登録されるので、工夫が必要。
- 移動する障害物が多数あるような場合には不向きかも。
- ていうか、実際のゲームなどのアプリケーションで試したことがないので、本当に実用に耐えうるのか疑問。誰かやってみてください！
S* アルゴリズムの利用について
S* アルゴリズムに関しては、私は、何らの主張もしません。しかし、他者が特許を取っている（またはこれから取る）可能性などについては関知しませんので、その点は自己責任でお願いします。
デモアプレットについては、著作権を主張します。 All rights reserved です。ていうか、突貫で作ったウンコードなので恥ずかしいから解析するな、ってことです。
『第5回デスマコロシアム』に参加しました
はじめに
『第5回デスマコロシアム』に参加しました。
「第5回デスマコロシアム」問題のトーナメント結果発表です！──優勝者は…！ #デスマコロシアム｜CodeIQ MAGAZINE
要は FizzBuzz ですが、15の倍数のときは大文字の FIZZBUZZ にするというのが特徴です。
問題を読んで、とりあえず書いた Perl (51文字) のコードに「とりあえず」とだけコメントを付けて、とりあえず提出しました。後で日々の集計を見て、短く書けそうな言語で再提出するつもりでした。「とりあえず」のコードは、暫定の全言語最短になりました。
第5回デスマコロシアム(http://t.co/5Bwq4clHQs)。全言語中最小文字数はPerl（51）が1名になりました。 #デスマコロシアム #CodeIQ
— tbpgr | peco | cat (@tbpgr) 2014, 7月 23
毎度Perlerの本気にはチビらされるなぁ RT @tbpgr 第5回デスマコロシアム(http://t.co/Hd0xCknbXW)。全言語中最小文字数はPerl（51）が1名になりました。 #デスマコロシアム #CodeIQ
— カニ戯（ry (@bananawani_mc) 2014, 7月 23
— ニクモ (@nikumo) 2014, 7月 23
ところが、それから何日経っても記録が更新されず、帯状疱疹を患って入院したり退院したりしているうちに締め切りを迎えました。結局、「とりあえず」のコードのまま最短賞をいただきました。チャンピオンバッジは、これで4回連続4個目です。（「決勝進出おめでとうございます！」と書いてあるのですが、決勝どころか準決勝にすら進んだことがない私が4個も持っていていいのかという妙な背徳感が…）
コード
print$_%5?$_%3?$_:fizz:$_%3?buzz:FIZZBUZZ for 1..50Perl (51文字) です。5の倍数かどうかで場合分けし、それぞれの場合を3の倍数かどうかで場合分けするという、なんの工夫もないコードですが、これで実際に最短賞が取れてしまったので仕方ありません。
ちなみに、15の倍数のときが小文字の fizzbuzz ならば工夫の余地があって、 Perl で 45 文字で書けますので、挑戦してみてください（ググる前に！）
『3番目のダンジョン』私の解答
テンプレ
この問題（に限らずダンジョンシリーズ）の面白いところは、定められた文字数制限と使用禁止文字列を満たす JavaScript のコードを提出すれば正解となってバッジが付与されるのですが、実際には場外（Twitter とか CodeIQ MAGAZINE とか）で出題者様主導で解答コードの短さが競われているのです！ いわゆるコードゴルフです。このことは問題文には一切書かれていなくて、バッジほしさに適当に解答を送ると、知らずにコードゴルフに引きずり込まれるという、恐ろしい罠が仕掛けられているのです！
はじめに
今回の問題は、相異なる5個の数値 a, b, c, d, e が与えられたときに、3番目の大きさのものを求める、というものでした。具体的な問題は、解説記事をご覧ください。
解説記事（CodeIQ MAGAZINE）
https://codeiq.jp/magazine/2014/08/14753/
今回もいつものように、途中経過を見ながら縮めていこうと思って、とりあえず様子見でコードを提出したのですが、いつもと違って途中経過の発表がほとんどありませんでした。いぶかしく思っているうちに、帯状疱疹を患って入院してしまい、入院中に締め切りとなってしまいました。しかし、蓋を開けてみると、とりあえず提出したコードがそのまま最短コードになっていました。途中経過の発表がほとんど無かったのは、そもそも動きがほとんど無かったからのようですね。
LV2の私のコード
(a<b)-(a>c)^(a>d)-(a<e)?arguments.callee(b,c,d,e,a):a53文字です。コードゴルフでは忌み嫌われる優先順位の括弧が、なんと4組も使われています。しかし + と / が使用禁止なので、まあ仕方ないところです。
(a<b)-(a>c)^(a>d)-(a<e) の部分がやや解りにくいですが、 ^ の両辺を表にすると次のようになります。
| 条件 | (a<b)-(a>c) の値 |
|---|---|
| a < b,c | 1 |
| b < a < c | 0 |
| c < a < b | |
| b,c < a | -1 |
| 条件 | (a>d)-(a<e) の値 |
|---|---|
| d,e < a | 1 |
| d < a < e | 0 |
| e < a < d | |
| a < d,e | -1 |
この表から、 a の大きさが3番目のときに限り (a<b)-(a>c)^(a>d)-(a<e) が 0 になることがわかります。
LV2の私の面白コード
上記のような経緯のため提出はしませんでしたが、私の考えた面白いコードです。
f=Math.min,-f(-f(a,b,c),-f(a,b,d),-f(a,b,e),-f(a,c,d),-f(a,c,e),-f(a,d,e),-f(b,c,d),-f(b,c,e),-f(b,d,e),-f(c,d,e))114文字です。 -f() だけで答えを求めています。
『ダブル数列のダンジョン』私の解答
テンプレ
この問題（に限らずダンジョンシリーズ）の面白いところは、定められた文字数制限と使用禁止文字列を満たす JavaScript のコードを提出すれば正解となってバッジが付与されるのですが、実際には場外（Twitter とか CodeIQ MAGAZINE とか）で出題者様主導で解答コードの短さが競われているのです！ いわゆるコードゴルフです。このことは問題文には一切書かれていなくて、バッジほしさに適当に解答を送ると、知らずにコードゴルフに引きずり込まれるという、恐ろしい罠が仕掛けられているのです！
はじめに
今回の問題は、等差数列又は等比数列の最初の2項 a, b が与えられたときに、3項目を求める、というものでした。初項の値の範囲（10～99）と、公差・公比の値の範囲（2～9）とが定められているため、等差数列なのか等比数列なのかは一意に定まるようになっています。具体的な問題は、解説記事をご覧ください。
解説記事（CodeIQ MAGAZINE）
https://codeiq.jp/magazine/2014/06/11998/
今回も、各レベルでの最短コードに到達することができました。途中経過がほぼ2日ごとに発表されたのですが、LV3は、追い抜いたと思って次の発表を見たら先を行かれ、今度こそ追いついたと思ったらさらに突き放され、という状況で、大変精神的につらか楽しめました。幸運にも、最終的にはなんとか追いつくことができました。
私のLV3の最終コード
(b*(b/a<<13)^b%a)%819122文字です。LV3では、LV2の禁止文字列に加えて + - が禁止されているため、等差数列の場合の b*2-a の値をどうやって表現するかが最大の焦点になります。上記のコードでは、13ビットずらしてORをとり、さらに8191での剰余をとることによって、加算を表現しています。
私のLV3の途中経過
提出しなかったものも含めて、約60のコードを作りました。以下に全て公開します。
(b/a>=2)*(b*b/a)^!(b/a>=2)*(Math.log(Math.exp(b)*Math.exp(b)/Math.exp(a)*1.6))
m=Math,(b/a>=2)*(b*b/a)^(b/a<2)*(m.log(m.exp(b)*m.exp(b)/m.exp(a)*1.6))
m=Math,e=m.exp,(b/a>=2)*(b*b/a)^(b/a<2)*(m.log(e(b)*e(b)/e(a)*1.6))
e=Math.exp,(b/a>=2)*(b*b/a)^(b/a<2)*(Math.log(e(b)*e(b)/e(a)*1.6))
e=Math.exp,[Math.log(e(b)*e(b)/e(a)*1.6)^0,b*b/a][1>>b%a]
e=Math.exp,[Math.log(e(b)*e(b)/e(a)/.8)^0,b*b/a][1>>b%a]
(e=Math.exp)^[Math.log(e(b)*e(b)/e(a)/.8),b*b/a][1>>b%a]
e=Math.exp,[~Math.log(e(a)/e(b)/e(b)*.3),b*b/a][1>>b%a]
e=Math.exp,[~Math.log(e(a)/e(b)/e(b)/3),b*b/a][1>>b%a]
e=Math.exp,[~Math.log(e(a)/e(b*2)/3),b*b/a][1>>b%a]
m=Math,[~m.log(m.exp(a)/m.exp(b*2)/3),b*b/a][1>>b%a]
~~(b/a)*b*Math.log(Math.exp(b%a/b)*2.7183)^0
~~(b/a)*b*Math.log(Math.exp(b%a/b)/.36787)^0
(b/a^0)*b*Math.log(Math.exp(b%a/b)*2.7183)^0
!!(b%a)*((2*b^256)%(a^256))^!(b%a)*(b*b/a)
x=!(b%a),!x*(2*b^256)%(a^256)^x*b*b/a
x=b%a,(2*b^x<<8)%(a^x<<8)^!x*b*b/a
!(x=b%a)*b*b/a^(2*b^x<<8)%(a^x<<8)
!(x=b%a<<8)*b*b/a^(2*b^x)%(a^x)
x=b%a<<8,!x*b*b/a^(2*b^x)%(a^x)
x=b%a<<13,(2*b^x)%(a^=x)^b*b/a
(2*b^(x=b%a<<13))%(a^=x)^b*b/a
b*b/(a^=x=b%a<<13)^(2*b^x)%a
a^=x=b%a<<13,b*b/a^(b*2^x)%a
a^=!!(b%a)*b<<13,b*b/a^b*8194%a
a^=!!(b%a)*b<<8,b*b/a^b*258%a
a^=!!(b%a)*b<<7,b*b/a^b*130%a
a^=b>>!(b%a)*13<<7,b*b/a^b*130%a
a^=b*!!(b%a)<<7,b*b/a^b*130%a
a^=b/!!(b%a)<<7,b*b/a^b*130%a
a^=b*(b<a*2)<<7,b*b/a^b*130%a
a^=b*(2>>b/a)<<7,b*b/a^b*130%a
x=a^b%a<<13,b*b/x^(b*2^x^a)%x
a^=b%a<<13,b*b/a^(b*2^a^a%256)%a
a^=x=b%a<<13,b*b/a^(b*2^x)%a
!(b%a)*b*b/a^!!(b%a)*(a<<8^b*2)%257
!(b%a)*b*b/a^!!(b%a)*(b%a<<8^b)%255
!(b%a)*b*b/a^!!(b%a)*(b%a^b<<7)%127
!(b%a)*b*b/a^(b<<7^(b%=a))%127*!!b
!(b%a)*b*b/a^!!(b%a)*(a<<7^b)*2%257
(b%a^b<<11)%2047*~~(b/a)
(b%a^b<<10)%1023*~~(b/a)
(b^b%a<<10)%1023*~~(b/a)
(b*~~(b/a)^b%a<<13)%8191
(b*~~(b/a)<<13^b%a)%8191
(b*~~(b/a)^b%a<<26)%8191
(b%a^b*992)%991*~~(b/a)
(b%a^b*896)%895*~~(b/a)
(b%a^b<<13)%~(8191^b/a)
(b%a^b<<13)%(~8191^b/a)
(b%a^b*1e4)%(~9999^b/a)
(b%a^b*8032)%(~8031^b/a)
(b%a^b/a<<14)%(~16383^b)
(b%a^b/a<<14)%(16383^~b)
(b%a^b/a<<14)%~(16383^b)
(b<<13)%(a*~8191^b)%8191
b*8192%(a*~8191^b)%8191
(b*(b/a<<13)^b%a)%8191
(b*(b/a<<45)^b%a)%8191
(b*(b/a<<77)^b%a)%8191『第4回デスマコロシアム』私の nasm (72)
はじめに
『第4回デスマコロシアム』で、途中で提出した nasm (72) のコードです。途中集計の最終回の直前まで、このコードが単独で全言語最小でした。しかし、 Perl に抜かれる可能性があったため、自ら Perl (57) を提出し、この nasm のコードはお蔵入りとなりました。結局、 nasm (72) に naoki_kp さんが並びましたが、 Perl (57) を提出せずとも、この nasm (72) でも最小賞が取れていたようです。
コード
db`BCTYv MU_OW]^j$ば~,z\u340X)蔔P<tqあ`機械語のバイトコードを直接文字コードで表現したものです。 v と M の間は TAB 文字です。
ソース
このコードのソースは、次の通りです。左の列がアセンブラのソース、中央がバイトコード（16進）、右が文字表現です。
inc edx ; 42 ; B
inc ebx ; 43 ; C
push esp ; 54 ; T
pop ecx ; 59 ; Y
L1:
jbe L2 ; 76 09 ; v[TAB]
dec ebp ; 4d ; M
push ebp ; 55 ; U
pop edi ; 5f ; _
dec edi ; 4f ; O
push edi ; 57 ; W
pop ebp ; 5d ; ]
pop esi ; 5e ; ^
push 36 ; 6a 24 ; j$
L2:
jnecx L2-126 ; e3 81 ; ば
mov al,7eh ; b0 7e ; ~
sub al,7ah ; 2c 7a ; ,z
int 80h ; cd 80 ; \u340
pop eax ; 58 ; X
sub eax,ebp ; 29 e8 ; )蔔
xchg eax,esp ; 94 ;
xchg eax,esp ; 94 ;
push eax ; 50 ; P
cmp al,116 ; 3c 74 ; <t
jno L1 ; 71 e3 ; qあ
db 81h,82h ; 81 82 ;解説
Perl (57) のコードと違って、この nasm (72) のコードは、さほどトリッキーなことはしていません。気を付けた点としては、
といった程度です。しかし、文法上どうしても ` を2回使ってしまうため、文字数に対する乗率が2になってしまうことが避けられません。 Perl (57) よりこちらのほうが文字数は少ないのですが、大きさでは上回ってしまいます。
tailsさんのnasm(72) 終了条件がわからなくてしばらく悩んでたけど、Oフラグで終了判定ができるのに気づいて芸術を感じた。1判定3分岐ヤバイ。 #デスマコロシアム
— 冷凍あざらし＠C++ﾁｮｯﾄﾃﾞｷﾅｲ (@naoki_kp) 2014, 7月 5
参考にしたもの
１．インテル：日本語技術資料のダウンロード：IA-32 アーキテクチャー
http://www.intel.co.jp/content/www/jp/ja/developer/download.html#ia32
特に「中巻 A」「中巻 B」は必須でした。
２．命令コード表
http://dl.dropboxusercontent.com/u/2476414/TechResources/x86_opcodemap_1_a4.pdf
『ハンド (逆) アセンブルのための x86 ニーモニックの覚え方』
http://d.hatena.ne.jp/a4lg/20120225/1330180431
に掲載されているものを使わせていただきました。ありがとうございます。これをプリントして、6日間ひたすら眺めていたら、妻に怪訝な顔をされましたw
『第4回デスマコロシアム』私の Perl (57)
はじめに
『第4回デスマコロシアム』に参加しました。今回のルールは、
$&(*,.02468:<>@BDFHJLNPRTVXZ\^`bdfhjlnprt$(,048<@DHLPTX\`dhlpt$*06<BHNTZ`flr$,4<DLT\dlt$.8BLV`jt$0<HT`l$2@N\j$4DTdt
という文字列を出力するプログラムを書く- 評価基準は【文字数×(重複文字数+1)】が小さいほど良い
- 言語ペナルティやトーナメントはいつもと同じ
といったところです。要するに、短くて、しかもなるべく同じ文字を使わないものが高評価ということです。
出題者様による結果記事
https://codeiq.jp/magazine/2014/07/12364/
私は、最終的に Perl (57) でエントリして、最小賞をいただきました。前々回と前回に続いて、3度目の最小賞受賞です。おめでとうございます。ありがとうございます。
結果の公開後、私のコードに対して、ツイッター上で「すごい」「頭おかしい」「変態」など、見ず知らずの多くの方々からお褒めの言葉をいただきました。ゴルファー冥利に尽きます。
コードとその解説
私が提出した Perl (57) のコードは、次の通りです。
eval
q<悃int ch掃雛_四郎囎2抛36f恃雎刈40/把郛;>=~y{遂胄刊掛}[$o-s*.+]drx8文字数 57、重複文字 0で、大きさは 57×(0+1) =57 です。
文字化けしているわけではありません。わけがわからないと思いますが、正直、書いた本人にもさっぱり読めません。ともあれ、１つずつ解釈していくことにします。
まず、
y{遂胄刊掛}[$o-s*.+]drの部分を見てみましょう。 Ideone.com では、日本語文字は UTF-8 として解釈されますから、1文字につき3バイト（例えば「遂」という文字は \xe9, \x81, \x82 の3バイト）です。 Perl の y/// は、どうやらマルチバイト文字は特に認識せずに、単純にバイト単位で置換を行うようで、この置換の対応を表にすると次のようになります。
| 元の文字 | 置換後の文字 | |
|---|---|---|
| 遂 | \xe9 | $ |
| \x81 | o | |
| \x82 | p | |
| 胄 | \xe8 | q |
| \x83 | r | |
| \x84 | s | |
| 刊 | \xe5 | * |
| \x88 | . | |
| \x8a | + | |
| 掛 | \xe6 | （削除） |
| \x8e | ||
| \x9b | ||
この置換を、
悃int ch掃雛_四郎囎2抛36f恃雎刈40/把郛;という文字列に適用しています。（なお、コードでこの文字列を囲んでいる q<......> というのは、展開を伴わない文字列を表す '......' の別記法です。）例えば先頭の「悃」という文字のバイト値は \xe6, \x82, \x83 なので、上の表によって pr という2文字に置換されることがわかります。文字列全体を置換すると、
print chr$_*$r*2+36for$*..40/++$r;という文字列になります。
この文字列、どこかで見たな… という鋭い方もいらっしゃるかと思います。そう、結果記事で解説されている antimon2 さんの文字列とほとんど同じなのです（こういう一致は嬉しいですね(^^)）。違いとしては、私の文字列では、 $k が $r に、 0 が $* になっていますが、置換の圧縮効果のため、私の解法ではこのほうが文字数的に有利なのであって、コードとしての意味は一緒です。
この後のプログラムの動作は antimon2 さんの解説の通りで、 y/// に r オプションを付けることで結果の文字列を取得し、それを x8 で8回繰り返し、それを eval で評価しています（詳しくは結果記事の antimon2 さんの解説を読んでください…）。めでたし、めでたし。
結局、置換対象を日本語文字で表現する解法には、
- 同じバイト値を複数回使っても、組み合わせを変えて別の文字にすることで、重複文字になるのを回避できる。
- 最大でコード3文字を日本語1文字で表現できるので、圧縮が効く
という一石二鳥の利点があります。ちなみに、 NeoCat さんも全く同じアプローチだったようです。
eval q<一:p丁乂n七仄ch仁俄36久了亂*仆_万丈5三上企各下予侈4之仇亅啅但仂;g亊乃今咄亀哄係争!(來呂&8)>=~y{|-龍}[WXYZA\x72it +$/.fo0]rd という重複文字なしPerlコードを書いたは良かったが縮める時間なかった… #デスマコロシアム
— NeoCat (@NeoCat) July 2, 2014
余談：「機種依存文字」
ところで、デスマコロシアムの解答のルールとして、 CodeIQ の入力欄で「機種依存文字」と判定される文字は使用禁止という制限があります。これは問題文には記載されていない（出題者様のブログのQ&Aに記載されている）細則なのですが、今回はこの細則が本質的に重要だったように思います。というのも、「機種依存文字」でない漢字は、 Unicode のコードポイントにおいて飛び飛びに（しかも不規則に）存在しているため、任意の3バイトを組み合わせた文字が解答で使用可能とは限らない（むしろ使用不可能な文字の方が圧倒的に多い）からです。
そこで、私の解法では、手探りでいろいろ試行錯誤して「遂」「胄」「刊」「掛」の4文字を選び、これらを構成するバイト値を組み替えて文字列を表現することにしました。その結果、日本語文字1文字でコード3文字を表現できたのは「刈」→ *.. の1か所だけで、他は全て1文字で1～2文字しか表現できていない、非効率なものになってしまっています。日本語文字の選択や置換の割り当てを最適化するツールを作って文字列を生成すれば、もっと短い解が得られたはずだと思いますが、今回は解答期間の多くを nasm での解の短縮につぎ込み、この Perl の解は途中集計の最終回になんとか間に合わせたため、そこまでする余裕がありませんでした。（解答をファイルでアップロードする形式か、 Ideone.com のURLを解答する形式だったら、「機種依存文字」を気にしなくていいので、もう少し楽ができたなあ…と思います。）
『魔方陣ヌルヌル』別の解法
はじめに
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 にも紹介されていない、別の解法を１つ紹介したいと思います。例として 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 になるように全体に一定の数を加えれば、普通の魔方陣になります。
