マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第11章 マルチスレッドプログラミング
第９話 シングル版魔方陣自動生成をマルチスレッド化するときの考え方
そこで生成するのに時間がかかる４次魔方陣の自動生成を
題材に戻し比べてみましょう。
普遍版はすでにできているので、
const int n = 5;//具体的な数字を使うのではなく、 n を使うと汎用性のあるプログラムになる！
const int n = 4;//具体的な数字を使うのではなく、 n を使うと汎用性のあるプログラムになる！
と変更すればよいのですが、
コンソールへの表示は終了時刻を計ってからにしないと、
今回と同じで正確な時間比較ができません。
#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 > 3) {
if (cn == 100)return;
}
}
}
if (n > 3) {
if (cn
== 100)return;
}
}
if (n > 3) {
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;
}
では皆さん第10章第９話の普遍版をマルチスレッド化をしてください、
と言いたいところですが実は、
マルチスレッド版数独自動生成ソフト開発に成功して南信州新聞と下野新聞に無料提供している私でも、
マルチスレッド版魔方陣自動生成は大変苦戦しました。
上のシングルスレッドを改良するのでは、
課題が難しすぎます。
そこで、第１１章第５話のコードを少しいじった
#pragma warning(disable: 4996)//第２編のために必要
#include<iostream>//インクルードファイルiostreamの読み込み
#include<conio.h>//while(!_kbhit());を使うためのお呪い
#include<string> //文字列変数を使えるようにするために組み込む
#include <iomanip> //setprecisionを使えるように組み込む
#include <cmath>//powなどを使うときに必要
#include <ctime>//time()（←現時刻発生する関数）を使うために必要
using namespace std;//coutを使うときに必要なお呪い
#include <process.h>//_beginthreadを使うために必要
void 変身の術関数(void* aa);//スレッドを派生させる関数
const int th = 8;
int 継続[th] = {
1,1,1,1,1,1,1,1 };
int main() {
clock_t hj, ow;
hj = clock();
int ii[th];
for (int i = 0; i < th; i += 1) {
ii[i] = i;
_beginthread(変身の術関数, 0, &ii[i]); //新しいスレッドを起動して、そのスレッド上で関数問題生成関数を働かせなさいの命令
}
while (1) {
int 合計 = 0;
for (int i = 0; i < th; i++)合計 += 継続[i];
if (合計 == 0)break;
}
while (!_kbhit());//待機させるための命令
return(0);
}
void 変身の術関数(void* aa)
{//マルチスレッド
int a = *(int*)aa;
//ここを空欄にしました。空欄にしないと下の問１⃣が成立しないからです。
継続[th] = 0;
}
を改良していくことにします。
問題が難しい場合どのように対処すべきでしょうか。
ルネ・デカルトの方法序説を参照するまでもなく、
複雑な問題は分解してそれぞれを単純な課題にすればよいのです。
そして、単純な課題をクリアした後合体すればよいのです。
デカルト流に言えば、分析と総合です。
この分析と総合の方法は『第13章のマルチスレッド版魔方陣自動生成の高速化』
でも扱います。
例えば、６次魔方陣で出て来る34は大きすぎるので、34を６で割った商と６で割った余りに分解するのです。
34÷６ = ５・・・４ 商が５で余りが４です。
1から36までの数字で２本の対角線・６行・６列の合計を同じにするするのは大変ですが、
商と余りそれぞれを２本の対角線・６行・６列の合計が同じになるようにする方が遥かに簡単です。
数字が小さいからです。
最後は商と余りから６×５ + ４ = 34に戻せば普通の魔方陣になります。
では、魔方陣自動生成をどのように分解したらよいでしょうか。
やり方は決して１つではありません。
「数学の答は１つであるから嫌い」「数学の答は１つであるから好き」と人はよく言いますが、
これは間違った見方です。
数学は論証の学問です。
図形の証明問題を除けば、
中学の数学は基本答だけ導ければ、
正解とされますが、
大学受験の数学では、基本答がそうなることを証明しなければなりません。
結論と言う意味の答えは確かに１つの場合もあります（６次魔方陣の結論でも答は京の単位であります）が、
論証の仕方は実は無数にあります。
朝日新聞に掲載された東大の数学の問題を30通りの方法で解いたことがあります。
三角関数を利用する方法・微分積分を応用する方法・図形の性質を考える方法などを考えて、
いくつかの方法を組み合わせることによって約30通りの別解を導いたわけです。
工夫すればいくらでも応えてくれる学問が数学なのです。
そして、プログラミングもコードを工夫すれば同じ問題でも何十通りプログラムが可能です。
プログラミングも工夫した数だけ答えてくれる応えてくれる領域の一つなのです。
ですから、下に示す分解案は唯一の正解ではなく、
案の一つを提示するにすぎません。
他にもいろいろなやり方があるはずなので、
まず、私の分解案に従ってマルチスレッド版魔方陣自動生成させた後、
皆さんも別の分解案を使って段階的に実現してください。
分解案
void 変身の術関数(void* aa)
{//マルチスレッド
int p = *(int*)aa;
・・・・・・・・
継続[th] = 0;
}
について
Ⅰ とりあえずの目標は４次魔方陣のマルチスレッド化なので、
中身のない16スレッドプログラミングを行う・・・ただしスレッドが立ち上がったことを示すために
（
私は派生スレッド：私は派生スレッド：0です。私は派生スレッド：1です。私は派生スレッド：4です。私は派生スレッド：3です。私は派生スレッド：5です。私は派生スレッド：6です。2私は派生スレッド：7です。です。私は派生スレッド：8私は派生スレッド：です。9です。私は派生スレッド：10です。私は派生スレッド：11です。私は派生スレッド：12です。私は派生スレッド：13です。私は派生スレッド：14です。私は派生スレッド：15です。
）
としてください。
16スレッドなのは部屋番号0に入れる生徒の出席番号が1から16まであるからです。
つまり、部屋番号0で16分類してそれに対応するスレッドを派生させるということです。
スレッド数が異なるので私が空欄にした場所以外でも変更になります。
よく考えてください。
さらに、int main()のint以外はまとめて置換をうまく利用して size_t 変更してください。
その際の注意は_beginthreadの int を size_t にうっかり変更するとエラーしますので気を付けてまとめて置換してください。
size_t の整数型ですが62bit処理でマルチスレッドに向いた整数型であるからです。
また、main()の上に
const size_t n = 4;
const size_t th = n * n; と宣言しておきましょう。
Ⅱ 各スレッド毎部屋番号0にのみ生徒の出席番号を入れてください。
その際のⅠの表示は外します。
int main()の上に
size_t a[th][n][n];//魔方陣を形成するための作業用３次元配列
size_t y[th];//縦座標
size_t x[th];//横座標
size_t b[n][n];//y座標・x座標形成のための２次元配列
を定義して、魔方陣自動生成で使った
void ２次座標生成();のプロトタイプ宣言と本体も入れておいてください。
本体
void ２次座標生成() {//y横座標とx縦座標生成
int i, j, c;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
b[i][j]
= -1;
}
}
for (i = 0; i < n; i++) {
b[i][i] = i;
}
c = n - 1;
for (i = 0; i < n; i++) {
if (b[i][n - 1 - i] == -1) {
c++;
b[i][n
- 1 - i] = c;
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (b[i][j]
== -1) {
c++;
b[i][j] = c;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
x[b[i][j]]
= j;
y[b[i][j]]
= i;
}
}
}
も入れておいて、a[p][y[0]][x[0]]に生徒の出席番号を代入してコンソール画面への表示も忘れずに行ってください。
（
出席番号出席番号出席番号出席番号出席番号6 2出席番号 出席番号出席番号出席番号出席番号出席番号14 出席番号出席番号4 出席番号12 5 13 1 15 7 出席番号8 10 11 16 出席番号9 3
）
16のスレッドがコンソール画面に同時に書き込むので表示はぐちゃぐちゃになります。
Ⅲ 関数void f(int p,int s)を冒頭にあるとタイプ宣言をしておいて
本体void f(int p,int s)を作り
void f(int p,int s)に部屋番号1以降に生徒の出席番号を順に入れていってください。
魔方陣の条件を外して順列の条件だけを満たすようにしてください。
最初に部屋番号15に到達したスレッドがコンソール画面に順列を書き込み、
全スレッドを強制的に終了させて、ルートスレッドが「全過程終了」と表示させてください。
強制的に全スレッドを終了させるためには
int main()の上に
グローバル変数
size_t 強制終了 = 0;
を定義しておいて、部屋番号15に到達したスレッドが
強制終了 = 1;
と書き換えてことにして関数fのあちらこちらに
if(強制終了 == 1)break;
を入れておくとよいでしょう。
それでも同時にイクスカのスレッドが部屋番号15についてしまうので、コンソール画面はぐちゃぐちゃになります。
Ⅳ Ⅲで入れた強制終了に関する項目はいったん外してください。
魔方陣の条件を付け加えましょう。
ⅰ 対角線が埋まったら対角線合計を計算して魔方陣の合計に一致しなければ h = 0; とすることによってそれ以降の処理を止めて
関数fの最初のfor文が進むようにしましょう。
ⅱ 行が埋まったら行合計を計算して魔方陣の合計に一致しなければ h = 0; とすることによってそれ以降の処理を止めて
関数fの最初のfor文が進むようにしましょう。
ⅲ 列が埋まったら列合計を計算して魔方陣の合計に一致しなければ h = 0; とすることによってそれ以降の処理を止めて
関数fの最初のfor文が進むようにしましょう。
さらに、魔方陣が各スレッド100個できた段階で戻ることにしましょう。
if (cn[p] == 100) {
a[p][y[s]][x[s]] = 0;
return;
}
を適宜加えればよいのです。
その他
a[p][y[s]][x[s]] = 0;
も適切な箇所に入れてください。
戻るときに
if (h == 1) {
a[p][y[s]][x[s]] = i + 1;
}
で入れた値を0に戻す必要があるからです。
Ⅴ 魔方陣が完成する度に、int m[100][th][n][n]に保存します。
冒頭に用意する配列は
int a[th][n][n];//作業用３次元配列
int m[100][th][n][n];//保存用４次元配列
初心者には２次元配列でさえ重い課題なのに３次元配列、４次元配列が出てきただけで拒絶反応が起きると思いますが、
とりあえずm[魔方陣番号][異世界番号][行][列]であると理解してください。
ただし、普通の世界では1からカウントしますが、プログラミングの世界では0からカウントすることに注意してください。
m[p][q][r][s]なら異世界番号の q + 1 の異世界が p + 1 番目に作り出した魔方陣の r + 1 行 s + 1 列を意味します。
それぞれに1加えてある理由は普通の世界のカウントに直すためです。
0からカウントすることに慣れている人は
m[p][q][r][s]なら異世界番号の q の異世界が p 番目に作り出した魔方陣の r 行 s 列を意味すると思ってください。
ここまでついてきた皆さんはすでに初心者ではありません。
ですから、0からカウントとすることになれてください。
Ⅵ 最後の課題です。
ルートスレッドにおいてint m[100][th][n][n];//保存用４次元配列に保存した内容を
コンソールに表示させてください。
第11章第８話へ 第11章10話へ
本講義トップへ