マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第13章 様々な魔方陣の作成および自動生成
第16話 魔方陣における全体構造解析とは何か
その話をするためにもう一度数独の全体構造解析に触れておきたいと思います。
すべての空欄について候補数字を考えることが全体構造解析でした。
例えば、上図の黄色の空欄を候補数字を考えるには、
黄色以外の同行・同列・同ブロックについて調べて数字が入っているものについては候補から外す必要がありました。
まず、同行によって｛5，8，6，9｝が候補から外されます。
次に、同列よって｛5，8｝が候補から外されます。
最後に同ブロックから｛1，6，3｝が候補から外されます。
その結果残る候補は｛2，4，7｝となり、黄色の候補数字が決定されます。
前話で述べた通りかなり複雑な分析を必要とされるわけです。
行・列・ブロックの３次元(３方向から）の分析が必要だったわけです。
それに対して魔方陣の場合はどうなるでしょうか。
黄色は数字の入っている
比較され、｛5，14，2，6，3，1，17，23，32，31，34，33｝が候補から外され、
黄色に入る数字候補は
｛4，7，8，9，10，11，12，13，15，16，18，19，20，21，22，24，25，26，27，28，29，30，36｝
となります。
青の動きは一見複雑そうです。
ところが、ある観点から考えると極めて単純な仕組みがあります。
それは、検討される軸は時間軸だけなのです。
平たく言うと過去との比較のみです。
時間軸のみの１次元の分析で済むわけです。
えっ、どういうこと？
と思いますよね。
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;
}
}
}
によってy座標とｘ座標が決められていました。
時間と比喩しているのは上の0～35です。
つまり、一見複雑そうに見えた青は
時間の12以下と比較をすればよいのです。
黄色の現時刻は13だからです。
第13話等でやった
void 全体構造解析関数() {
int max = 8;
int 配列[9] = { 1,2,3,4,5,6,7,8,9 };
for (int i = 0; i < n; i++) {
if (a[0][i] > 0) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < max;
k++) {
if (配列[k] == a[0][j]) {
配列[k] = 配列[max];
配列[max] = a[0][j];
max--;
}
}
}
}
}
for (int i = 0; i < n; i++) {
if (a[0][i] == 0) {
mx[0][i] = max;
for (int j = 0; j < n; j++) {
s[0][i][j] = 配列[j];
}
}
}
for (int i = 0; i < n; i++) {
if (a[0][i] == 0)cout <<
"mx[0][" << i << "] = " << mx[0][i]
<< " " << endl;
}
for (int i = 0; i < n; i++) {
if (a[0][i] == 0) {
for (int j = 0; j < mx[0][i] + 1;
j++) {
cout << "s[0]["
<< i << "] = " << s[0][i][j] << " ";
}
}
cout << endl;
}
}
の部分を改良すれば、魔方陣による全体構造解析は完成させることができるのです。
int max = 8;
int 配列[9] = { 1,2,3,4,5,6,7,8,9 };
は
size_t max = th - 1;
int 配列[th] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36
};
と改良すればよいのです。
尚、使用するコードは第11章第15話のコードです。
void 変身の術関数(void* aa) {//マルチスレッド
size_t
p = *(size_t*)aa;
a[p][y[0]][x[0]] = p + 1;
f(p, 1);
継続[p] = 0;
}
void f(int p,
int s) {//魔方陣生成関数
for (size_t i = 0; i < th; i++) {
size_t h = 1;
for (size_t j = 0; j < s; j++) {
if (a[p][y[j]][x[j]]
== i + 1) {
h = 0;
break;
}
}
if (h == 1) {
a[p][y[s]][x[s]] = i + 1;
}
までの部分は大幅な改良が必要となります。
青は現在進行形（下のコード赤参照）で交換とmaxの減少が行われますから過去との比較は不要であり全削除します。
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--;
過去との比較を行わないことが、全体構造解析型が第11章第13話から大幅にスピードアップする理由の一つなのです。
もっと大きな理由はmaxの減少によって時間と共に試行数が時間と共に減少していくことです。
ですから忘れてならない変更は
for (size_t i = 0; i < max; i++) {
です。試行しなければならない場合の数が時間の進行とともに1つずつ減少していくので大幅な生成速度の上昇が図れるのです。
数独に空欄を埋めていくほど解法の速度が上がることと同じです。
a[p][y[s]][x[s]]
= 配列[i];
も忘れてはならない変更となります。
さらに、
u = 配列[max - 1];
配列[max - 1] = 配列[(i + gz) %
max];
配列[(i + gz) % max] = u;
はもう一か所必要になります。
実行画面
100個生成バージョン
第13章第15話へ 第13章17話へ
本講義トップへ