第３２講　数独(ナンバープレイス)問題解決ソフトVer.3の制作
（数独(ナンバープレイス)問題作成ソフトに挑戦する人は☆☆)

第１話　本講の改善目標
Ver.2の完成により、Ver.1が苦手であった問題をかなり早く解けるようになりました。
しかし、Ver.2には２つの問題があります。
１つは、入力順の構築をすべての空欄セルについて行っていますが、
実は、すべてのセルについて決定する必要はありません。
次に入力する１つのセルだけを決定すればよいのです。
なぜ１つだけでよいのか。
それはもう一つの問題と関係しています。
Ver.2では、ソフトが問題を解決するためにセルに数字を入れたことによって、
問題構造が変わることを考慮に入れていません。
問題構造解析によって、入力順が決定されているのですから、
問題構造が変わる度に入力順は変わっていきます。
問題構造解析は、本当はセルに数字を入れる度に行わなければなりません。
そして、問題構造解析は数字を入れたことによって影響を受けるセルのみに対して行う問題部分構造解析でよいのです。
c++
ところが、この部分構造解析が極めて難しいのです。
従いまして、問題部分構造解析はVer.4以降の課題として、Ver.3では問題全体構造解析を繰り返すことにします。

さて、数字を入れる度に問題構造が変わるとはどういうことでしょうか。
上の場合、リスト最大候補数は、

* 6 5 3 5 4 * 5 5
3 5 * * 5 * 5 4 5
5 7 6 5 6 5 8 6 6
5 7 6 3 6 * 5 6 5
4 7 * 1 4 4 5 6 *
4 5 4 3 * * 5 * 4
3 4 4 * 4 3 5 * *
* 7 5 5 5 4 5 5 6
* 6 4 * 5 4 5 5 5

であり、それに基づく入力順の構築は、

* 48 21 1 22 7 * 23 24
2 25 * * 26 * 27 8 28
29 59 49 30 50 31 63 51 52
32 60 53 3 54 * 33 55 34
9 61 * 0 10 11 35 56 *
12 36 13 4 * * 37 * 14
5 15 16 * 17 6 38 * *
* 62 39 40 41 18 42 43 57
* 58 19 * 44 20 45 46 47

でした。そして、

3

のリストは

座標（０，３）のリスト  １ ２ ３ ４ ５ ６ ７ ８ ９
× × ○ × ○ × ○ × ×

であり、

1

のリストは

座標（３，４）のリスト  １ ２ ３ ４ ５ ６ ７ ８ ９
× × × × × × ○ × ×

でした。そこで、７を入れてみます。

1 4
3 9 6
5
6 7 3
1 4 8
2 3 6
5
4 8

すると、

3

のリストが変わり、

座標（０，３）のリスト  １ ２ ３ ４ ５ ６ ７ ８ ９
× × ○ × ○ × × × ×

リスト最大候補数も

2

と変わります。
このように７を入れたことによってリスト構造が変化するわけです。
7を入れたことによって全体がどう変わるかといいますと、

* 6 5 3 5 4 * 5 5
3 5 * * 5 * 5 4 5
5 7 6 5 6 5 8 6 6
5 7 6 3 6 * 5 6 5
4 7 * 1 4 4 5 6 *
4 5 4 3 * * 5 * 4
3 4 4 * 4 3 5 * *
* 7 5 5 5 4 5 5 6
* 6 4 * 5 4 5 5 5

から

* 6 5 2 5 4 * 5 5
3 5 * * 5 * 5 4 5
5 7 6 4 6 5 8 6 6
5 7 6 2 5 * 5 6 5
3 6 * * 3 3 4 5 *
4 5 4 2 * * 5 * 4
3 4 4 * 4 3 5 * *
* 7 5 4 5 4 5 5 6
* 6 4 * 5 4 5 5 5

へと様相を一変させます。従いまして、入力順も大きく変わり、

* 48 21 1 22 7 * 23 24
2 25 * * 26 * 27 8 28
29 59 49 30 50 31 63 51 52
32 60 53 3 54 * 33 55 34
9 61 * 0 10 11 35 56 *
12 36 13 4 * * 37 * 14
5 15 16 * 17 6 38 * *
* 62 39 40 41 18 42 43 57
* 58 19 * 44 20 45 46 47


から

* 49 23 0 24 9 * 25 26
3 27 * * 28 * 29 10 30
31 59 50 11 51 32 63 52 53
33 60 54 1 34 * 35 55 36
4 56 * * 5 6 12 37 *
13 38 14 2 * * 39 * 15
7 16 17 * 18 8 40 * *
* 61 41 19 42 20 43 44 57
* 58 21 * 45 22 46 47 48

となります。例えば、入力順10は５へ、35は12へと大きく順位を上げています。
35は1つ入れた影響を差し引いても、３５－１２－１＝２２位も順位を上昇させています。



第31講第13話へ　第２話へ


戻る

VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）