第20講 魔方陣汎用的生成プログラムVer.3＝末項確定法
第４話 Ver.3（末項確定法）コード解説その１
Ver.3（末項確定法）コード主要部分再掲
public static void f(int g){
if(cn>9)return;
if(y[g]==n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==n-1 && x[g]==0){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][n-1-i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==0 && x[g]==n-2){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[y[g]][i];
w+=m[y[g]][n-1];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==n-2 && x[g]==0){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[i][x[g]];
w+=m[n-1][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[y[g]][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
return;
}
if(y[g]==n-1 && x[g]>0 && x[g]<n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
if(g+1<n*n){
f(g+1);
if(cn>9)return;
}
else{
cn++;
int j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(m[i][j]<10){
System.out.print(" "+m[i][j]+" ");
}
else{
System.out.print(m[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
if(cn>9)return;
}
return;
}
int i,j,h,ii,iii;
ii=0;
if(n!=3 && n!=4){
if(n==6)s=2031;
if(n==5)s=361;
Random r = new Random(s);
ii=(int)(r.nextInt(n*n));
}
if(n==6)t=1;
if(n==5)t=23;
for(i=1;i<n*n+1;i++){
h=1;
iii=(t*i+ii)%(n*n)+1;
m[y[g]][x[g]]=iii;
for(j=0;j<g;j++){
if(m[y[g]][x[g]]==m[y[j]][x[j]]){
h=0;
}
}
if(h==1)f(g+1);
}
}
}
解説
if(y[g]==n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==n-1 && x[g]==0){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][n-1-i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==0 && x[g]==n-2){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[y[g]][i];
w+=m[y[g]][n-1];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==n-2 && x[g]==0){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[i][x[g]];
w+=m[n-1][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[y[g]][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
return;
}
if(y[g]==n-1 && x[g]>0 && x[g]<n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
if(g+1<n*n){
f(g+1);
if(cn>9)return;
}
else{
cn++;
int j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(m[i][j]<10){
System.out.print(" "+m[i][j]+" ");
}
else{
System.out.print(m[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
if(cn>9)return;
}
return;
}
の部分が末項確定法のキモともいうべき部分です。
| ｙ |
|
|
|
|
|
|
|
|
|
|
|
|
| ↓ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
← |
ｘ |
| 0 |
0 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
10 |
|
|
| 1 |
28 |
1 |
36 |
37 |
38 |
39 |
40 |
41 |
11 |
42 |
|
|
| 2 |
29 |
43 |
2 |
50 |
51 |
52 |
53 |
12 |
54 |
55 |
|
|
| 3 |
30 |
44 |
56 |
3 |
62 |
63 |
13 |
64 |
65 |
66 |
|
|
| 4 |
31 |
45 |
57 |
67 |
4 |
14 |
72 |
73 |
74 |
75 |
|
|
| 5 |
32 |
46 |
58 |
68 |
15 |
5 |
80 |
81 |
82 |
83 |
|
|
| 6 |
33 |
47 |
59 |
16 |
76 |
84 |
6 |
88 |
89 |
90 |
|
|
| 7 |
34 |
48 |
17 |
69 |
77 |
85 |
91 |
7 |
94 |
95 |
|
|
| 8 |
35 |
18 |
60 |
70 |
78 |
86 |
92 |
96 |
8 |
98 |
|
|
| 9 |
19 |
49 |
61 |
71 |
79 |
87 |
93 |
97 |
99 |
9 |
|
|
のセルの色とコードの色が対応しています。
if(y[g]==n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
が対角線上の
に
if(y[g]==n-1 && x[g]==0){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][n-1-i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
が逆対角線上の
に、
if(y[g]==0 && x[g]==n-2){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[y[g]][i];
w+=m[y[g]][n-1];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
が０行目上の
| ｙ |
|
|
|
|
|
|
|
|
|
|
|
|
| ↓ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
← |
ｘ |
| 0 |
0 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
10 |
|
|
| 1 |
28 |
1 |
36 |
37 |
38 |
39 |
40 |
41 |
11 |
42 |
|
|
| 2 |
29 |
43 |
2 |
50 |
51 |
52 |
53 |
12 |
54 |
55 |
|
|
| 3 |
30 |
44 |
56 |
3 |
62 |
63 |
13 |
64 |
65 |
66 |
|
|
| 4 |
31 |
45 |
57 |
67 |
4 |
14 |
72 |
73 |
74 |
75 |
|
|
| 5 |
32 |
46 |
58 |
68 |
15 |
5 |
80 |
81 |
82 |
83 |
|
|
| 6 |
33 |
47 |
59 |
16 |
76 |
84 |
6 |
88 |
89 |
90 |
|
|
| 7 |
34 |
48 |
17 |
69 |
77 |
85 |
91 |
7 |
94 |
95 |
|
|
| 8 |
35 |
18 |
60 |
70 |
78 |
86 |
92 |
96 |
8 |
98 |
|
|
| 9 |
19 |
49 |
61 |
71 |
79 |
87 |
93 |
97 |
99 |
9 |
|
|
に、
if(y[g]==n-2 && x[g]==0){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[i][x[g]];
w+=m[n-1][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
が０列目上の
に
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[y[g]][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
return;
}
がｎ－１行目上の
最後
if(y[g]==n-1 && x[g]>0 && x[g]<n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
if(g+1<n*n){
f(g+1);
if(cn>9)return;
}
else{
cn++;
int j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(m[i][j]<10){
System.out.print(" "+m[i][j]+" ");
}
else{
System.out.print(m[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
if(cn>9)return;
}
return;
}
が
に対応しています。
最後の行の一番最後のセルが
else{
cn++;
int j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(m[i][j]<10){
System.out.print(" "+m[i][j]+" ");
}
else{
System.out.print(m[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
if(cn>9)return;
}
に対応しています。
if(y[g]==n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==n-1 && x[g]==0){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][n-1-i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==0 && x[g]==n-2){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[y[g]][i];
w+=m[y[g]][n-1];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]==n-2 && x[g]==0){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[i][x[g]];
w+=m[n-1][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
return;
}
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[y[g]][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
return;
}
if(y[g]==n-1 && x[g]>0 && x[g]<n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
if(g+1<n*n){
f(g+1);
if(cn>9)return;
}
else{
cn++;
int j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(m[i][j]<10){
System.out.print(" "+m[i][j]+" ");
}
else{
System.out.print(m[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
if(cn>9)return;
}
return;
}
の存在が、Ver.2の次のコードを
if(h==1){
if(y[g]==n-1 && x[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=m[j][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-1 && x[g]==0){
w=0;
for(j=0;j<n;j++){
w+=m[j][n-1-j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y[g]==0 && x[g]==n-2){
w=0;
for(j=0;j<n;j++){
w+=m[y[g]][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(x[g]==0 && y[g]==n-2){
w=0;
for(j=0;j<n;j++){
w+=m[j][x[g]];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=m[y[g]][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(x[g]>0 && x[g]<n-1 && y[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=m[j][x[g]];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
不要なものにしています。和の条件が、キモの部分に入っているので和のチェックは必要ないわけです。
また、
if(h==1){
if(g+1<n*n){
f(g+1);
//if(cn>20)return;
}
else{
cn++;
for(j=0;j<n;j++){
for(k=0;k<n;k++){
if(m[j][k]<10){
System.out.print(" "+m[j][k]+" ");
}
else{
System.out.print(m[j][k]+" ");
}
}
System.out.println();
}
System.out.println();
//if(cn>20)return;
}
}
も
if(h==1)f(g+1);
と簡単になっています。理由は、
if(y[g]==n-1 && x[g]>0 && x[g]<n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
if(g+1<n*n){
f(g+1);
if(cn>9)return;
}
else{
cn++;
int j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(m[i][j]<10){
System.out.print(" "+m[i][j]+" ");
}
else{
System.out.print(m[i][j]+" ");
}
}
System.out.println();
}
System.out.println();
if(cn>9)return;
}
return;
}
に機能が移っているからです。
第３話へ 第５話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第２部
初心者のための
VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
