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


第2話 なぜ問題全体構造解析とそれに基づく入力順の構築が必要なのか。

リストする意義は明らかです。
c++

* 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

例えば、セル入門なら7のみを試せばよいのです。
また、初心者なら3,5,7の場合のみについて調べればよいのです。

では入力順構築の意味は何でしょうか。

* * *

例えば、縦横ブロックの条件から
1番目のセルは1,3,4,5,6の5通りの可能性があり、
2番目のセルは2,7,8の3通り可能性があり、
3番目のセルには9の可能性があるとします。
正順に試していく場合は


1 * *



1 2 *


1 2 9


1 7 *


1 7 9


1 8 *


1 8 *


1 8 9





3 * *



3 2 *


3 2 9


3 7 *


3 7 9


3 8 *


3 8 *


3 8 9




4 * *



4 2 *


4 2 9


4 7 *


4 7 9


4 8 *


4 8 *


4 8 9





5 * *



5 2 *


5 2 9


5 7 *


5 7 9


5 8 *


5 8 *


5 8 9




6 * *



6 2 *


6 2 9


6 7 *


6 7 9


6 8 *


6 8 *


6 8 9




45通りの場合を調べなければなりません。
それに対して逆順で調べていく場合は

* * 9



* 2 9


1 2 9


3 2 9


4 2 9


5 2 9


6 2 9




* * 9



* 7 9


1 7 9


3 7 9


4 7 9


5 7 9


6 7 9




* * 9



* 8 9


1 8 9


3 8 9


4 8 9


5 8 9


6 8 9




の21通りで済みます。順番を変更するだけで、45通りから21通りに場合の数が減少するのです。
たった3つの空欄でこれだけ大きな影響があります。
数独超上級の場合60個程度空欄がありますので、
その違いは段違いになると言うことはお分かりかと思います。

現在の高校は、学科があり、選択があり、習熟がありと大変複雑になっています。
ですから、時間割を組むというは大変なパズルです。
場合によっては、1カ所変更しようとすると100駒間程度動いてしまうこともあります。
ですから難解なパズルなのです。
この時間割を組むときの鉄則は、条件の厳しい駒から入れていくです。
条件のきつい体育(同時に2展開できない、男女別の2クラス4選択など厳しい条件)や家庭科(調理実習の関係で4,5限のみ)から入れ、
次に条件がきつい非常勤講師の駒(曜日と時間が指定されている)を入れていくといった順で入れていきます。
条件の緩い駒は、自由に動かせるのに対して条件がきつい駒は動かすことが出来ないからです。
最初に条件の緩い駒で、埋め尽くすと自由度がなくなり条件のきつい駒は入らなくなります。
難問を解くコツは、条件の厳しいところからやっていくことです。

前掲の

* 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

は数字が少ないほど自由度がありません。
ですから数字の小さい方から、攻めていくと効率的に攻略できるのです。
条件の厳しいところから、クリアして行っているわけです。

では、問題全体構造解析と問題全体構造解析に基づく入力順の構築はどうしたらよいでしょうか。
両方とも難問ですが、考えてみましょう。




第1話へ 第3話へ

戻る

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