第２１講　末項確定法
第１話 末項確定法とは？

今回はいつもと手法を変えて、
最初に、今回の成果を最初に紹介した後に、
末項確定法とは何か説明しましょう。
以下のデータは各次魔方陣を１００個作るのにかかった時間です。

１個あたり０．０１５９１２秒です。
前話のデータが０．０７２８４秒ですから、約４．６倍のスピード差です。
さらに、10次魔方陣の場合

1個あたり０．３９８８９２秒ですから、約５．６倍です。
今までソフトがバージョンアップする度に、
１万倍とか１１００万倍とかとう桁外れの性能アップを見せていたのに比べるとかなり地味に見えるかもしれませんが、
結構大きな戦果だと思います。
プログラミングの世界では、１．１倍でも大きな成果です。
（例えば、数独問題作成ソフトのスピードを１．１倍にするのに私は数日も場合によっては数週間費やしていました。
皆さんからすれば結果だけ見ているので、その苦労は見えないと思いますが、
プログラミングとは地味な研究の積み重ねなのです。
ただ、前々話で紹介したようにときには驚愕の成果を見せることもあります。）
ですから５，６倍はかなり大きな成果です。
さらに、今回の改良によって１１次魔方陣も１個あたり約０．０５６秒でできています。
前話のときは途中で実験を打ち切ってしまったので、単純比較はできませんが、
２０秒まで探索範囲を広げて、６０分も実験を続けましたが最適乱数系列を発見できませんでしたので、
仮に前話のソフトが２０秒であると前提しても、
２０÷０．０５６＝約３６０倍です。

末講確定法とは、水色以外のセルについては、初めから入る数字は確定していることに、
着眼した方法です。
例えば、

と来たときに、青のセルに入る数字は決まっています。

（表を見るときには、セルに入っている数字がセル番号のｇかそのセルに実際に入っている数字かを常に区別してください。
上表の数字は、セル番号ｇではなく、そのセルに入っている実際の数字です。
本講義においては、セル番号ｇのときは基本的にはピンクとしています。）
６＋４＋９＋４＋１＋０＋８＋３＋４＝３９
対角線の合計は、
０＋１＋２＋３＋４＋５＋６＋７＋８＋９＝４５
ですから、

に入る数字は
４５−３９＝６
と確定してしまうのです。


ですから、このセルについてはfor文で探索するのは無駄です。

に来たら、for文は通らないで次の世界（ｇ＋１）に進むか、
前の世界（ｇ−１）に戻るしかないのです。
戻る場合の言うのは、例えば

なら、６＋４＋９＋４＋１＋０＋８＋０＋２＝３４ですが、
合計の４５との差をとると、４５−３４＝１１

にはいる最大数は９ですから、
このセルのある対角線の合計を４５にするのは不可能になっているわけです。
この場合には1つ前のセル

に戻ってやり直すしかありません。



あるいは

の場合も６＋４＋９＋４＋１＋２＋８＋５＋７＝４６となり、

に入る数字が−１となってしまいこれも禁則に反します。
セルに入る数字は０から９までですから。
この場合にも

に戻ってやり直すしかありません。

さて、末講確定法についてはお分かりでしょうか。
ソースでは、
void f1(int g){
　　if(s==100)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;
　　　　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(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==100)return;
　　　　　　}
　　　　}
　　　　cn1[kkk]--;
　　}
}
緑色以外の色のついている部分を工夫しなければなりません。
これらは、for文の中にあってはいけませんから、for文の前に出すことになります。
するとfor文は、
　　for(i=0;i<n;i++){
　　　　kkk=(kk+i)%n;
　　　　a1[y[g]][x[g]]=kkk;
　　　　h=1;
　　　　cn1[kkk]++;
　　　　if(cn1[kkk]>n)h=0;
　　　　if(h==1)f1(g+1);
　　　　cn1[kkk]--;
　　}
と至ってシンプルなものになります。

第２０講第９話へ 第２１講第２話へ

VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座