第20講 一般種法による魔方陣ソフトの高速化
第7話 模範解答例の前のエピソード
簡単にうまくいくはずでした。
ところが、昨日は1日かけても5次までしかできるようになりませんでした。
それで、第7話のアップを諦めて本日になってしまいました。
ですが、今日になり大きな進展=それは予想を超える驚愕天地の進展でした。
前に10次なら10分程度かかってしまうと書きましたが、
実際には10次は0.0624秒で作成できました。
昨日と今日と2日かけた戦果をご覧ください。時間の単位は秒です。
時間データはすべて私の使用パソコンによります。
使用感環境は、Intel(R)Core(TM)Quad CPU Q6600 @2.40GHz 2.40GHz
つまり、3次魔方陣から10次魔方陣まですべて1個作成するのにかかった時間は0.07秒以下です。
前の特殊種による魔方陣作成ソフトでは、9次は10時間かけても1個もできなかったのに対して、
0.001秒以下(データは0秒となっていますが0.001秒以下は計測できないと言うことでしょう。)という驚異的な時間です。
昨日1日かけてもうまくいかなかったソースを最初にご覧頂きます。
といっても、プログラミングには間違いがありません。
ですが、6次でさえ8時間コンピュータを走らせましたが、
1個もできませんでした。
かつてVBで作ったプログラミングと基本的に同じはずなのに、なぜうまくいかないのか、
1日考えてしまいました。
ソースには間違いがないと思われ、最適乱数系列を探す実験を1日中繰り返しましたが、
数秒以内に6次魔方陣などを作り出す最適乱数系列は発見することができませんでした。
(注 srand(0以上の整数);で乱数系列を指定し初期化することができます。
実験の方法については次話で紹介します。)
プログラミングが間違いないというのは、
そのプログラミングにたった6行(=f1に3行、f2に3行)付け加えただけで、
ある乱数系列の基に8時間かけてもできなかった6次魔方陣が0.001秒以下でできるようになったからです。
仮に6行加える前のソフトが8時間(実際はそれ以上でしょう)だとしても、
8×3600÷0.001=10800000(倍)=1080万(倍)を上回るほど作成速度が速くなったのです。
ソースを示しますので、どのような6行(f1に3行+f2に3行)を付け加えたのか考えてみてください。
もちろんヒントがなければ考えようがありませんから、後にヒントを書きます。
void f1(int g){
if(s==1)return;
int i,j,k,h,wa,kk,kkk,m;
kk=rand()%n;
m=n/2;
for(i=0;i<n;i++){
kkk=(kk+i)%n;
a1[y[g]][x[g]]=kkk;
h=1;
if(g==n-1){
wa=0;
for(j=0;j<n;j++){
wa+=a1[j][j];
}
if(wa!=n*(n-1)/2)h=0;
}
if(h==1){
if(y[g]==n-1 && x[g]==0){
wa=0;
for(j=0;j<n;j++){
wa+=a1[n-1-j][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]==0 && x[g]==n-2){
wa=0;
for(j=0;j<n;j++){
wa+=a1[y[g]][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-2 && x[g]==0){
wa=0;
for(j=0;j<n;j++){
wa+=a1[j][x[g]];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
wa=0;
for(j=0;j<n;j++){
wa+=a1[y[g]][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(x[g]>0 && x[g]<n-1 && y[g]==n-1){
wa=0;
for(j=0;j<n;j++){
wa+=a1[j][x[g]];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(g<n*n-1){
f1(g+1);
}
else{
f2(0);
if(s==1)return;
}
}
}
}
void f2(int g){
if(s==1)return;
int i,j,k,h,wa,kk,kkk,m,xx,yy,hh;
yy=a1[y[g]][x[g]];
array<String^>^ w=gcnew array<String^>(16);
kk=rand()%n;
m=n/2;
for(i=0;i<n;i++){
kkk=(kk+i)%n;
a2[y[g]][x[g]]=kkk;
xx=a2[y[g]][x[g]];
h=1;
hh=0;
if(p[yy][xx]==0){
p[yy][xx]=1;
hh=1;
}
else{
h=0;
}
if(h==1){
if(g==n-1){
wa=0;
for(j=0;j<n;j++){
wa+=a2[j][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-1 && x[g]==0){
wa=0;
for(j=0;j<n;j++){
wa+=a2[n-1-j][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]==0 && x[g]==n-2){
wa=0;
for(j=0;j<n;j++){
wa+=a2[y[g]][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-2 && x[g]==0){
wa=0;
for(j=0;j<n;j++){
wa+=a2[j][x[g]];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
wa=0;
for(j=0;j<n;j++){
wa+=a2[y[g]][j];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(x[g]>0 && x[g]<n-1 && y[g]==n-1){
wa=0;
for(j=0;j<n;j++){
wa+=a2[j][x[g]];
}
if(wa!=n*(n-1)/2)h=0;
}
}
if(h==1){
if(g<n*n-1){
f2(g+1);
}
else{
for(j=0;j<n;j++){
for(k=0;k<n;k++){
w[k]=(n*a1[j][k]+a2[j][k]+1).ToString();
}
dataGridView1->Rows->Add(w);
}
for(j=0;j<16;j++)w[j]=L"";
dataGridView1->Rows->Add(w);
s++;
if(s==1)return;
}
}
f(hh==1)p[yy][xx]=0;
}
}
ダウンロードファイルForm2.h(該当フォルダに貼り付けるときには、Form1.hと名前を変更してください。)
ヒントは
#pragma once
#include<stdlib.h>
int n;
int a1[20][20],a2[20][20],p[20][20],cn1[20],cn2[20];
int x[400],y[400];
int s;
namespace 一般種法による魔方陣作成ソフト {
グローバル配列cn1[20]、cn2[20]を付け加えたことです。
これは何のカウンタかと言いますと、
一般種の中の各数字0から(n−1)がそれぞれ何個になっているかを数えるものです。
一般種を構成する各数字は、0から(n−1)まで各n個ずつでなければなりません。
そうでなければ、種の中のすべての数字の話が
{0+1+3+・・・+(n−1)}×n=n*n*(n−1)/2
にはなりません。
1行(1列あるいは1対角線)当たりの合計はn*(n−1)/2でしたから、
すべての種の中の数字の話は
n*(n−1)/2×n=n*n*(n−1)/2
ですね。
一般的に話をすると、難しいと考えるときは何時でも具体的なものに置き換えてください。
(普遍と具体を常に行き来しなければならない、というのが私の右脳数学教育の基本となる考えです。)
例えば、6次魔方陣の場合
1行当たりは
0+1+2+3+4+5=15(=6*(6−1)/2)です。
6行あるので6次魔方陣種のすべての数字の話は、15×6=90(=6*6*(6−1)/2)
4 | 2 | 0 | 1 | 5 | 3 |
0 | 5 | 4 | 2 | 1 | 3 |
2 | 1 | 0 | 5 | 3 | 4 |
3 | 0 | 3 | 4 | 5 | 0 |
5 | 2 | 4 | 1 | 0 | 3 |
1 | 5 | 4 | 2 | 1 | 2 |
各行の合計は
4+2+0+1+5+3=15
0+5+4+2+1+3=15
2+1+0+5+3+4=15
3+0+3+4+5+0=15
5+2+4+1+0+3=15
1+5+4+2+1+2=15(=6*(6−1)/2)
すべての数の合計は
(4+2+0+1+5+3)+
(0+5+4+2+1+3)+
(2+1+0+5+3+4)+
(3+0+3+4+5+0)+
(5+2+4+1+0+3)+
(1+5+4+2+1+2) =90(=15×6=6*6*(6−1)/2)
ですから6次魔方陣種には、0から5までの数字が各6個ずつなければなりません。
各数字を数える役割がグローバル配列cn1[20]、cn2[20]に与えられているのです。
尚、このソフト(Form2.h)は5次まで一応できますが、5次は30秒程度かかってしまいます。
この2日間苦戦させられて、
プログラミングとは本当に恐ろしいものだと思いました。
VB時代(今から10年以上前)にプログラミングしたものを、
記憶を辿りながら、今回プログラミングしました。
結構記憶が頭にちゃんと残っていましたので、
スムーズにできるはずでした。
ところが、5次まではかろうじてできましたし、
4次の場合すべてで5248個できる(if(s==1)return;を外して計算)のも記憶の通りでしたが、
6次以降が何をしても1個もできないのですから。
そこで、自分のサイトを開き、魔方陣の研究→新魔方陣HPとクリックして、
一般次魔方陣一般種法を開きました。
さっと、見るとどう考えても今回作ったものと基本的に同じです。
なのに何故、できないのか。
一晩たってから、一般次魔方陣一般種法のプログラミングをもう一度見ると、
私がそのプログラミングをしたときにも大して重要視していなかった1項目(例の3行)
が私の目にとまりました。
ひょっとして原因はこれかなと、
余り期待もせず改良してみると、冒頭に書いたような予想だにしない大戦果を得ることができたのです。
VBでプログラミングしたときも軽視していたので、
私の記憶から欠落していましたし、
原因の調査でも見落としていたのです。
f1とf2にたった3行ずつ加えるだけで6次魔方陣において1080万(倍)以上の速度差が出るとは、
予想だにしていませんでした。
7次以上では、おそらく100億倍以上の速度差でしょう。
たった、3行で!
恐るべき3行と言えます。
私は、今たまたまデボノの水平思考という本を読んでいますが、
その中でデボノは創造に果たす偶然の役割の大きさに言及しています。
ちょっとした、試行錯誤で全く予想外の結果が得られて、
デボノの主張はまさに正当だと考えさせられています。
試行錯誤、プログラミングにおいて非常に大切なものです。
皆さんもいろいろと試行錯誤して下さい。
皆さんの中には、私のプログラミングよりより成果のがあるプログラミングされた方もいらっしゃるかもしれません。
その場合には、是非メールで教えて頂ければと思います。差し支えなければ、皆様にご紹介させて頂きます。
もう一つの感想は、10年以上このプログラミングに全く触っていないし、
見てもいないのに記憶にちゃんと残っていた(これが今回災いしました)ことに驚きを覚えます。
でも、これがきっとプログラミングの本質なのです。
苦労して作ったものは、10年の歳月が流れても忘れることはないのだと、私は主張したいと思います。
ですから、皆さん是非粘りに粘ってプログラミングに挑戦して下さい。
第20講第6話へ 第20講第8話へ
VC++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual
Basic入門基礎講座