を実現するコード例
マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第13章 様々な魔方陣の作成および自動生成
第17話 全体構造解析による魔方陣生成
を実現するコード例
#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 size_t n = 6;
const size_t th = n * n;
const size_t ts = 100;
void f(int p, int s, size_t max, size_t 配列[th]);//魔方陣生成関数
void ２次座標生成();
size_t 検証();
size_t m[n][n];//魔方陣を収納する４次元配列
size_t a[th][n][n];//魔方陣を形成するための作業用３次元配列
size_t cn = 0;//それぞれのスレッドにおける魔方陣をカウントする１次元配列
size_t y[th];//縦座標
size_t x[th];//横座標
size_t b[n][n];//y座標・x座標形成のための２次元配列
size_t mg = n * (th + 1) / 2;//魔方陣の対角線または行または列の合計
size_t ps;//魔方陣を発見したスレッドの番号を保存する変数
size_t 継続 = 1;
size_t シード値 = (unsigned)time(NULL);
size_t h1[th];//昇順
size_t mx[th];//候補数字数
int main() {
clock_t hj, ow;
２次座標生成();
hj = clock();
for (size_t i = 0; i < th; i++) {
h1[i] = i + 1;
mx[i] = th;
}
cout << "マルチスレッド版" << n << "次魔方陣生成を始めます。" << endl;
size_t ii[th];
for (size_t i = 0; i < th; i++) {
ii[i] = i;
_beginthread(変身の術関数, 0, &ii[i]); //新しいスレッドを起動して、そのスレッド上で関数問題生成関数を働かせなさいの命令
}
int k = 0;
while (継続) {}
ow = clock();
cout << endl;
int h = 1;
for (size_t p = 0; p < ts; p++) {
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < n; j++) {
if (m[i][j] < 10) {
cout << " " << m[i][j] << " ";
}
else {
cout << m[i][j] << " ";
}
}
cout << endl;
}
h = 検証();
if (h == 1)cout << "正常" << endl; else { cout << "異常" << endl; goto tobi; }
cout << endl;
}
cout << endl;
tobi:;
if (h == 1)cout << "すべて正常でした。" << endl; else cout << "異常がありました。" << endl;
cout << n << "次魔方陣1個当たりの平均生成時間は" << (double)(ow - hj) / (ts * CLOCKS_PER_SEC) << "秒です。" << endl;
while (!_kbhit());//待機させるための命令
return(0);
}
void 変身の術関数(void* aa) {//マルチスレッド
size_t p = *(size_t*)aa;//スレッド番号
srand(シード値 - 19 * p);
size_t k[th];
size_t 配列[th];//候補数字ランダム順
for (size_t i = 0; i < th; i++) {
k[i] = 1;
}
for (size_t i = 0; i < th; i++) {
size_t q;
while (1) {
q = rand() % th;
if (k[q] == 1) {
配列[i] = h1[q];
k[q] = 0;
break;
}
}
}
size_t max = th;
f(p, 0, max, 配列);
}
void f(int p, int s, size_t max, size_t 配列[th]) {//魔方陣生成関数
size_t gz = rand() % max;
for (size_t i = 0; i < max; i++) {
size_t h = 1;
if (継続 == 0)return;
a[p][y[s]][x[s]] = 配列[(i + gz) % max];
size_t u;//交換の受け皿
u = 配列[max - 1];
配列[max - 1] = 配列[(i + gz) % max];
配列[(i + gz) % max] = u;
max--;
if (継続 == 0)return;
if (h == 1) {
if (y[s] == n - 1 && x[s] == n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][j][j];
}
if (合計 != mg)h = 0;
}
}
if (継続 == 0)return;
if (h == 1) {
if (y[s] == n - 1 && x[s] == 0) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][j][n - 1 - j];
}
if (合計 != mg)h = 0;
}
}
if (継続 == 0)return;
if (h == 1) {
if (y[s] == 0 && x[s] == n - 2) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][y[s]][j];
}
if (合計 != mg)h = 0;
}
}
if (継続 == 0)return;
if (h == 1) {
if (y[s] > 0 && y[s] < n - 1 && x[s] == n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][y[s]][j];
}
if (合計 != mg)h = 0;
}
}
if (継続 == 0)return;
if (h == 1) {
if (y[s] == n - 2 && x[s] == 0) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][j][x[s]];
}
if (合計 != mg)h = 0;
}
}
if (継続 == 0)return;
if (h == 1) {
if (y[s] == n - 1 && x[s] > 0 && x[s] < n - 1) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][j][x[s]];
}
if (合計 != mg)h = 0;
}
}
if (h == 1) {
if (y[s] == n - 1 && x[s] == n - 2) {
size_t 合計 = 0;
for (size_t j = 0; j < n; j++) {
合計 += a[p][y[s]][j];
}
if (合計 != mg)h = 0;
}
}
if (継続 == 0)return;
if (h == 1) {
if (s + 1 < th) {
f(p, s + 1, max, 配列);
if (継続 == 0)return;
}
else {
for (size_t j = 0; j < n; j++) {
for (size_t k = 0; k < n; k++) {
m[j][k] = a[p][j][k];
}
}
ps = p;
cn++;
if (cn == ts)継続 = 0;
if (継続 == 0) {
a[p][y[s]][x[s]] = 0;
max++;
u = 配列[max - 1];
配列[max - 1] = 配列[(i + gz) % max];
配列[(i + gz) % max] = u;
return;
}
}
}
if (継続 == 0) {
a[p][y[s]][x[s]] = 0;
max++;
u = 配列[max - 1];
配列[max - 1] = 配列[(i + gz) % max];
配列[(i + gz) % max] = u;
return;
}
a[p][y[s]][x[s]] = 0;
max++;
u = 配列[max - 1];
配列[max - 1] = 配列[(i + gz) % max];
配列[(i + gz) % max] = u;
}
}
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;
}
}
}
size_t 検証() {
size_t gk;
for (size_t i = 0; i < n; i++) {
gk = 0;
for (size_t j = 0; j < n; j++) {
gk += m[i][j];
}
if (gk != mg) {
return(0);
}
}
for (size_t i = 0; i < n; i++) {
gk = 0;
for (size_t j = 0; j < n; j++) {
gk += m[j][i];
}
if (gk != mg) {
return(0);
}
}
gk = 0;
for (size_t i = 0; i < n; i++) {
gk += m[i][i];
}
if (gk != mg) {
return(0);
}
gk = 0;
for (size_t i = 0; i < n; i++) {
gk += m[i][n - 1 - i];
}
if (gk != mg) {
return(0);
}
size_t hk[th];
for (size_t i = 0; i < th; i++)hk[i] = 0;
for (size_t i = 0; i < th; i++) {
hk[m[y[i]][x[i]] - 1] = 1;
}
for (size_t i = 0; i < th; i++) {
if (hk[i] == 0)return(0);
}
return(1);
}
むずかしい！ですよね。
答を見ても大丈夫です。
おそらく95％の方が見てしまっています。
本当に難しいんですよ。
私も簡単にできたわけではありません。
難しくてへこたれそうに何度もなりました（笑）
この全構造解析型は間違いなしに幅広い応用範囲を持っています。
少しだけ解説します。
max++;
u = 配列[max - 1];
配列[max - 1] = 配列[(i + gz) % max];
配列[(i + gz) % max] = u;
が必要な理由はお分かりです。
再帰は、潜航したり浮上したりを繰り返しながら試行錯誤を繰り返す方法です。
ですから駄目だったときには再帰＝浮上してやり直すので、
もう一度交換して元の状態の戻さなければならないのです。
u = 配列[max];
配列[max] = 配列[(i + gz) % max];
配列[(i + gz) % max] = u;
max--;
としてもよいですね。
プログラミングに唯一の答えはありません。
答は無数にあるのです。
それは、数学も同じです。
結論（答）を出すことが数学の目的ではありません。
答を論証することが数学が求めていることです。
論証の仕方も大きく分けても６通りぐらいあり、
それらを組み合わせると無数に近い論証方法があるのです。
ですから、「答が一つだから数学が好きだ」「答が一つしかないから数学が嫌いだ」両方とも間違った考えです。
更にいうと、結論と言う意味の答も６次魔方陣の場合は1775京3889兆1976億6063万5632通りもあるのです。
第17話では簡単な解説にとどめましたが、
今回のコードは大変難解ですので、
次話で可能な限りのトレースをして皆さんの理解を深めたいと思います。
第13章第16話へ 第13章18話へ
本講義トップへ