を実現するコード例
マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第13章 様々な魔方陣の作成および自動生成
第15話 １ブロック数独の構造解析
を実現するコード例
#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 全体構造解析関数();//スレッドを派生させる関数
const int n = 9;//数独の一辺は９です
int s[n][n][n];//各空欄の候補数字を収納する３次元配列
int a[n][n];//問題及び解答を収納する２次元配列
int mx[n][n];//各空欄の候補数字数
int main() {
//すべてを0に初期化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = 0;
}
}
//データ入力
a[0][0] = 2;
a[2][1] = 6;
for (int i = 0; i < n / 3; i++) {
for (int j = 0; j < n / 3; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
全体構造解析関数();
while (!_kbhit());//待機させるための命令
return(0);
}
void 全体構造解析関数() {
int 配列[9] = { 1,2,3,4,5,6,7,8,9 };
int max = 8; // 有効インデックスの最大値
// 1ブロック内にすでに入っている数字を候補から除外
for (int i = 0; i < n / 3; i++) {
for (int j = 0; j < n / 3; j++) {
if (a[i][j] > 0) {
for (int k = 0; k <= max; k++) {
if (配列[k] == a[i][j]) {
配列[k] = 配列[max];
配列[max] = a[i][j];
max--;
break;
}
}
}
}
}
// 空欄に候補を格納
for (int i = 0; i < n / 3; i++) {
for (int j = 0; j < n / 3; j++) {
if (a[i][j] == 0) {
mx[i][j] = max + 1; // 候補数
for (int k = 0; k < mx[i][j]; k++) {
s[i][j][k] = 配列[k];
}
}
}
}
// デバッグ出力
for (int i = 0; i < n / 3; i++) {
for (int j = 0; j < n / 3; j++) {
if (a[i][j] == 0)
cout << "mx[" << i << "][" << j << "] = " << mx[i][j] << endl;
}
cout << endl;
}
for (int i = 0; i < n / 3; i++) {
for (int j = 0; j < n / 3; j++) {
if (a[i][j] == 0) {
for (int k = 0; k < mx[i][j]; k++) {
cout << "s[" << i << "][" << j << "][" << k << "] = " << s[i][j][k] << " ";
}
cout << endl;
}
}
}
}
行→列→ブロックと進んできましたが、
難易度は右に進むほど難しく、
さらに、列からブロックへの難度の上昇は極めて大きいです。
for文の次元数が１つ上がってしまうからです。
さて、全体構造解析の話題は第12話の
から始まりました。
本来であればここに戻り、全空欄について候補数字探索をやらねばなりませんが、
これは第２編数独自動生成ソフトの開発にゆだねることにします。
１行数独・1列数独・1ブロック数独とは比較にならないほど、
難度が高くなるかです。
超超Z難度と言っても誇張でないほどです。
基礎編第13章の主題は魔方陣数独自動生成でした。
話題を元に戻したいと思いますが、
ついでに１つ脱線することをお許しください。
魔方陣の研究はおもしろいが、
実用性はまったくないと私は考えていましたが、
最近考えが変わりました。
渋滞のない交通網
無駄の少ない物流
効率的な医療や介護
食料やエネルギーの最適配分
金融の最適化
計画経済の最適化
に直接繋がる研究である可能性が高い、と思っています。
魔方陣や数独の研究が社会を根底から変える可能性をもっているのです。
人権尊重・人権保障と搾取のない社会という高い理想を掲げながら、
旧ソ連や東欧社会主義はことごとく潰れました。
人権擁護どころか、
人権抑圧が起きていたのです。
最大の失敗の要因の一つは、
計画経済が上手くいかなくなったことです。
第２次産業が主流だったころは計画経済がうまく回り、
アメリカと同等の発展を遂げていた旧ソ連は、
第３次産業へと軸足を移し始めたころから、
計画経済が回らなくなり、
市場に行くと魚の腐臭が漂っていたと言います。
社会が複雑になりすぎて、
スパコンをもってしても計画経済を運用することができずに、
破綻を迎えたわけです。
魔方陣と数独の研究がどうして金融最適化や運輸最適化等につながるのか、
この話は第１篇基礎編の最終章で詳しく解説していきます。
実は、実用的な研究は応用範囲が最も狭く歴史的条件が変わってしまうと、
使い物にならなくなります。
それに対して数学や基礎科学は応用範囲が無限と言えるほど広く、
実用的な学問より少し長いスパンで考えれば、
社会を変えるほどのインパクトをもった研究であるのです。
終章に期待してください。
次話では全体構造解析を応用した魔方陣自動生成ソフトについて考えていきます。
第13章第14話へ 第13章16話へ
本講義トップへ