魔方陣 -- ランダム化された方法

はじめに

N次の 魔方陣 とは，N × N のますめのなかに 1 から N までの整数を 1 個ずついれて，縦，横，対角線上のそれぞれ N 個の整数の和がすべてひとしくしたもののことです．ここでは，CCM をつかって 魔方陣をもとめます．

CCM をつかって魔方陣をもとめる方法

下記のアプレットは，初期状態のままでは動作がある程度目でおえるかたちで ひとつの魔方陣をもとめます．(このアプレットが おおきすぎるときはこのちいさいアプレット をつかえばよい.) 初期状態では ``Medium speed (20 rps)'' となっているオプションを ``Full speed'' に変更すれば最高速で 計算できます．(20 rps とは 1 秒間に 20 回 規則を適用する (rps = reductions per second) という意味．ただし， このアプレットにおいては 20 回よりすくなくなる.) ``Restart'' ボタンをおすことによって再度スタートさせることが できます．乱数をつかっているので，そのたびごとにことなる解がもとめられ ますし，計算時間もばらつきます．

[Java アプレットがみえない (実行できない) とき…]

``Swapping rule'' とかかれたオプションを変更すると，使用する プロダクション規則を変更することができます．その方法については 計算方法のページにおいて 説明していますが，かんたんにいうと， ``Swapping rule'' は 2 個のますの整数を交換する規則，``Rotation rule'' は 3 個のますの整数をローテーションする規則です．

魔方陣をもとめる問題は ``局所最適解'' が多数存在する (やさしくない) ので，うまく解をもとめるには，シミュレーテッド・アニーリング (SA) に類似した方法をつかう必要がでてきます．うえのアプレットでは，SA に類似しているが局所的な情報だけをつかうフラストレーション蓄積法 (FAM) (文献 [1] または [2]) という方法をつかっています． ``Initial frustration'' および ``Frustration factor'' の値をかきかえる ことで，フラストレーション蓄積法のはたらきを制御することができます． ``Initial frustration'' の値を 0 にするか，``Frustration factor'' の値を 0 にすることで，フラストレーション蓄積法がはたらかない ようにすることができます．こうすると，解がもとまらないうちに計算が とまったり，いつまでも計算がとまらなくなったりする確率がたかくなります． 計算が停止したときに解がもとめられていれば ``MOD = 0'' と表示されますが，この値が 1 よりちいさいときは 解がもとまらないまま停止したことを意味します．

計算の方法

CCM にもとづいて魔方陣をもとめる方法に興味があれば， 計算方法のページを参照してください． (ここでも説明のためにアプレットを使用しています. ) CCM にもとづく魔方陣のもとめかたについてさらに知りたければ， 文献 [3] をみるとよいでしょう．

魔方陣をもとめるための従来の方法については 「魔方陣のページ」などから たどることができるでしょう．しかし，従来の方法にもとづくアプレットは みつけることができませんでした (96 年 8 月現在)．

参考文献など

注意事項などについては例題ホーム ページの「参考文献など」を参照してください．

• [1] 情報処理学会人工知能研究会報告 94-AI95-4
• [2] 電子情報通信学会人工知能研究会報告 95-AI95-16
• [3] 情報処理学会記号処理研究会報告 94-SYM-75-5

なお，上記のアプレットの原始プログラムは ここにあります．ただし，このアプレットはローディングの時間を短縮するために オブジェクト指向プログラミングとしては最低のものになっています． つまり，すべてがひとつのクラスのなかにつめこまれています．