第４話 確かめを派生スレッドで行う！
を実現するコード例
テキストファイル
第８講 理詰め解法エンジンの開発
第４話 確かめを派生スレッドで行う！
を実現するコード例
テキストファイル
#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;
char hnt = 26;
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);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
void hitaisyou(char a);//非対称の問題配置
void sayutaisyou(char a);//左右対称
void jyogetaisyou(char a);//上下対称
void tentaisyou(char a);//点対称
void kokoro(char a);
void sayujyogetaisyou(char a);//左右にも上下にも対象 = 線対称にして点対称 = 完全対称
char lst[th][n][n][n];//セルリスト解析によって可能な数字を収容する４次元配列
char lstcp[th][n][n][n];//セルリスト解析によって可能な数字を収容する４次元配列のコピー
char mx[th][n][n];//セルの数字候補の個数
char mxcp[th][n][n];//セルにおける数字候補の個数のコピー
char Y[th][81], X[th][81];//次に入力するセルのy座標とx座標
unsigned u = (unsigned)time(NULL);
//マルチスレッド化した際に、
//ルートスレッドと発生させたスレッドが共有できるようにグローバル変数に変更
void hontai(void* a);
void zahyousakusei(char a);
void ridume(char a);
char onoff[th][n][n][n];
char keizoku;
char A;
char H;
int main() {
clock_t hj, ow;
hj = clock();
hnt = 22;
int teisu = 1;
keizoku = 1;
sng = 1;
H = 1;
unsigned int ii[th];
for (unsigned char i = 0; i < th; i += 1) {
ii[i] = i;
_beginthread(hontai, 0, &ii[i]); //新しいスレッドを起動して、そのスレッド上で関数f1を働かせなさいの命令
}
while (keizoku);
char k = 0;
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (sudoku[A][y][x] > 0)k++;
}
}
hys(A);
k = 0;
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (mondai[A][y][x] > 0)k++;
}
}
cout << "予定されたヒント数：" << +hnt << endl;
k = 0;
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (mondai[A][y][x] > 0)k++;
}
}
cout << "実際の配置数：" << +k << endl;
hym(A);
int h = 1;
char hr[n];
for (char y = 0; y < n; y++) {
for (char i = 0; i < n; i++)hr[i] = 0;
for (char x = 0; x < n; x++)hr[mondai[A][y][x] - 1] = 1;
for (char i = 0; i < n; i++) {
if (hr[i] == 0) {
cout << "行異常：" << +y << endl;
h = 0;
goto tobi;
}
}
}
for (char y = 0; y < n; y++) {
for (char i = 0; i < n; i++)hr[i] = 0;
for (char x = 0; x < n; x++)hr[mondai[A][x][y] - 1] = 1;
for (char i = 0; i < n; i++) {
if (hr[i] == 0) {
cout << "列異常：" << +y << endl;
h = 0;
goto tobi;
}
}
}
for (char y = 0; y < n; y++) {
for (char i = 0; i < n; i++)hr[i] = 0;
for (char x = 0; x < n; x++) {
hr[mondai[A][3 * (y / 3) + (x / 3)][3 * (y % 3) + (x % 3)] - 1]
= 1;
}
for (char i = 0; i < n; i++) {
if (hr[i] == 0) {
cout << "ブロック異常：" << +i << endl;
goto tobi;
}
}
}
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
mondai[A][i][j] = sudoku[A][i][j];
}
}
sudokukaiho(A, hnt);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (sudoku[A][y][x] == mondai[A][y][x]) {
cout << "〇";
}
else {
cout << "×";
h = 0;
}
}
cout << endl;
}
tobi:;
if (h == 1)cout << "すべて正常でした。" << endl;
//以降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", sudoku[A][i][j]);//数独表示
}
}
for (unsigned char i = 0; i < n; i++) {
for (unsigned char j = 0; j < n; j++) {
fprintf(fp, "%d,\n", gensudoku[A][i][j]);//数独解答
}
}
}
/*忘れずに閉じる*/
fclose(fp);
ow = clock();
cout << "数独生成にかかった時間は" << (double)(ow - hj) / (teisu * CLOCKS_PER_SEC) << "秒です。" << endl;
//while (!_kbhit()); //待機させるための命令
return(0);
}
void hontai(void* aa) {
int a = *(int*)aa;
srand(u - 19 * a);
while (1) {
if (keizoku == 0)return;
zahyousakusei(a);
syokika(a);
f(a, 0);
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
mondai[a][i][j] = sudoku[a][i][j];
}
}
for (char i = 0; i < 20; i++) {//派生スレッドで実際に配置された数字の個数が81なっているか確かめている
ridume(a);
char k = 0;
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (mondai[a][y][x] > 0)k++;
}
}
if (k == 81) {
cn1[a] = 1;
if (H == 1) {
A = a;
H = 0;
}
keizoku = 0;
return;
}
}
//sudokukaiho(a, hnt);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
if (keizoku == 0)return;
if (cn1[a] == 1) {
if (H == 1) {
A = a;
H = 0;
}
keizoku = 0;
return;
}
}
}
void ridume(char a) {
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (mondai[a][y][x] > 0) {
for (char i = 0; i < n; i++) {
if (i != x) {
if (mondai[a][y][i] == 0) {
onoff[a][y][i][mondai[a][y][x] - 1] = 1;
}
}
}
for (char i = 0; i < n; i++) {
if (i != y) {
if (mondai[a][i][x] == 0) {
onoff[a][i][x][mondai[a][y][x] - 1] = 1;
}
}
}
for (char i = 0; i < n; i++) {
char yy = 3 * (y / 3) + (i / 3);
char xx = 3 * (x / 3) + (i % 3);
if (yy != y || xx != x) {
if (mondai[a][yy][xx] == 0) {
onoff[a][yy][xx][mondai[a][y][x] - 1] = 1;
}
}
}
}
}
}
for (char i = 0; i < n; i++) {
for (char y = 0; y < n; y++) {
char k = 0;
for (char j = 0; j < n; j++) {
if (mondai[a][y][j] == 0) {
if (onoff[a][y][j][i] == 0)k++;
}
}
if (k == 1) {
char xk = 0;
for (char j = 0; j < n; j++) {
if (mondai[a][y][j] == 0) {
if (onoff[a][y][j][i] == 0) {
xk = j;
break;
}
}
}
mondai[a][y][xk] = i + 1;
for (char j = 0; j < n; j++) {
if (j != xk) {
if (mondai[a][y][j] == 0) {
onoff[a][y][j][i] = 1;
}
}
}
for (char j = 0; j < n; j++) {
if (j != y) {
if (mondai[a][j][xk] == 0) {
onoff[a][j][xk][i] = 1;
}
}
}
for (char j = 0; j < n; j++) {
char yy = 3 * (y / 3) + (j / 3);
char xx = 3 * (xk / 3) + (j % 3);
if (yy != y && xx != xk) {
if (mondai[a][yy][xx] == 0) {
onoff[a][yy][xx][i] = 1;
}
}
}
}
}
for (char x = 0; x < n; x++) {
char k = 0;
for (char j = 0; j < n; j++) {
if (mondai[a][j][x] == 0) {
if (onoff[a][j][x][i] == 0)k++;
}
}
if (k == 1) {
char yk = 0;
for (char j = 0; j < n; j++) {
if (mondai[a][j][x] == 0) {
if (onoff[a][j][x][i] == 0) {
yk = j;
break;
}
}
}
mondai[a][yk][x] = i + 1;
for (char j = 0; j < n; j++) {
if (j != yk) {
if (mondai[a][j][x] == 0) {
onoff[a][j][x][i] = 1;
}
}
}
for (char j = 0; j < n; j++) {
if (j != x) {
if (mondai[a][yk][j] == 0) {
onoff[a][yk][j][i] = 1;
}
}
}
for (char j = 0; j < n; j++) {
char yy = 3 * (yk / 3) + (j / 3);
char xx = 3 * (x / 3) + (j % 3);
if (yy != yk || xx != x) {
if (mondai[a][yy][xx] == 0) {
onoff[a][yy][xx][i] = 1;
}
}
}
}
}
for (char y = 0; y < 9; y++) {
for (char x = 0; x < 9; x++) {
if (mondai[a][y][x] > 0) {
char k = 0;
for (int j = 0; j < 9; j++) {
char yy = 3 * (y / 3) + (j / 3);
char xx = 3 * (x / 3) + (j % 3);
if (yy != y || xx != x) {
if (mondai[a][yy][xx] == 0) {
if (onoff[a][yy][xx][i] == 0)k++;
}
}
}
if (k == 1) {
char yk = 0;
char xk = 0;
for (int j = 0; j < 9; j++) {
char yy = 3 * (y / 3) + (j / 3);
char xx = 3 * (x / 3) + (j % 3);
if (yy != y || xx != x) {
if (mondai[a][yy][xx] == 0) {
if (onoff[a][yy][xx][i] == 0) {
yk = yy;
xk = xx;
break;
}
}
}
}
mondai[a][yk][xk] = i + 1;
for (int j = 0; j < n; j++) {
if (j != xk) {
onoff[a][yk][j][i] = 1;
}
}
for (char j = 0; j < n; j++) {
if (j != x) {
if (mondai[a][yk][j] == 0) {
onoff[a][yk][j][i] = 1;
}
}
}
for (char j = 0; j < n; j++) {
char yy = 3 * (yk / 3) + (j / 3);
char xx = 3 * (xk / 3) + (j % 3);
if (yy != yk || xx != x) {
if (mondai[a][yy][xx] == 0) {
onoff[a][yy][xx][i] = 1;
}
}
}
}
}
}
}
}
}
で検査している内容は、
k = 0;
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (mondai[A][y][x] > 0)k++;
}
}
cout << "実際の配置数：" << +k << endl;
hym(A);
int h = 1;
char hr[n];
for (char y = 0; y < n; y++) {
for (char i = 0; i < n; i++)hr[i] = 0;
for (char x = 0; x < n; x++)hr[mondai[A][y][x] - 1] = 1;
for (char i = 0; i < n; i++) {
if (hr[i] == 0) {
cout << "行異常：" << +y << endl;
h = 0;
goto tobi;
}
}
}
for (char y = 0; y < n; y++) {
for (char i = 0; i < n; i++)hr[i] = 0;
for (char x = 0; x < n; x++)hr[mondai[A][x][y] - 1] = 1;
for (char i = 0; i < n; i++) {
if (hr[i] == 0) {
cout << "列異常：" << +y << endl;
h = 0;
goto tobi;
}
}
}
for (char y = 0; y < n; y++) {
for (char i = 0; i < n; i++)hr[i] = 0;
for (char x = 0; x < n; x++) {
hr[mondai[A][3 * (y / 3) + (x / 3)][3 * (y % 3) + (x % 3)] - 1]
= 1;
}
for (char i = 0; i < n; i++) {
if (hr[i] == 0) {
cout << "ブロック異常：" << +i << endl;
goto tobi;
}
}
}
for (char i = 0; i < n; i++) {
for (char j = 0; j < n; j++) {
mondai[A][i][j] = sudoku[A][i][j];
}
}
sudokukaiho(A, hnt);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
for (char y = 0; y < n; y++) {
for (char x = 0; x < n; x++) {
if (sudoku[A][y][x] == mondai[A][y][x]) {
cout << "〇";
}
else {
cout << "×";
h = 0;
}
}
cout << endl;
}
tobi:;
if (h == 1)cout << "すべて正常でした。" << endl;
答えの行上・列上・ブロック上に数字の重複がないこと、
sudokukaiho(A, hnt);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
で解かせた解答と派生スレッドが作った解答と比較しながら、
すべてが一致していることを確認しています。
第３話へ 第５話へ
トップへ