第20講 一般種法による魔方陣ソフトの高速化
第8話 模範解答例と乱数系列最適実験プログラムについて
label2のテキストは消してありますが、赤囲いの中にlabe2が挿入してあります。
今まで入れてきませんでしたが、TextBoxに範囲外の整数が入力されている場合
『TextBoxには3以上11以下の整数を入力し再度実行ボタンを押して下さい。』と表示させるために今回入れました。
(今までのソフトも同様に是非改良して下さい。)
それに対応するのが下のソースのピンクです。尚、青色の部分は乱数最適実験によってsrand()内の数字を決めました。
乱数最適実験プログラムはこの後示します。
そして、赤こそが驚異の結果をもたらせてくれた各3行です。茶色は、これに伴って変更した箇所です。
また、syokika();は処理内容が多くなったので関数として独立させました。
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
label2->Text=L"";
DateTime^ hj=DateTime::Now;
n=int::Parse(textBox1->Text);
int h=1;
if(n<3 || n>=12){
label2->Text=L"TextBoxには3以上11以下の整数\r\nを入力し再度実行ボタンを\r\n押して下さい。";
h=0;
}
if(h==1){
s=0;
if(n%2==1)g1(n);
if(n%2==0)g2(n);
syokika();
if(n==3 || n==4)srand(0);
if(n==5)srand(3);
if(n==6)srand(17);
if(n==7)srand(95);
if(n==8)srand(1845);
if(n==9)srand(4860);
if(n==10)srand(9877);
f1(0);
array<String^>^ w=gcnew array<String^>(16);
int i;
w[10]=n.ToString();w[11]=L"次";w[12]=L"魔";w[13]=L"方";w[14]=L"陣";w[15]=L"の場合";
for(i=0;i<9;i++)w[i]=L"";
dataGridView1->Rows->Add(w);
DateTime^ ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
w[10]=L"時";w[11]=L"間";w[12]=L"計";w[13]=L"則";w[14]=L":";w[15]=(sa.TotalSeconds).ToString();
for(i=0;i<10;i++)w[i]=L"";
dataGridView1->Rows->Add(w);
}
}
void syokika(){
int i,j;
for(i=0;i<n;i++){
cn1[i]=0;cn2[i]=0;
for(j=0;j<n;j++){
p[i][j]=0;
}
}
}
・
・
・
void f1(int g){
kkk=(kk+i)%n;
a1[y[g]][x[g]]=kkk;
h=1;
for(i=0;i<n;i++){
・
・
・
cn1[kkk]++;
if(cn1[kkk]>n)h=0;
if(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(g<n*n-1){
f1(g+1);
}
else{
f2(0);
if(s==1)return;
}
}
cn1[kkk]--;
}
}
void f2(int g){
・
・
・
for(i=0;i<n;i++){
・
・
・
h=1;
cn2[kkk]++;
if(cn2[kkk]>n)h=0;
hh=0;
if(h==1){
if(p[yy][xx]==0){
p[yy][xx]=1;
hh=1;
}
else{
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;
}
}
if(hh==1)p[yy][xx]=0;
cn2[kkk]--;
}
}
ダウンロード用ファイルForm3.h(自分の該当フォルダに貼り付けるときは、名前をForm1.hに変更してから貼り付けてください。)
乱数最適実験ですが、そのソースは上のForm3.hファイルを次のように変更して作りました。
DateTime^ hj;
DateTime^ ow;
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
n=int::Parse(textBox1->Text);
s=0;
if(n%2==1)g1(n);
if(n%2==0)g2(n);
for(sk=0;sk<20000;sk++){
hj=DateTime::Now;
syokika();
int i;
srand(sk);
f1(0);
array<String^>^ w=gcnew array<String^>(16);
ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
if(s>0){
w[6]=n.ToString();w[7]="次";w[8]=sk.ToString();w[9]=L"";w[10]=L"時";w[11]=L"間";w[12]=L"計";w[13]=L"則";w[14]=L":";
w[15]=(sa.TotalSeconds).ToString();
for(i=0;i<6;i++)w[i]=L"";
dataGridView1->Rows->Add(w);
break;
}
s=0;
}
}
void f1(int g){
if(s==1)return;
ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
if(sa.TotalSeconds>0.05)return;
・
・
・
for(i=0;i<n;i++){
・
・
・
cn1[kkk]++;
if(cn1[kkk]>n)h=0;
if(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(g<n*n-1){
f1(g+1);
ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
if(sa.TotalSeconds>0.05)return;
・
・
・
}
cn1[kkk]--;
}
}
void f2(int g){
if(s==1)return;
ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
if(sa.TotalSeconds>0.05)return;
・
・
・
for(i=0;i<n;i++){
・
・
・
cn2[kkk]++;
if(cn2[kkk]>n)h=0;
hh=0;
if(h==1){
if(p[yy][xx]==0){
p[yy][xx]=1;
hh=1;
}
else{
h=0;
}
・
・
・
if(h==1){
if(g<n*n-1){
f2(g+1);
ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
if(sa.TotalSeconds>0.05)return;
}
else{
s++;
if(s==1)return;
}
}
if(hh==1)p[yy][xx]=0;
cn2[kkk]--;
}
}
ダウンロード用ファイルForm4.h(自分の該当フォルダに貼り付けるときは、名前をForm1.hに変更してから貼り付けてください。)
実行結果
Iに書いてある値がシード値(srand()内の数字)です。
このような実験を繰り返し、最適乱数系列を探し出したのです。
10次までで実験を止めてしまいましたが、
if(sa.TotalSeconds>0.05)return;の0.05の部分を0.1などに変更し、11次12次などでも実験すると
0.1秒以内で12次魔方陣を作り出してしまうシード値を見つけることができかもしれません。
皆さん、是非実験して下さい。
尚、前話の3次から9次までのデータは、if(sa.TotalSeconds>0.02)return;で実験したときのものです。
粘り強く実験を続ければ、10次以下についてはすべて0.001秒以下で作成できるようになるかもしれません。
第20講第7話へ 第20講第9話へ
VC++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual
Basic入門基礎講座