マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第10章 関数の再帰的使用によって魔方陣を自動生成する
第９話 普遍版完成？
（
・
1 21 19 20 4
18 2 22 8 15
12 16 13 10 14
11 17 6 24 7
23 9 5 3 25
1 20 23 17 4
19 2 21 8 15
12 16 13 10 14
11 18 5 24 7
22 9 3 6 25
1 20 23 17 4
21 2 15 8 19
14 16 13 10 12
7 18 11 24 5
22 9 3 6 25
1 23 17 20 4
19 2 21 8 15
12 16 13 10 14
11 18 5 24 7
22 6 9 3 25
1 23 17 20 4
21 2 15 8 19
14 16 13 10 12
7 18 11 24 5
22 6 9 3 25
1 17 23 20 4
22 2 15 8 18
14 16 13 10 12
7 19 9 24 6
21 11 5 3 25
1 17 23 20 4
22 2 18 8 15
12 16 13 10 14
9 19 6 24 7
21 11 5 3 25
生成された5次魔方陣総数は100個です。
）
を実現するプログラムコード例
#include<iostream>//インクルードファイルiostreamの読み込み
#include<conio.h>//while(!_kbhit());を使うためのお呪い
#include<string> //文字列変数を使えるようにするために組み込む
#include <iomanip> //setprecisionを使えるように組み込む
#include <cmath>//powなどを使うときに必要
#include <ctime>//time()（←現時刻発生する関数）を使うために必要
using namespace std;//coutを使うときに必要なお呪い
const int n = 5;//具体的な数字を使うのではなく、 n を使うと汎用性のあるプログラムになる！
void f(int s);//順列生成関数←引数名をgからsに変更（2026年３月19日）
void ２次座標生成();
void 番号づけ確認();
int a[n][n]; //将来n次魔方陣まで生成できるようにn * nに変更
int y[n * n];//縦座標
int x[n * n];//横座標
int cn = 0; //aをnに変更 変更理由はnuberの頭文字nは整数を表す場合が多いからです。
int mg;//魔方陣の対角線等の合計
int main() {
２次座標生成();//y横座標とx縦座標生成
//番号づけ確認();//部屋番号と座標の関連づけが成功しているか確認！
mg = n * (n * n + 1) / 2;
clock_t hj, ow;
hj = clock();
f(0);
ow = clock();
cout << endl << "生成された"
<< n << "次魔方陣総数は" << cn
<< "個です。" << endl;//←2026年３月19日訂正
cout << n << "次魔方陣生成時間は"
<< (double)(ow - hj) / CLOCKS_PER_SEC << "秒です。" << endl;
while (!_kbhit());//待機させるための命令
return(0);
}
void f(int s) {
int h;
for (int i = 0; i < n * n; i++) {
if (s == 0)a[y[s]][x[s]] = i
+ 1;
h = 1;
if (s > 0) {
for
(int j = 0; j < s; j++) {
if (a[y[j]][x[j]] == i + 1) {
h = 0;
break;
}
}
if (h
== 1) {
a[y[s]][x[s]] = i + 1;
}
if (h
== 1) {
if (y[s] == n - 1 && x[s] == n - 1) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[j][j];
}
if (g != mg) {
h = 0;
}
}
}
if (h
== 1) {
if (y[s] == n - 1 && x[s] == 0) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[j][n - 1 - j];
}
if (g != mg) {
h = 0;
}
}
}
if (h
== 1) {
if (y[s] == 0 && x[s] == n - 2) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[y[s]][j];
}
if (g != mg) {
h = 0;
}
}
}
if (h
== 1) {
if (y[s] > 0 && y[s] < n - 1 && x[s] == n - 1) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[y[s]][j];
}
if (g != mg) {
h = 0;
}
}
}
if (h
== 1) {
if (y[s] == n - 2 && x[s] == 0) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[j][x[s]];
}
if (g != mg) {
h = 0;
}
}
}
if (h
== 1) {
if (y[s] == n - 1 && x[s] > 0 && x[s] < n - 1) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[j][x[s]];
}
if (g != mg) {
h = 0;
}
}
}
if (h
== 1) {
if (y[s] == n - 1 && x[s] == n - 2) {
int g = 0;//魔方陣の対角線または各行または各列の話
for (int j = 0; j < n; j++) {
g += a[y[s]][j];
}
if (g != mg) {
h = 0;
}
}
}
}
if (h == 1) {
if (s
+ 1 < n * n) {
f(s + 1);
if (n > 4) {
if (cn == 100)return;
}
}
else
{
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[j][k] < 10) {
cout << " " << a[j][k] << " ";
}
else {
cout << a[j][k] << " ";
}
}
cout << endl;
}
cout << endl;
cn++;
if (n > 4) {
if (cn == 100)return;
}
}
}
if (n > 4) {
if (cn
== 100)return;
}
}
if (n > 4) {
if (cn == 100)return;
}
}
void ２次座標生成() {//y横座標とx縦座標生成
int i, j, c;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
a[i][j]
= -1;
}
}
for (i = 0; i < n; i++) {
a[i][i] = i;
}
c = n - 1;
for (i = 0; i < n; i++) {
if (a[i][n - 1 - i] == -1) {
c++;
a[i][n
- 1 - i] = c;
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (a[i][j]
== -1) {
c++;
a[i][j] = c;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
x[a[i][j]]
= j;
y[a[i][j]]
= i;
}
}
}
void 番号づけ確認() {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (a[i][j]
< 10)cout << " " << a[i][j] << " ";
if (a[i][j]
>= 10)cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
普遍版完成？となっているのは、
５次魔方陣や６次魔方陣を生成させると生成が止まってしまう時間帯があるので、
まだ、コードには問題があるのではないかと考えたからです。
一番の可能性は対角線または行または列のすべての欄が埋まっていない段階で、
合計チェックという余計なことをやっているのではないかと考えましたが、
if (y[s] == n - 1 && x[s] == n - 1) {
if (y[s] == n - 1 && x[s] == 0) {
if (y[s] == 0 && x[s] == n - 2) {
if (y[s] > 0 && y[s] < n - 1 && x[s] == n - 1) {
if (y[s] == n - 2 && x[s] == 0) {
if (y[s] == n - 1 && x[s] > 0 && x[s] < n - 1) {
if (y[s] == n - 1 && x[s] == n - 2) {
のいずれにおいても欄はすでに埋まっていました。
なぜなら、
if (h
== 1) {
の条件を満たしているもののみが合計チェックの対象とされており、
すべての条件下において a[y[s]][x[s]] > 0 が満たされており、
合計される対象の部屋番号はいずれもs以下で空欄のある対角線または行または列が合計対象にはされていないからです。
ですから、『第９話 普遍版完成？』は『第９話 普遍版完成』と訂正したいと思います。
では、なぜ止まってしまう時間帯があるのか。
まだ、工夫が足りないからです。
第11章マルチスレッドプログラミングをもって本講義第１篇である基礎編を終了予定でしたが、
第12章を付け加え、根本的な改良を加えたうえで、
第11章のマルチスレッドプログラミングと掛け合わせることによって、
現在私のパソコンで５次魔方陣を100個生成するのに34.647秒要していましたが、
0.05秒以下という時間で100個生成が終わることを体験していただきます。
そして、６次魔方陣でさえおそらく0.1秒以内に100個の生成を終えてしまうでしょう。
つまり、皆さんは350倍以上の生成速度を体験することになります。
マルチスレッドプログラミングの凄さとちょっと改良するだけで段違いに生成速度がアップすることを体験して、
プログラミングとは工夫すればするほどそれに応えてくれる存在なのだと、
皆さんは強く確信して基礎編を終えることになると断言しておきます。
根本的な改良とは私が35年前に行った改良で、
CPUの速度は今のパソコンの1/1000000未満、
メモリも1/1000000未満の35年前のパソコンが10次魔方陣の自動生成に成功しているのです。
工夫すればスパコンでも実現できなかったことを普通のパソコンで実現できてしまうのです。
プログラミングとは創造者の力に大きく影響を受ける存在なのです。
皆さん、第12章を楽しみにしてください。
あなたのプログラム観は大きく変わることになります。
第10章第８話へ 第10章10話へ
本講義トップへ