第６講 残された課題の解消とマルチスレッド化
第８話 C++マルチスレッド版全文
致命的と言えるミスをしていました。
訂正箇所は青で示してあります。
#pragma warning(disable: 4996)
#include<iostream>
#include<conio.h> //while (!_kbhit())を使うために必要
#include <process.h> /* _beginthread, _endthread を使うために必要*/
using namespace std;
void f(char a, char s); //sは次元番号=部屋番号
const char n = 9; //16次数独や25次数独も考えてnと一般化した。
const char th = 30;
const char hnt = 35;
const char tm = 81;
char cn[th]; //順列を数える変数
char cn1[th]; //順列を数える変数
char sudoku[th][n][n]; //解答用２次元配列（魔方陣の研究から始まったので本体をmとしてきた。
char mondai[th][n][n];
//mondai[th][n][n]は問題用であるが、解いていく過程で空欄が埋められて行って
//最終的にはsudoku[th][n][n]と同じになってしまう。
char gensudoku[th][n][n];
char sng = 1;//１ならば真
void syokika(char a);//初期化
void hyg(char a);//数独をコンソール画面に表示する関数
void hym(char a);//数独に向かう過程をコンソール画面に表示する関数
void hys(char a);//数独解答をコンソール画面に表示する関数
void kyokusyokaiseki(char a, char y, char x);//単セル解析（候補数字探索）
void nextcell(char a, char g);//次に入力するセルを探索する関数
void sudokukaiho(char a, char g);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
char lst[th][n][n][n];//セルリスト構造解析によって可能な数字を収容する３次元配列
char mx[th][n][n];//セルの数字候補の個数
char Y[th][81], X[th][81];//次に入力するセルのy座標とx座標
unsigned u = (unsigned)time(NULL);
//マルチスレッド化した際に、
//ルートスレッドと発生させたスレッドが共有できるようにグローバル変数に変更
void hontai(void* a);
char keizoku[th];
char A;
char main() {
clock_t hj, ow;
hj = clock();
for (char i = 0; i < th; i++)keizoku[i] = 1;
unsigned int ii[th];
for (unsigned char i = 0; i < th; i += 1) {
ii[i] = i;
_beginthread(hontai, 0, &ii[i]); //新しいスレッドを起動して、そのスレッド上で関数f1を働かせなさいの命令
}
while (1) {
int c = 0;
for (char v = 0; v < th; v++)c += keizoku[v];
if (c == 0)break;
}
ow = clock();
hyg(A);
hys(A);
//以降CSVファイルの作成
FILE* fp;
/*ファイル(save.csv)に書き込む*/
if ((fp = fopen("a.csv", "w")) != NULL) {
for (unsigned char i = 0; i < n; i++) {
for (unsigned char j = 0; j < n; j++) {
fprintf(fp, "%d,\n", gensudoku[A][i][j]);//数独表示
}
}
for (unsigned char i = 0; i < n; i++) {
for (unsigned char j = 0; j < n; j++) {
fprintf(fp, "%d,\n", sudoku[A][i][j]);//数独解答
}
}
}
/*忘れずに閉じる*/
fclose(fp);
cout << "数独生成にかかった時間は" << (double)(ow - hj) / CLOCKS_PER_SEC
<< "秒です。" << endl;
cout << "プロジェクト終了" << endl;
//while (!_kbhit()); //待機させるための命令
return(0);
}
void hontai(void* aa) {
int a = *(int*)aa;
srand(u - 19 * a);
while (1) {
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}
syokika(a);
f(a, 0);
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
if (keizoku[a] == 0)return;
if (mondai[a][i][j] == 0)kyokusyokaiseki(a, i, j);
//セルリスト構造解析 = 単セル解析を積み重ねれば全体構造解析になる
}
}
sudokukaiho(a, hnt);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}
if (cn1[a] == 1) {
A = a;
keizoku[a] = 0;
return;
}
}
}
void syokika(char a) {
cn[a] = 0;
cn1[a] = 0;
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
gensudoku[a][i][j] = 0;//数独本体 mondai[a][i][j]は戻ってきた段階でこれと一致するのでなくてもよい
sudoku[a][i][j] = 0;//数独解答
mondai[a][i][j] = 0;//最初はgensudoku[a][i][j] と一致しているが、複雑な経過をたどりsudoku[a][i][j]と //一致する。キャンセルが存在するために最後にはgensudoku[a][i][j]と一致する
}
}
}
void hyg(char a) {
for (char i = 0; i < 26; i++)cout << " -"; //最初の横線
cout << endl;
for (char i = 0; i < n; i++) {
cout << "｜";//最初の縦線
for (char j = 0; j < n; j++) {
if (gensudoku[a][i][j] > 0) {
cout << " " << +gensudoku[a][i][j] <<
" "; //２次元配列を２次元に並べる
}
else {
cout << " " << " " << " ";
//２次元配列を２次元に並べる
}
if (j % 3 == 2)cout << "｜";//２本目３本目の縦線
}
if (i % 3 == 2) {
cout << endl;
for (char j = 0; j < 26; j++)cout << " -"; //２本目３本目の横線
}
cout << endl;
}
}
void hym(char a) {//数独表示関数
for (char i = 0; i < 26; i++)cout << " -"; //最初の横線
cout << endl;
for (char i = 0; i < n; i++) {
cout << "｜";//最初の縦線
for (char j = 0; j < n; j++) {
if (mondai[a][i][j] > 0) {
cout << " " << +mondai[a][i][j] <<
" "; //２次元配列を２次元に並べる
}
else {
cout << " " << " " << " ";
//２次元配列を２次元に並べる
}
if (j % 3 == 2)cout << "｜";//２本目３本目の縦線
}
if (i % 3 == 2) {
cout << endl;
for (char j = 0; j < 26; j++)cout << " -"; //２本目３本目の横線
}
cout << endl;
}
}
void hys(char a) {
for (char i = 0; i < 26; i++)cout << " -"; //最初の横線
cout << endl;
for (char i = 0; i < n; i++) {
cout << "｜";//最初の縦線
for (char j = 0; j < n; j++) {
if (sudoku[a][i][j] > 0) {
cout << " " << +sudoku[a][i][j] <<
" "; //２次元配列を２次元に並べる
}
else {
cout << " " << " " << " ";
//２次元配列を２次元に並べる
}
if (j % 3 == 2)cout << "｜";//２本目３本目の縦線
}
if (i % 3 == 2) {
cout << endl;
for (char j = 0; j < 26; j++)cout << " -"; //２本目３本目の横線
}
cout << endl;
}
}
void kyokusyokaiseki(char a, char y, char x) {//局所解析 = 単セルリスト構造解析
for (char i = 0; i < n; i++)lst[a][y][x][i] = i + 1;//初期化{1,2,3,4,5,6,7,8,9}とする
mx[a][y][x] = 0;//{1,2,3,4,5,6,7,8,9}を{2,4}等にするために0に初期化 再カウントのため
for (char i = 0; i < n; i++) {//mondai[a][y][x]と同じ行にあるセルへの影響を調べる
if (i != x) {//自分自身は対象にしない
if (mondai[a][y][i] > 0) {//空欄のみを対象とする
for (char j = 0; j < n; j++) {
if (lst[a][y][x][j] == mondai[a][y][i])lst[a][y][x][j] = 0;
//mondai[a][y][i]と一致する数字を0にすることによって候補から外す
}
}
}
}
for (char i = 0; i < n; i++) {//mondai[a][y][x]と同じ列にあるセルへの影響を調べる
if (i != y) {
if (mondai[a][i][x] > 0) {//空欄のみを対象とする
for (char j = 0; j < n; j++) {
if (lst[a][y][x][j] == mondai[a][i][x])lst[a][y][x][j] = 0;
//mondai[a][i][x]と一致する数字を0にすることによって候補から外す
}
}
}
}
for (char i = 0; i < n; i++) {//mondai[a][y][x]と同じブロックにあるセルへの影響を調べる
if (3 * (y / 3) + (i / 3) != y && 3 * (x / 3) + (i % 3) !=
x) {//行と列の分析との重複を防ぐ
if (mondai[a][3 * (y / 3) + (i / 3)][3 * (x / 3) + (i % 3)] >
0) {//空欄を対象とする
for (char j = 0; j < n; j++) {
if (lst[a][y][x][j] == mondai[a][3 * (y / 3) + (i / 3)][3 * (x
/ 3) + (i % 3)])lst[a][y][x][j] = 0;
//mondai[3 * (y / 3) + (i / 3)][3 * (x / 3) + (i % 3)]と一致する数字を
//0にすることによって候補から外す
}
}
}
}
for (char i = 0; i < n; i++) {
if (lst[a][y][x][i] > 0) {
lst[a][y][x][mx[a][y][x]] = lst[a][y][x][i];
//例えば、{0, 2, 0, 4, 0, 0, 0, 0, 0}を{2, 4}と詰めて0を含めない
mx[a][y][x]++;//候補数字の個数のカウント
}
}
}
void nextcell(char a, char g) {//次に入力するセルの座標を探索する関数
char mn = 10;
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
if (mondai[a][i][j] == 0) {//空欄のみをランキング対象にする
if (mx[a][i][j] < mn) {//<=でないことによって左及び上が優先される
mn = mx[a][i][j];
Y[a][g] = i;
X[a][g] = j;
}
}
}
}
}
void sudokukaiho(char a, char g) {//数独を解くエンジン
nextcell(a, g);//座標(Y[a][g], X[a][g])の取得
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
for (char i = 0; i < mx[a][Y[a][g]][X[a][g]]; i++) {
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
mondai[a][Y[a][g]][X[a][g]] = lst[a][Y[a][g]][X[a][g]][i];
//候補の数字を代入 例えば、mondai[0][1]なら{2, 4}の2，4の順に代入する
for (char j = 0; j < n; j++)if (j != X[a][g])if (mondai[a][Y[a][g]][j]
== 0)kyokusyokaiseki(a, Y[a][g], j);
//x[Y[a][g]][X[a][g]]と同じ行にあるセルの単セル解析（候補数字探索）
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
for (char j = 0; j < n; j++)if (j != Y[a][g])if (mondai[a][j][X[a][g]]
== 0)kyokusyokaiseki(a, j, X[a][g]);
//x[Y[a][g]][X[a][g]]と同じ列にあるセルの単セル解析（候補数字探索）
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
char s = 3 * (Y[a][g] / 3);
char t = 3 * (X[a][g] / 3);
for (char j = 0; j < n; j++) {
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (s + (j / 3) != Y[a][g] && t + (j % 3) != X[a][g]) {//行解析と列解析と重複させないため
if (mondai[a][s + (j / 3)][t + (j % 3)] == 0) {
kyokusyokaiseki(a, s + (j / 3), t + (j % 3));
//x[Y[a][g]][X[a][g]]と同じブロックにあるセルの単セル解析（候補数字探索）
}
}
}
if (g + 1 < tm)sudokukaiho(a, g + 1);//内側部屋へ
if (cn1[a] == 2) {
return;//複数解
}
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (g == tm - 1) {
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
if (mondai[a][i][j] != sudoku[a][i][j]) {
cn1[a] = 2;
return;
}
}
}
cn1[a]++;
}
if (i == mx[a][Y[a][g]][X[a][g]] - 1) {
//i < mx[a][Y[a][g]][X[a][g]] - 1)のときはiが１つ進んで上で単セル解析（候補数字探索）を行うので
//キャンセルは不要だが、最後だけはキャンセルをしなければならないので単セル解析（候補数字探 //索）を行う必要がある
//cout << "*-*-*-*-復元-*-*-*-*-*" << endl;
mondai[a][Y[a][g]][X[a][g]] = 0;
//cout << g << endl;
for (char j = 0; j < n; j++)if (j != X[a][g])if (mondai[a][Y[a][g]][j]
== 0)kyokusyokaiseki(a, Y[a][g], j);
for (char j = 0; j < n; j++)if (j != Y[a][g])if (mondai[a][j][X[a][g]]
== 0)kyokusyokaiseki(a, j, X[a][g]);
for (char j = 0; j < n; j++) {
if (s + (j / 3) != Y[a][g] && t + (j % 3) != X[a][g]) {
if (mondai[a][s + (j / 3)][t + (j % 3)] == 0) {
kyokusyokaiseki(a, s + (j / 3), t + (j % 3));
}
}
}
}
}
}
void f(char a, char s) {//ヒント数0の数独を解く関数
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
char y = s / 9; //縦座標
char x = s % 9; //横座標
char e[n];
e[0] = rand() % 9 + 1;
char i = 1;
while (i < 9) {
e[i] = rand() % 9 + 1;
while (1) {
char h = 1;
e[i] = rand() % 9 + 1;
for (char j = 0; j < i; j++) {
if (e[i] == e[j]) {
h = 0;
break;
}
}
if (h == 1)break;
}
i++;
}
char ii = rand() % 9; //始まりをランダムにする
for (char i = 0; i < n; i++) {
sudoku[a][y][x] = e[(i + ii) % n]; //２次元配列に１から９までの整数を入力
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (x > 0) {
for (char j = 0; j < x; j++) {
if (sudoku[a][y][x] == sudoku[a][y][j])goto tobi; //行の重複を防ぐ
}
}
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (y > 0) {
for (char j = 0; j < y; j++) {
if (sudoku[a][j][x] == sudoku[a][y][x])goto tobi; //行の重複を防ぐ
}
}
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (y % 3 == 1) {
for (char j = 0; j < 3; j++) {
if ((x / 3) * 3 + j != x) {
if (sudoku[a][y][x] == sudoku[a][y - 1][(x / 3) * 3 + j])goto
tobi; //ブロックの重複を防ぐ
}
}
}
if (y % 3 == 2) {
for (char j = 0; j < 3; j++) {
if ((x / 3) * 3 + j != x) {
if (sudoku[a][y][x] == sudoku[a][y - 2][(x / 3) * 3 + j])goto
tobi; //ブロックの重複を防ぐ
if (sudoku[a][y][x] == sudoku[a][y - 1][(x / 3) * 3 + j])goto
tobi; //ブロックの重複を防ぐ
}
}
}
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (s + 1 < n * n)f(a, s + 1); //１つ奥の部屋に入室
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
if (cn[a] == 1)return; //数独が1個できた時点で止める
if (sng == 0)return; //異常があった時点でプロジェクトを止める
if (s == n * n - 1) { //一番奥に部屋に到達
char hb; //部屋番号
char tbs[13] = { 11,13,17,19,23,29,31,37,41,43,47,53,59 }; //飛びの選択肢
//素数であれば81と互いに素は保証されている
char st = rand() % 81; //始めの位置
char tb = tbs[rand() % 13]; //飛び
char h = 0; //可否の否
char* gohr = (char*)calloc(hnt, sizeof(char));
for (char t = 0; t < hnt; t++) {
gohr[t] = (st + t * tb) % 81;
}
for (char j = 0; j < n; j++) {
for (char k = 0; k < n; k++) {
if (keizoku[a] == 0) {
for (char v = 0; v < th; v++)keizoku[v] = 0;
return;
}//数独を発見したスレッドからの連絡および閉じよの指令
hb = n * j + k; //部屋番号の再初期化 = 空欄の数字候補の個数の小さい順に入れる
char h = 0; //可否の否
for (char t = 0; t < hnt; t++) {
if (gohr[t] == hb) {
h = 1;//可否の可
break;
}
}
if (h == 1) {
mondai[a][j][k] = sudoku[a][j][k]; //問題用の配列に代入
gensudoku[a][j][k] = sudoku[a][j][k];
}
}
}
//hy();//問題表示
free(gohr); //メモリ解放
cn[a]++;
if (cn[a] == 1)return; //数独が1個できた時点でとめる
}
tobi:;
}
}
第７話へ 第９話へ
トップへ