第13章 様々な魔方陣の作成および自動生成
第14話 １列数独の構造解析
１列数独を構造解析するプログラム例
マルチスレッド版数独自動生成ソフトC++コードを題材とする超初心者のためのVisual Studio C++講義
第13章 様々な魔方陣の作成および自動生成
第14話 １列数独の構造解析
１列数独を構造解析するプログラム例
#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;
}
}
//候補数字数を９で初期化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mx[i][j] = 9;
}
}
//データ入力
a[0][0] = 2;
a[0][4] = 8;
a[0][8] = 9;
a[3][0] = 6;
a[6][0] = 5;
全体構造解析関数();
//各空欄候補数字表
for (int i = 0; i < n; i++) {
if (a[0][i] == 0) {
for (int j = 0; j < mx[0][j]; j++) {
cout << "s[0][" << i << "][" << j << "] = " << s[0][i][j] << endl;
}
}
cout << endl;
}
for (int i = 0; i < n; i++) {
if (a[i][0] == 0) {
for (int j = 0; j < mx[j][0]; j++) {
cout << "s[" << i << "][0][" << j << "] = " << s[i][0][j] << endl;
}
}
cout << endl;
}
while (!_kbhit());//待機させるための命令
return(0);
}
void 全体構造解析関数() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 0) {
for (int k = 0; k < n; k++) {
s[i][j][k] = k + 1;//空欄のすべてに１～９までをリストする
}
}
}
}
for (int i = 0; i < n; i++) {
if (a[0][i] == 0) {
for (int j = 0; j < n; j++) {
if (a[0][j] > 0) {
int k = 0;
while (k < mx[0][i]) {
if (s[0][i][k] == a[0][j]) {
mx[0][i]--;
s[0][i][k] = s[0][i][mx[0][i]];
}
else {
k++;
}
}
}
}
}
}
for (int i = 0; i < n; i++) {
if (a[i][0] == 0) {
for (int j = 0; j < n; j++) {
if (a[j][0] > 0) {
int k = 0;
while (k < mx[i][0]) {
if (s[i][0][k] == a[j][0]) {
mx[i][0]--;
s[i][0][k] = s[i][0][mx[i][0]];
}
else {
k++;
}
}
}
}
}
}
}
実行結果
実行結果については解説が必要です。
１行数独のときと同じで１列数独でも候補数字群が同じになります。
パズルの絶対条件である答が一つのいう条件を
１行数独・１列数独では満たしません。
全行・全列・全ブロックがそろうときに唯一解になりますし、
理詰めで解ける数独になります。
ですから、１列数独という名称は仮のもので、
１行や１列や１ブロックではパズルの絶対条件である答が１つであるを満たさないのです。
全体構造解析をいきなりやったのでは４次元繰り返し処理または５次元繰り返し処理になり、
これは初心者では当然無理な課題です。
最終的には全体構造解析をしなければならないにしても、
全体構造解析とは部分構造解析の総和です。
部分構造解析とは１つのセルに数字を入れたときに影響を与えるセルについて解析する事を指しています。
問題を作る過程で同じ行または同じ列または同じブロックで数字の重複が起きれば、
当然数独は解なしになり問題は成立しません。
ですから、１つ数字を入れるごとに影響与える部分について解析するのが部分構造解析です。
問題作る過程や問題を作る過程で同じ行または同じ列または同じブロックで数字の重複が起きないようにするには、
数字を入れる度に構造解析すなわち部分構造解析をしていけばよいのです。
なぜなら、重複が起きれば候補数字数0という現象がおきます。
部分構造解析をやって候補数字数が0は問題制作途中で数字の重複が起きていることを教えてくれます。
候補数字数 = mx[i][j]が0になってしまえば当然問題は解のない問題になります。
部分構造解析をやってmx[i][j]が0の時点で今いれた数字は入れられないことがわかります。
部分構造解析は、問題を作る過程でも必要ですが、
問題を解いていく過程でも常に部分構造解析をしなけばなりなりません。
工夫して４次元繰り返し処理に落とすことができたとしても、
実際には数字を入れる度に構造が変わっていきますので、
時間を考慮に入れれば実際上は５次元繰り返し処理になります。
５次元動的繰り返しになるわけですが、
動的（時間とともに変わるという意味）処理については、
毎回部分構造解析をやっておけばクリアできるのです。
も一つ
について説明しなけばならないことがあります。
先生同じものが並んでいるではありませんか。
ところが何も問題ないのです。
構造解析型の最大の売りは
int mx[n][n];//各空欄の候補数字数
にあります。
そして、このプログラムではデータ同士の交換を行っていますが、
デーは一度も消滅させていないのです。
for (int i = 0; i < n; i++) {
if (a[i][0] == 0) {
for (int j = 0; j < n; j++) {
if (a[j][0] > 0) {
int k = 0;
while (k < mx[i][0]) {
if (s[i][0][k] == a[j][0]) {
mx[i][0]--;
s[i][0][k] = s[i][0][mx[i][0]];
}
else {
k++;
}
}
}
}
}
}
mx[i][0]--;
に注目してください。
でどうして問題がないかと申しますと、
このときmx[8][0]は5なのです。
ですから、s[8][0][6] = 7 があっても何の影響もないのです。
黄色を解析しているときに何が起きているかと申しますと、
s[1][0]={1,3,4,5,6,7,8,9,2}
すなわち、{1,2,3,4,5,6,7,8,9}→{1,3,4,5,6,7,8,9,2}
２と９を交換したのです。
そして、mx[8][0]はmx[i][0]--;によって一つ減らされてmx[8][0] = 8
となっているのです。実際上は{1,3,4,5,6,7,8,9,2}は{1,3,4,5,6,7,8,9}と同じなのです。
やっていることはデータの交換であってデータを消滅させているわけではないのです。
データを残していくことは再帰で数独を自動生成するときには絶対に必要なことなのです。
上手くいかないときには再帰は深いところから浅いところまで戻ってやり直すからです。
データを消滅させたらやり直しはできません。
急速潜航・急速浮上を繰り返しながら試行錯誤をやるのが再帰なのです。
上手くいけば潜航して、失敗すれば浮上してやり直すそれが再帰です。
説明を読んでもよく分からなかった点は当然あるでしょう。
人はわからいときに「ぜんぜんわからなかった」と思う生き物です。
ですが、そんなことは絶対にありません。
分かった部分もあるのにそれを自覚できないから「ぜんぜんわからなかった」という誤った考えを抱くのです。
私が保証します。
繰り返し読み自分でコードを工夫していけば必ず、腑に落ちる瞬間があるものです。
さて、次話への課題です。
について構造解析をやってください。
つまり、１ブロック数独です。
第13章第13話へ 第13章15話へ
本講義トップへ