第７講 左右対称形・上下対称形・点対称形・左右にも上下に対称・ハート型
第15話 問題を先に作ってから解く方式
#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);
char keizoku;
char A;
char H;
char main() {
clock_t hj, ow;
hj = clock();
hnt = 27;
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);
hyg(A);
if (k == hnt)cout << "〇" << endl;
cout << "予定されたヒント数：" << +hnt << endl;
cout << "実際のヒント数：" << +k << 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];
}
}
sudokukaiho(a, hnt);//数独を解くエンジン 部分構造解析を進めながら問題を解いていく
if (keizoku == 0)return;
if (cn1[a] == 1) {
if (H == 1) {
A = a;
H = 0;
}
keizoku = 0;
return;
}
}
}
void zahyousakusei(char a) {
char k;
if (hnt < 22)k = rand() % 4; else k = rand() % 5;
if (k == 0)sayutaisyou(a);
if (k == 1)jyogetaisyou(a);
if (k == 2)tentaisyou(a);
if (k == 3)sayujyogetaisyou(a);
if (k == 4)kokoro(a);
}
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]と一致する
mx[a][i][j] = 9;
for (char k = 0; k < n; k++)lst[a][i][j][k] = k + 1;
}
}
}
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++) {//sudoku[a][y][x]と同じ行にあるセルからの影響を調べる
if (i != x) {//自分自身は対象にしない
if (sudoku[a][y][i] > 0) {//数字が入っている欄のみを対象とする
for (char j = 0; j < n; j++) {
if (lst[a][y][x][j] == sudoku[a][y][i])lst[a][y][x][j] = 0;
//sudoku[a][y][i]と一致する数字を0にすることによって候補から外す
}
}
}
}
for (char i = 0; i < n; i++) {//sudoku[a][y][x]と同じ列にあるセルからの影響を調べる
if (i != y) {
if (sudoku[a][i][x] > 0) {//数字が入っている欄のみを対象とする
for (char j = 0; j < n; j++) {
if (lst[a][y][x][j] == sudoku[a][i][x])lst[a][y][x][j] = 0;
//sudoku[a][i][x]と一致する数字を0にすることによって候補から外す
}
}
}
}
for (char i = 0; i < n; i++) {//sudoku[a][y][x]と同じブロックにあるセルからの影響を調べる
char yy = 3 * (y / 3) + (i / 3);
char xx = 3 * (x / 3) + (i % 3);
if (yy != y && xx != x) {//行と列の分析との重複を防ぐ
if (sudoku[a][yy][xx] == 0) {//空欄を対象とする
for (char j = 0; j < n; j++) {
if (lst[a][y][x][j] == sudoku[a][yy][xx])lst[a][y][x][j] = 0;
//sudoku[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])の取得
char y = Y[a][g];
char x = X[a][g];
if (keizoku == 0)return;//数独を発見したスレッドからの連絡および閉じよの指令
for (char i = 0; i < mx[a][y][x]; i++) {
char gy[n] = { 0,0,0,0,0,0,0,0,0 };
char r[n] = { 0,0,0,0,0,0,0,0,0 };
char b[n] = { 0,0,0,0,0,0,0,0,0 };
mondai[a][y][x] = lst[a][y][x][i];
//候補の数字を代入 例えば、mondai[0][1]なら{2, 4}の2，4の順に代入する
if (keizoku == 0)return;
//x[y][x]と同じ行にあるセルへの影響を調べる。
//具体的には座標(y, j)においてmondai[a][y][x]が候補数字に入っている場合には
//候補から外し、候補数字の個数も一つ減らす。
for (char j = 0; j < n; j++) {
if (j != x) {//自己を対象から外す。
if (mondai[a][y][j] == 0) {//空欄のみを解析対象にする。
for (char k = 0; k < mx[a][y][j]; k++) {
if (keizoku == 0)return;
if (mondai[a][y][x] == lst[a][y][j][k]) {
lst[a][y][j][k] = lst[a][y][j][mx[a][y][j] - 1];
lst[a][y][j][mx[a][y][j] - 1] = mondai[a][y][x];
mx[a][y][j]--;
gy[j] = 1;//座標(y, j)においてmondai[a][y][x]が候補数字から外され、
//候補数字数も減らされたことを記録している。
}
}
}
}
}
if (keizoku == 0)return;
for (char j = 0; j < n; j++) {
if (j != y) {//自己を対象から外す。
if (mondai[a][j][x] == 0) {//空欄のみを解析対象にする。
for (char k = 0; k < mx[a][j][x]; k++) {
if (keizoku == 0)return;
if (mondai[a][y][x] == lst[a][j][x][k]) {
lst[a][j][x][k] = lst[a][j][x][mx[a][j][x] - 1];
lst[a][j][x][mx[a][j][x] - 1] = mondai[a][y][x];
mx[a][j][x]--;
r[j] = 1;//座標(j, x)においてmondai[a][y][x]が候補数字から外され、
//候補数字数も減らされたことを記録している。
}
}
}
}
}
if (keizoku == 0)return;
char s = 3 * (y / 3);
char t = 3 * (x / 3);
for (char j = 0; j < n; j++) {
char yy = s + (j / 3);
char xx = t + (j % 3);
if (yy != y && xx != x) {//自己を対象から外す。
if (mondai[a][yy][xx] == 0) {//空欄のみを解析対象にする。
for (char k = 0; k < mx[a][yy][xx]; k++) {
if (keizoku == 0)return;
if (mondai[a][y][x] == lst[a][yy][xx][k]) {
lst[a][yy][xx][k] = lst[a][yy][xx][mx[a][yy][xx] - 1];
lst[a][yy][xx][mx[a][yy][xx] - 1] = mondai[a][y][x];
mx[a][yy][xx]--;
b[j] = 1;//座標(j, x)においてmondai[a][y][x]が候補数字から外され、
//候補数字数も減らされたことを記録している。
}
}
}
}
}
if (g + 1 < tm)sudokukaiho(a, g + 1);//内側部屋へ
if (cn1[a] == 2) {
return;//複数解
}
if (keizoku == 0)return;
if (g + 1 == tm) {
for (char j = 0; j < n; j++) {
for (char k = 0; k < n; k++) {
gensudoku[a][j][k] = mondai[a][j][k];//解答の保存
}
}
cn1[a]++;
}
for (char j = 0; j < n; j++) {//以下復元作業
if (gy[j] == 1) {
mx[a][y][j]++;
}
if (r[j] == 1) {
mx[a][j][x]++;
}
if (b[j] == 1) {
char yy = 3 * (y / 3) + (j / 3);
char xx = 3 * (x / 3) + (j % 3);
mx[a][yy][xx]++;
}
}
}
}
void f(char a, char s) {//ヒント数0の数独を解く関数
if (keizoku == 0)return;
char y = Y[a][s];
char x = X[a][s];
//kyokusyokaiseki(a, y, x);
char ii;
if (mx[a][y][x] > 0)ii = rand() % mx[a][y][x]; else ii = 0;
for (char i = 0; i < mx[a][y][x]; i++) {
char iii = (ii + i) % mx[a][y][x];
char g[n] = { 0,0,0,0,0,0,0,0,0 };
char r[n] = { 0,0,0,0,0,0,0,0,0 };
char b[n] = { 0,0,0,0,0,0,0,0,0 };
sudoku[a][y][x] = lst[a][y][x][iii]; //２次元配列に候補数字を代入
//座標(y, x)に値sudoku[a][y][x]が入ったことによってy行にある他のセル
//への影響を調べています。具体的にはy行にある他のセルの候補数字sudoku[a][y][x]
//が入っている場合にsudoku[a][y][x]を候補数字から外します。
//自己から他セルへの影響を調べています。
for (char j = 0; j < n; j++) {
if (j != x) {//自分自身を含めない
if (sudoku[a][y][j] == 0) {//空欄のみを対象とする
for (char k = 0; k < mx[a][y][j]; k++) {
if (keizoku == 0)return;
if (sudoku[a][y][x] == lst[a][y][j][k]) {
lst[a][y][j][k] = lst[a][y][j][mx[a][y][j] - 1];
lst[a][y][j][mx[a][y][j] - 1] = sudoku[a][y][x];
mx[a][y][j]--;
g[j] = 1;//座標(y,j)上で行われた。この情報は復元するときに必要
break;
}
}
}
}
}
if (keizoku == 0)return;
//座標(y, x)に値sudoku[a][y][x]が入ったことによってy行にある他のセル
//への影響を調べています。具体的にはy行にある他のセルの候補数字にsudoku[a][y][x]
//が入っている場合にsudoku[a][y][x]を候補数字から外します。
//自己から他セルへの影響を調べています。
for (char j = 0; j < n; j++) {
if (j != y) {//自分自身を含めない
if (sudoku[a][j][x] == 0) {//空欄のみを対象とする
for (char k = 0; k < mx[a][j][x]; k++) {
if (keizoku == 0)return;
if (sudoku[a][y][x] == lst[a][j][x][k]) {
lst[a][j][x][k] = lst[a][j][x][mx[a][j][x] - 1];
lst[a][j][x][mx[a][j][x] - 1] = sudoku[a][y][x];
mx[a][j][x]--;
r[j] = 1;//座標(y,j)上で行われた。この情報は復元するときに必要
break;
}
}
}
}
}
if (keizoku == 0)return;
//座標(y, x)に値sudoku[a][y][x]が入ったことによって同じブロックにある他のセル
//への影響を調べています。具体的にはブロックにある他のセルの候補数字にsudoku[a][y][x]
//が入っている場合にsudoku[a][y][x]を候補数字から外します。
//ただし、x列とy行についてはすでに調べているので、それらの空欄は対象から外してあります。
//自己から他セルへの影響を調べています。
for (char j = 0; j < n; j++) {
char yy = 3 * (y / 3) + (j / 3);
char xx = 3 * (x / 3) + (j % 3);
if (yy != y && xx != x) {//自分自身を含めないおよび行と列との重複を防ぐ
if (sudoku[a][yy][xx] == 0) {//空欄のみを対象とする
for (char k = 0; k < mx[a][yy][xx]; k++) {
if (keizoku == 0)return;
if (sudoku[a][y][x] == lst[a][yy][xx][k]) {
lst[a][yy][xx][k] = lst[a][yy][xx][mx[a][yy][xx] - 1];
lst[a][yy][xx][mx[a][yy][xx] - 1] = sudoku[a][y][x];
mx[a][yy][xx]--;
b[j] = 1;//座標(y,j)上で行われた。この情報は復元するときに必要
break;
}
}
}
}
}
if (keizoku == 0)return;
if (s + 1 < hnt)f(a, s + 1); //１つ奥の部屋に入室
if (keizoku == 0)return;
if (cn[a] == 1)return; //数独が1個できた時点で止める
if (s == hnt - 1) { //一番奥に部屋に到達
for (char c = 0; c < 9; c++) {
for (char d = 0; d < 9; d++) {
if (sudoku[a][c][d] == 0) {
if (keizoku == 0)return;
mxcp[a][c][d] = mx[a][c][d];
for (char k = 0; k < mx[a][c][d]; k++) {
lstcp[a][c][d][k] = lst[a][c][d][k];
}
}
}
}
cn[a]++;
if (cn[a] == 1)return; //数独が1個できた時点でとめる
}
for (char j = 0; j < n; j++) {//以下復元作業
if (g[j] == 1) {
mx[a][y][j]++;
}
if (r[j] == 1) {
mx[a][j][x]++;
}
if (b[j] == 1) {
char yy = 3 * (y / 3) + (j / 3);
char xx = 3 * (x / 3) + (j % 3);
mx[a][yy][xx]++;
}
}
tobi:;
}
}
void hitaisyou(char a) {
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 == 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];
}
}
}
free(gohr); //メモリ解放
}
void sayutaisyou(char a) {
char k = hnt / 9;//中央列の個数の平均
char s[3] = { k - 1,k,k + 1 };//平均がk
char p;
if (hnt % 2 == 1) {//中央列以外は左右対称であるためにセルの個数は必ず偶数になるから
//セルの総数を奇数にするためには中央列の個数を奇数にしなければならない
while (1) {
p = s[rand() % 3]; //{ k - 1, k, k + 1}から１つを選ぶ
if (p % 2 == 1)break;//ヒント数が奇数の場合中央列はのセルの個数は奇数にするしかない
}
}
if (hnt % 2 == 0) {
while (1) {
p = s[rand() % 3];
if (p % 2 == 0)break;
}
}
char e[9];//大は小を兼ねる Y[a][]の過去を記録
char i = 0;
while (i <= p) {//すでに入っているセルとの重複を避ける
X[a][i] = 4;
if (i == 0) {
Y[a][i] = rand() % 9;
e[i] = Y[a][i];
}
if (i > 0) {
while (1) {
Y[a][i] = rand() % 9;
char h = 1;
for (char j = 0; j < i; j++) {
if (Y[a][i] == e[j]) {
h = 0;//１つでも一致したらwhile文は継続させる
break;
}
}
if (h == 1) {//hが 1 ということは過去のいずれとも一致しないので
//while文を終了させる
e[i] = Y[a][i];
break;
}
}
}
i++;
}
//if (p == 0)cout << "中央列には１個も入りません。";
for (char j = 0; j < p; j++) {
sudoku[a][Y[a][j]][X[a][j]] = 1;
}
char st = rand() % 36;
char tbk[8] = { 5,7,11,13,17,19,23,29 };//すべて素数であり36とは互いに素
char tb = tbk[rand() % 8];
for (i = 0; i < (hnt - p) / 2; i++) {
X[a][i] = ((st + tb * i) % 36) / 9;
//例えば、st = 20、tb = 13とすると
//20，33，10，23，0，13，26，3，16，29，6，19，32，
//9，22，35，12，25，2，15，28，5，18，31，8，21，34，11，24，1，14，27，4，17，30，7
//以下同じ循環を繰り返すが、重複なしに１巡目で0，1，2，・・・，35もれなく並べられること
//この手法を私たちは何度も使ってきた
Y[a][i] = ((st + tb * i) % 36) % 9;
X[a][i + 1] = 8 - X[a][i];//左右対称な位置
Y[a][i + 1] = Y[a][i];
sudoku[a][Y[a][i]][X[a][i]] = 1;
sudoku[a][Y[a][i + 1]][X[a][i + 1]] = 1;
}
}
void jyogetaisyou(char a) {
char k = hnt / 9;//中央列の個数の平均
char s[3] = { k - 1,k,k + 1 };//平均がk
char p;
if (hnt % 2 == 1) {//中央列以外は上下対称であるためにセルの個数は必ず偶数になるから
//セルの総数を奇数にするためには中央列の個数を奇数にしなければならない
while (1) {
p = s[rand() % 3]; //{ k - 1, k, k + 1}から１つを選ぶ
if (p % 2 == 1)break;//ヒント数が奇数の場合中央列はのセルの個数は奇数にするしかない
}
}
if (hnt % 2 == 0) {
while (1) {
p = s[rand() % 3];
if (p % 2 == 0)break;
}
}
char e[9];//大は小を兼ねる Y[a][]の過去を記録
char i = 0;
while (i <= p) {//すでに入っているセルとの重複を避ける
Y[a][i] = 4;
if (i == 0) {
X[a][i] = rand() % 9;
e[i] = Y[a][i];
}
if (i > 0) {
while (1) {
X[a][i] = rand() % 9;
char h = 1;
for (char j = 0; j < i; j++) {
if (X[a][i] == e[j]) {
h = 0;//１つでも一致したらwhile文は継続させる
break;
}
}
if (h == 1) {//hが 1 ということは過去のいずれとも一致しないので
//while文を終了させる
e[i] = X[a][i];
break;
}
}
}
i++;
}
//if (p == 0)cout << "中央列には１個も入りません。";
for (char j = 0; j < p; j++) {
sudoku[a][Y[a][j]][X[a][j]] = 1;
}
char st = rand() % 36;
char tbk[8] = { 5,7,11,13,17,19,23,29 };
char tb = tbk[rand() % 8];
for (i = 0; i < (hnt - p) / 2; i++) {
Y[a][i] = ((st + tb * i) % 36) / 9;
//例えば、st = 20、tb = 13とすると
//20，33，10，23，0，13，26，3，16，29，6，19，32，
//9，22，35，12，25，2，15，28，5，18，31，8，21，34，11，24，1，14，27，4，17，30，7
//以下同じ循環を繰り返すが、重複なしに１巡目で0，1，2，・・・，35もれなく並べられること
//この手法を私たちは何度も使ってきた
X[a][i] = ((st + tb * i) % 36) % 9;
Y[a][i + 1] = 8 - Y[a][i];//上下に対称な位置
X[a][i + 1] = X[a][i];
sudoku[a][Y[a][i]][X[a][i]] = 1;
sudoku[a][Y[a][i + 1]][X[a][i + 1]] = 1;
}
}
void tentaisyou(char a) {
char q = 0;
if (hnt % 2 == 1) {//点対称の場合はヒント数が奇数の場合には真ん中の座標(4, 4)に入れる必要がある。
//他のセルは点対称性から偶数個になるため
Y[a][0] = 4;
X[a][0] = 4;
q++;
}
char b = rand() % 2;
if (b == 1) {//中央行に左右対称に入れる
Y[a][q] = 4;
X[a][q] = rand() % 4;
q++;
Y[a][q] = 4;
X[a][q] = 8 - X[a][q - 1];
q++;
}
char st = rand() % 36;//36なのは上位４行を対象としているから 9×4 = 36
char tbs[8] = { 5,7,11,13,17,19,23,29 };//すべて素数であるから36とは互いに素である
char tb = tbs[rand() % 8];
for (char i = 0; ; i++) {
Y[a][q] = ((st + tb * i) % 36) / 9;
X[a][q] = ((st + tb * i) % 36) % 9;
Y[a][q + 1] = 8 - Y[a][q];//180°回転した位置
X[a][q + 1] = 8 - X[a][q];
q += 2;
if (hnt == q)break;
}
for (char i = 0; i < hnt; i++)sudoku[a][Y[a][i]][X[a][i]] = 1;
}
void sayujyogetaisyou(char a) {
char q = 0;
if (hnt % 2 == 1) {//ヒント数が奇数の場合には真ん中の座標(4, 4)に入れないないとだめ
//左右にも上下にも対称は線対称にして点対称であることと同値であり、
//点対称の要請から真ん中入力は必要
Y[a][0] = 4;
X[a][0] = 4;
q++;
}
if ((hnt - q) % 4 == 2) {//中央列と中央行にの両方に入れてしまうと４で割った時に余りが２であるから、
//どちらか一方を選ばないと矛盾してしまう
char b = rand() % 2;
if (b == 0) {
Y[a][q] = 4;
X[a][q] = rand() % 4;
q++;
Y[a][q] = 4;
X[a][q] = 8 - X[a][q - 1];
q++;
}
if (b == 1) {
Y[a][q] = rand() % 4;
X[a][q] = 4;
q++;
Y[a][q] = 8 - Y[a][q - 1];
X[a][q] = 4;
q++;
}
}
if ((hnt - q) % 4 == 0) {//(hnt - q) % 4 == 2の場合とは異なり、両方に入れないと４の倍数にならない
Y[a][q] = 4;
X[a][q] = rand() % 4;
q++;
Y[a][q] = 4;
X[a][q] = 8 - X[a][q - 1];
q++;
Y[a][q] = rand() % 4;
X[a][q] = 4;
q++;
Y[a][q] = 8 - Y[a][q - 1];
X[a][q] = 4;
q++;
}
char st = rand() % 16;//中央行と中央列を除いた左上1/4部分に対応
char tbs[5] = { 3,5,7,11,13 };//すべて素数であるから16との互いに素は保証されている
char tb = tbs[rand() % 5];
for (char i = 0; ; i++) {
Y[a][q] = ((st + tb * i) % 16) / 4;//中央行と中央列を除いた左上1/4部分に対応
X[a][q] = ((st + tb * i) % 16) % 4;
//例えば、st = 10,tb = 7とすると
//10，1，8，15，6，13，4，11，2，9，0，7，14，5，12，19
//一巡しただけで0～15までに数字がもれなく重複なしにそろう
//二巡以降も全く同じ動きする
Y[a][q + 1] = Y[a][q];
X[a][q + 1] = 8 - X[a][q];//左右対称性
Y[a][q + 2] = 8 - Y[a][q];//上下対称性
X[a][q + 2] = X[a][q];
Y[a][q + 3] = 8 - Y[a][q];//点対称性
X[a][q + 3] = 8 - X[a][q];
q += 4;
if (hnt == q)break;
}
for (char i = 0; i < q; i++)sudoku[a][Y[a][i]][X[a][i]] = 1;
}
void kokoro(char a) {//ハート型
int q = 0;
//以下ハートの外枠
//以下０列目
Y[a][q] = 2;
X[a][q] = 0;
q++;
Y[a][q] = 3;
X[a][q] = 0;
q++;
Y[a][q] = 4;
X[a][q] = 0;
q++;
//以下１列目
Y[a][q] = 1;
X[a][q] = 1;
q++;
Y[a][q] = 5;
X[a][q] = 1;
q++;
//以下２列目
Y[a][q] = 1;
X[a][q] = 2;
q++;
Y[a][q] = 6;
X[a][q] = 2;
q++;
//以下３列目
Y[a][q] = 2;
X[a][q] = 3;
q++;
Y[a][q] = 7;
X[a][q] = 3;
q++;
//以下４列目
Y[a][q] = 3;
X[a][q] = 4;
q++;
Y[a][q] = 8;
X[a][q] = 4;
q++;
//以下５列目
Y[a][q] = 2;
X[a][q] = 5;
q++;
Y[a][q] = 7;
X[a][q] = 5;
q++;
//以下６列目
Y[a][q] = 1;
X[a][q] = 6;
q++;
Y[a][q] = 6;
X[a][q] = 6;
q++;
//以下７列目
Y[a][q] = 1;
X[a][q] = 7;
q++;
Y[a][q] = 5;
X[a][q] = 7;
q++;
//以下８列目
Y[a][q] = 2;
X[a][q] = 8;
q++;
Y[a][q] = 3;
X[a][q] = 8;
q++;
Y[a][q] = 4;
X[a][q] = 8;
q++;
if (hnt % 2 == 1) {//青から１つ選択 解説を参照してください。
X[a][q] = 4;
Y[a][q] = 4 + rand() % 4;
q++;
}
//以下緑から不足分を選択 左右対称性のためにセル１つ選択すると対称の位置にあるセルも選択しなければならない。
char p[11] = { 19,28,37,20,29,38,47,30,39,48,57 };
char st = rand() % 11;
char tbs[7] = { 3,4,5,6,7,8,9 };//11が素数なので左の{}内は11と互いに素
//互いに素である場合７回以内では重複はあり得ない。
char tb = tbs[rand() % 7];//飛び
//例えば、(st + tb * t) % 11はstが5でtbが2なら5,7,9,4,6,8,3と7回で重複なしに網羅することになる。
//7回の7は配列tbsの要素数
for (char t = 0;; t++) {
Y[a][q] = p[(st + tb * t) % 11] / 9;//{ 19,28,37,20,29,38,47,30,39,48,57 }をY座標に転換
X[a][q] = p[(st + tb * t) % 11] % 9;//{ 19,28,37,20,29,38,47,30,39,48,57 }をX座標に転換
//11は配列pの要素数
q++;
Y[a][q] = Y[a][q - 1];
X[a][q] = 8 - X[a][q - 1];//緑を選択するとその対称な位置も選択しなければならない。
q++;
if (hnt == q)break;
}
/*for (char i = 0; i < hnt; i++) {
cout << +Y[a][i];
cout << +X[a][i] << " ";
if (i == 9)cout << endl;
}*/
//cout << endl;
for (char i = 0; i < hnt; i++)sudoku[a][Y[a][i]][X[a][i]] = 1;
}
第13話へ 第15話へ
トップへ