The Office Uchida, School of Computer

コンピュータを学習する人の学校:パソコンキャンパス、プログラミングキャンパス
ホームCプログラマ徹底養成コース初級コース 第14問/中級コース 第7問
文字の拡大

初級コース 第14問/中級コース 第7問:魔方陣

問題:N×Nの升目の中に、1からN2までの数を重複なく配置します。 このとき、升目の縦・横・斜めの合計がすべて同じ値になるように配置したものを魔方陣と呼びます。

たとえば、次の例は、N=5、すなわち5×5の魔方陣です。

これは、次に示すように、1から52までの数が1つだけ配置され、 縦・横・斜めの合計がすべて65になっています。

Nが偶数のときに魔方陣を作成するアルゴリズムは見つかっていませんが、Nが奇数の場合に魔方陣を作成するアルゴリズムは見つかっています。

そこで、N=3, 5, 7, ... , 1001までの魔方陣を求め、それが正しく魔法人になっているかどうか検証するプログラムを作成して下さい。魔方陣を 表示する必要はありません。


学習ポイント
  1. 複雑なループロジックに慣れる
  2. 関数の設計に慣れる
  3. 2次元配列の使い方に慣れる
  4. 込み入ったアルゴリズムのデバッグ方法に慣れる
  5. ローカル変数とグローバル変数の違いと利用法を認識する

本問題に対するFAQ

質問1:Nが奇数のときの魔方陣を求めるアルゴリズムが分かりません。

 それでは、5×5の魔方陣を例にとって考えましょう。まず、第1行目の中央に1を置きます。

次に、2を入れるわけですが、一般に次の数値を入れる場合には『斜め右上の枡』に入れます。 ところが、この場合、そこは枡の外側なので、入れることができません。その場合には、その一番下の行に入れます。

今度は3を入れるわけですが、この場合には、斜め右上の枡は空いていますから、 そこに3を入れます。

次に、3の斜め右上を見ますと、そこは枡の外側になりますので、入れることができません。 このように、枡の右に飛び出した場合には、その行の先頭列に置きます。

4の斜め右上は空いていますから、そこに5を入れます。

次に6を入れるわけですが5の斜め右上はすでに1が入っています。 このように入れようとした場所にすでに数値が入っている場合には、5の下の部分に次の数値である6を入れます。

今度は、7と8を入れますが、これは下に示すように、斜め右上の枡が空いているので、 そのまま配置します。

次に8の斜め右上に9を入れるわけですが、飛び出してしまうので、その行の最下位に配置します。

同様に9の斜め右上も枡の右に飛び出してしまうので、その行の先頭列に10を置きます。

10の斜め右上に11を置こうとするのですが、そこにはすでに6があります。 このように配置できないときは、そのすぐ下に配置します。

今度は、12から15まで斜め右上が開いているので、一気に格納できます。

次に15の斜め右上ですが、この場合、今までの方法で処理してもどちらも桝目の外になってしまい、 16を格納することができません。その場合には、15の下に16を置きます。

さて、16の次に17を置くわけですが、斜め右上の枡は、魔方陣の外側に飛び出してしまいますので、 その行の一番左に17を起きます。次に斜め右上に18を置くわけですが、これもまた、魔方陣の外側に飛び出してしまいますので、 その列の一番下に18を起きます(下図左)。

19、20は、斜め右上に場所が空いていますので、そのまま入れることができます(下図右)。

次に21ですが、斜め右上に16がすでに入っていますので、20の下に21を置きます(下図左)。そして、22は、その斜め右上が空いていますので、 そこに22を入れます(下図右)。

22の斜め右上は魔方陣の外ですから、その行の一番左に23を置きます。そして、その斜め右上に24を置きます。 その斜め右上は魔方陣の外ですから、その列の一番下に25を置きます。

このようにすれば、縦・横・斜めのどの和をとっても65になる魔方陣が完成します。

質問2:質問1で5×5の魔方陣の作り方を教わりましたが、一般的なアルゴリズムに直して 教えてもらえますか。これでは1000×1000の魔方陣は作れません。

 それでは、数値の置き方を一般化して示しましょう。次の(a)から(e)のパターンです。 これ以外のパターンはありません。

ここで、青い丸がすでに置かれた数値で、赤い丸が次に置くべき数値を示しています。 深緑の四角い箱は、すでに数値があるなどしてそこには数値を置けないことを意味しています。