第10講 関数の再帰的使用による魔方陣の自動生成
第５話 n次魔方陣自動生成ソフト
n次魔方陣生成ソフトコード例
#include<iostream> //入出力のために組み込む
using namespace std; //coutを使うために必要なお呪い
void f(int g);
int x[25];
int n, cn;
int main() {
　　cout << "これはすべてのn次魔方陣を求めるソフトです。" << endl;
　　cout << "何のn次魔方陣を発生させるのかをnに入力してエンターして下さい。" << endl;
　　cout << "n=";
　　scanf("%d", &n);
　　cn = 0;
　　f(0);
　　cout << "生成された" << n << "次魔方陣" << cn << "個です。" << endl;
　　return(0);
}
void f(int g) {
　　int i, j,k, h,hh,w;
　　for (i = 0; i<n*n; i++) {
　　　　if (g == 0)x[g] = i + 1;
　　　　h = 1;
　　　　if (g>0) {
　　　　　　for (j = 0; j<g; j++) {
　　　　　　　　if (x[j] == i + 1) {
　　　　　　　　　　h = 0;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　}
　　　　　　if (h == 1)x[g] = i + 1;
　　　　}
　　　　if (h == 1) {
　　　　　　if (g + 1 < n*n) {
　　　　　　　　f(g + 1);
　　　　　　}
　　　　　　else {
　　　　　　　　hh=1;
　　　　　　　　for (j = 0; j < n; j++) {
　　　　　　　　　　w=0;
　　　　　　　　　　for (k = 0; k < n; k++) {
　　　　　　　　　　　　w+=x[n*j+k];
　　　　　　　　　　}
　　　　　　　　　　if(w!=n*(n*n+1)/2){
　　　　　　　　　　　　hh=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　if(hh==1){
　　　　　　　　　　for (j = 0; j < n; j++) {
　　　　　　　　　　　　w=0;
　　　　　　　　　　　　for (k = 0; k < n; k++) {
　　　　　　　　　　　　　　w+=x[n*k+j];
　　　　　　　　　　　　}
　　　　　　　　　　　　if(w!=n*(n*n+1)/2){
　　　　　　　　　　　　　　hh=0;
　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　if(hh==1){
　　　　　　　　　　w=0;
　　　　　　　　　　for (j = 0; j < n; j++) {
　　　　　　　　　　　　w+=x[n*j+j];
　　　　　　　　　　}
　　　　　　　　　　if(w!=n*(n*n+1)/2){
　　　　　　　　　　　　hh=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　if(hh==1){
　　　　　　　　　　w=0;
　　　　　　　　　　for (j = 0; j < n; j++) {
　　　　　　　　　　　　w+=x[n*j+n-1-j];
　　　　　　　　　　}
　　　　　　　　　　if(w!=n*(n*n+1)/2){
　　　　　　　　　　　　hh=0;
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　if(hh==1){
　　　　　　　　　　for (j = 0; j < n; j++) {
　　　　　　　　　　　　for (k = 0; k < n; k++) {
　　　　　　　　　　　　　　cout << x[n*j + k] << " ";
　　　　　　　　　　　　}
　　　　　　　　　　　　cout << endl;
　　　　　　　　　　}
　　　　　　　　　　cout << endl;
　　　　　　　　　　cn++;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
}


実行結果例
これはすべてのn次魔方陣を求めるソフトです。
何のn次魔方陣を発生させるのかをnに入力してエンターして下さい。
n=3
2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

6 1 8
7 5 3
2 9 4

6 7 2
1 5 9
8 3 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

生成された3次魔方陣は8個です。

　　　　　　　　　　　　w+=x[n*j+n-1-j];
が大変わかりにくいと思いますが、
トレースするとわかります。n = 3 を前提にトレースします。
j = 0 とき、
　　　　　　　　　　　　w+=x[3*0+3-1-0];
　　　　　　　　　　　　w+=x[0+3-1-0];
　　　　　　　　　　　　w+=x[2];
j = 1 とき、
　　　　　　　　　　　　w+=x[3*1+3-1-1];
　　　　　　　　　　　　w+=x[3+3-1-1];
　　　　　　　　　　　　w+=x[4];
j = 2 とき、
　　　　　　　　　　　　w+=x[3*2+3-1-2];
　　　　　　　　　　　　w+=x[6+3-1-2];
　　　　　　　　　　　　w+=x[6];
ですから、

（数字はgを示す。）
見事に逆対角線上を動いています。
　　　　　　　　　　　　w+=x[n*j+j];
についても各自でトレースして下さい。

粘り強く待ち続ければ、４次魔方陣でもすべて生成して、
７０４０個をコンソール画面に表示します。
前に２０分程度で全部が生成出来ると書きましたが、
私の記憶違いのようで、実際には今の段階では全部生成するには、
10時間ぐらいかかりそうです。

これからいろいろと改善していく最終的には、
２６次魔方陣でさえ１秒で数百の単位で生成できるようにもって行きます。
そこでどのぐらいスピードアップしているのかがわかるように計算にかかった時間がわかるように改善します。
コードは次のようになります。
#include<iostream> //入出力のために組み込む
#include<ctime> //時間を計測するために必要
using namespace std; //coutを使うために必要なお呪い
void f(int g);
int x[20];
int n, cn;
int main() {
　　clock_t hj,ow; //時刻取得変数の宣言
　　cout << "これはすべてのn次魔方陣を求めるソフトです。" << endl;
　　cout << "何のn次魔方陣を発生させるのかをnに入力してエンターして下さい。" << endl;
　　cout << "n=";
　　scanf("%d", &n);
　　cn = 0;
　　hj=clock(); //始めの時刻取得
　　f(0);
　　ow=clock(); //終わりの時間取得
　　//計算に要した時間を秒単位に換算して表示
　　cout << "魔方陣生成にかかった時間は" << (double)(ow - hj) / 1000 << "秒です。";
　　cout << "生成された" << n << "次魔方陣" << cn << "個です。" << endl;
　　return(0);
}
以下は同じ

　　cout << "魔方陣生成にかかった時間は" << (double)(ow - hj) / 1000 << "秒です。";
の1000はミリ秒を秒単位に換算するためのものです。
で実行結果は
これはすべてのn次魔方陣を求めるソフトです。
何次の魔方陣を発生させるのかをnに入力し
エンターするとn次魔方陣がすべて生成されます。
n=3
2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

6 1 8
7 5 3
2 9 4

6 7 2
1 5 9
8 3 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

魔方陣生成にかかった時間は0.109000秒です。
生成された3次魔方陣は8個です。
となります。
このできの悪いプログラムでも３次ならおよそ０．１秒ですべて生成できます。

少しずつ改良していって最終的には２６次魔方陣でも、
１秒で数百の単位で生成できるように持って行きますが、
この第10講の改良では、４次魔方陣が

すべてを約10分程度生成するのが関の山です。
５次魔方陣はおそらく１時間待っても１個も出てこないでしょう。
尚、４次以降では上図のように２桁になりますので、表示も２桁対応に変更して下さい。

このコードがわかりにくい最大の理由は、
グローバル配列が
int x[25];
と１元配列になっているということです。
皆さん、これを２次元配列
int mah[5][5];
にしてソフトを作り直して下さい。
x座標とy座標を導入しますので、
いままで魔方陣の各値を入力する配列名をxとしてきましたが、
以降はmahに変更します。

第４話へ　　 第６話へ



初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc** c言語 c** 入門 初心者 基礎から応用まで
eclipse c** 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C**入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC**による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
本サイトトップへ