第６話 行・列・ブロックの重複検査をして異常がないときには〇を表示させる
・
・
・
を実現させるプロジェクト例
#include<iostream>
#include<conio.h> //while (!_kbhit()); を使うためのお呪い。
using namespace std;
void f(int s); //sは次元番号=部屋番号
int n; //次元数（部屋数）をキーボードから指定
int cn = 0; //順列を数える変数
int m[9][9];//本体２次元配列（魔方陣の研究から始まったので本体をmとしてきた
int sng = 1;//１ならば真
int main() {
//cout << "n = ";
//scanf_s("%d", &n); //キーボードからnの値を取得
n = 9;
clock_t hj, ow;
hj = clock();
f(0);
ow = clock();
if (sng == 1)cout << endl << "すべて正常でした。" << endl;
cout << "計算時間は" << (double)(ow - hj) / CLOCKS_PER_SEC << "秒です。" << endl;
cout << "順列の場合の数は" << cn << "です。" << endl;
cout << "プロジェクト成功" << endl;
while (!_kbhit()); //待機させるための命令
return(0);
}
void f(int s) {
int y = s / 9; //縦座標
int x = s % 9; //横座標
for (int i = 0; i < n; i++) {
m[y][x] = i + 1; //２次元配列に１から９までの整数を入力
if (x > 0) {
for (int j = 0; j < x; j++) {
if (m[y][x] == m[y][j])goto tobi; //行の重複を防ぐ
}
}
if (y > 0) {
for (int j = 0; j < y; j++) {
if (m[j][x] == m[y][x])goto tobi; //行の重複を防ぐ
}
}
if (y % 3 == 1) {
for (int j = 0; j < 3; j++) {
if ((x / 3) * 3 + j != x) {
if (m[y][x] == m[y - 1][(x / 3) * 3 + j])goto tobi; //ブロックの重複を防ぐ
}
}
}
if (y % 3 == 2) {
for (int j = 0; j < 3; j++) {
if ((x / 3) * 3 + j != x) {
if (m[y][x] == m[y - 2][(x / 3) * 3 + j])goto tobi; //ブロックの重複を防ぐ
if (m[y][x] == m[y - 1][(x / 3) * 3 + j])goto tobi; //ブロックの重複を防ぐ
}
}
}
if (s + 1 < n * n)f(s + 1); //１つ奥の部屋に入室
if (cn == 100)return; //数独が100個できた時点で止める
if (sng == 0)return; //異常があった時点でプロジェクトを止める
if (s == n * n - 1) { //一番奥に部屋に到達
cout << endl;
for (int j = 0; j < 17; j++)cout << " -"; //最初の横線
cout << endl;
for (int j = 0; j < n; j++) {
cout << "｜";//縦線
for (int k = 0; k < n; k++) {
cout << " " << m[j][k] << " "; //２次元配列を２次元に並べる
if (k % 3 == 2)cout << "｜";//縦線
}
if (j % 3 == 2) {
cout << endl;
for (int k = 0; k < 17; k++)cout << " -"; //横線
}
cout << endl;
}
int p[9];//重複検査のための配列
int kr;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++)p[k] = 0;//初期化
kr = 1; //初期化
for (int k = 0; k < n; k++) {
p[m[j][k] - 1] = 1;
}
for (int k = 0; k < n; k++) { //行検査
if (p[k] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
for (int k = 0; k < n; k++)p[k] = 0;//初期化
kr = 1; //初期化
for (int k = 0; k < n; k++) {
p[m[k][j] - 1] = 1;
}
for (int k = 0; k < n; k++) { //列検査
if (p[k] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
for (int k = 0; k < n; k++)p[k] = 0;//初期化
kr = 1; //初期化
for (int k = 0; k < n; k++) {
p[m[3 * (j / 3) + (k / 3)][3 * (j % 3) + (k % 3)] - 1] = 1;
}
for (int k = 0; k < n; k++) { //ブロック検査
if (p[k] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
}
tobi1:;
if (kr == 1)cout << "〇";
cn++;
if (cn == 100)return; //数独が100個で来た時点でとめる
}
tobi:;
}
}
解説
int p[9];//重複検査のための配列
int kr;
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++)p[k] = 0;//初期化
kr = 1; //初期化
for (int k = 0; k < n; k++) {
p[m[j][k] - 1] = 1;
}
for (int k = 0; k < n; k++) { //行検査
if (p[k] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
for (int k = 0; k < n; k++)p[k] = 0;//初期化
kr = 1; //初期化
for (int k = 0; k < n; k++) {
p[m[k][j] - 1] = 1;
}
for (int k = 0; k < n; k++) { //列検査
if (p[k] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
for (int k = 0; k < n; k++)p[k] = 0;//初期化
kr = 1; //初期化
for (int k = 0; k < n; k++) {
p[m[3 * (j / 3) + (k / 3)][3 * (j % 3) + (k % 3)] - 1] = 1;
}
for (int k = 0; k < n; k++) { //ブロック検査
if (p[k] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
}
tobi1:;
この部分について？？の人もいると思いますので、
解説します。
たとえば、赤い行の重複検査を考えるとします。
数の種類は９個ですから、９セルであれば重複はあり得ません。
いわゆる１：１対応です。
まず、
for (int k = 0; k < n; k++)p[k] = 0;//初期化によって
p[0]，p[1]，p[2]，p[3]，p[4]，p[5]，p[6]，p[7]，p[8]をすべて0とします。
すなわち、
p[0] = 0;
p[1] = 0;
p[2] = 0;
p[3] = 0;
p[4] = 0;
p[5] = 0;
p[6] = 0;
p[7] = 0;
p[8] = 0;
次に
for (int k = 0; k < n; k++) {
p[m[j][k] - 1] = 1;
}
よって、
p[m[4][0] - 1] = 1;
p[m[4][1] - 1] = 1;
p[m[4][2] - 1] = 1;
p[m[4][3] - 1] = 1;
p[m[4][0] - 1] = 1;
p[m[4][1] - 1] = 1;
p[m[4][2] - 1] = 1;
p[m[4][3] - 1] = 1;
p[m[4][3] - 1] = 1;
からp[9 - 1] = 1;
p[4 - 1] = 1;
p[1 - 1] = 1;
p[6 - 1] = 1;
p[3 - 1] = 1;
p[8 - 1] = 1;
p[5 - 1] = 1;
p[7 - 1] = 1;
p[2 - 1] = 1;
すなわち
p[8] = 1;
p[3] = 1;
p[0] = 1;
p[5] = 1;
p[2] = 1;
p[7] = 1;
p[4] = 1;
p[6] = 1;
p[1] = 1;
もし、
9，4，1，6，3，8，5，7，2
すなわち
8，3，0，5，2，7，4，6，1（これも1：1対応です。）
に重複がなければ
p[0] = 1;
p[1] = 1;
p[2] = 1;
p[3] = 1;
p[4] = 1;
p[5] = 1;
p[6] = 1;
p[7] = 1;
p[8] = 1;
となるはずです。
ご覧になればわかる通り重複がないので、
p[8] = 1;
p[3] = 1;
p[0] = 1;
p[5] = 1;
p[2] = 1;
p[7] = 1;
p[4] = 1;
p[6] = 1;
p[1] = 1;
が実現されてすべてが1になるのです。
ですが、
9，4，1，6，4，8，5，7，2
のように重複させてみると
p[9 - 1] = 1;
p[4 - 1] = 1;
p[1 - 1] = 1;
p[6 - 1] = 1;
p[4 - 1] = 1;
p[8 - 1] = 1;
p[5 - 1] = 1;
p[7 - 1] = 1;
p[2 - 1] = 1;
すなわち
p[8] = 1;
p[3] = 1;
p[1] = 1;
p[5] = 1;
p[3] = 1;
p[7] = 1;
p[4] = 1;
p[6] = 1;
p[1] = 1;
となりp[2]だけが取り残され、
p[2] = 0; からp[2] = 1;に変更されずに初期化ときのp[2] = 0; のままです。
for (int k = 0; k < n; k++) { //ブロック検査
if (p[2] == 0) {
cout << "×";
kr = 0;
sng = 0;
goto tobi1;
}
}
の検査に通らずgoto tobi1;によって次の数字に変わってしまうわけです。
では、次の課題です。
を見ればわかりますが、このままでは使いものになりません。
あらゆる場合を生成させるプログラムになっていて、
ここから数字を抜いて（空欄にして）もおそらく良い数独はできないと考えられます。
シード値を現在時刻から取得して、疑似乱数が毎回異なるように変更してください。
・
・
・
第５話へ 第７話へ
トップ