第15講 リスト法による魔方陣末項確定法自動生成ソフトの高速化
第２話 魔方陣自動生成におけるリスト構造解析の簡単さについて

数独の場合、空白の全セルについてセルのリスト分析をすること、
すなわち、全体構造解析は大変困難です。
しかし、数独を解くソフトについても、
数独自動生成ソフトにおいても、
絶対に欠かすことのできない作業です。
そして、数独を解く場合どんどん空欄が減っていき、
空欄を埋める度にセルのリスト構造が変化します。
全体構造解析とともに、
1つのセルに入力されたことによって影響を受けるセルのリスト解析、
部分構造解析も必要になります。
全体構造解析でさえ、
頭が爆発そうなのに、
部分構造解析はそれを遙かに凌駕する困難な難問です。

数独の全体構造解析と部分構造解析が難しい決定的な理由は、
セル毎にリストが違うため、
全セルについて構造解析をしなければならない点です。
セル毎の構造解析によって、
それぞれのセルのリスト数とリスト（候補数字）が解析されなければなりません。
リスト構造を表す配列は、３次元配列となります。
例えば、セル（0,0）

ls(0,0,0)=1
ls(0,0,1)=4
ls(0,0,2)=6
と解析されます。
３次元配列の最初の２つの添え字がセルを表す座標で、
３つ目の添え字は、そのセルのリストの順番を表します。
ただし、０番目から数えますので2はリスト数３から１を引いたものとなります。
同様にセル（6,2）

を見ておきますと
ls(6,2,0)=1
ls(6,2,1)=3
ls(6,2,2)=5
ls(6,2,3)=9
リストが１，３，５，９でリスト数が４です。



ところが、幸いなことに魔方陣の場合は、
全体構造解析も部分構造解析も大変シンプルです。
全体構造解析は、
初めすべて空欄ですから、
すべてのセルが同じリスト構造を持ちます。
しがたって、用意する配列は１次元配列で良いのです。
４次元魔方陣の全体構造解析は、
ls(0)=1
ls(1)=2
ls(2)=3
　　・
　　・
　　・
ls(15)=16
これはFor文で簡単に実現できます。
また、部分構造解析も大変簡単です。

空欄セルのリストは
１，２，３，・・・，１５，１６
から、すでに入っている
１，２，１５，１６を外した、
３，４，５，・・・，１３，１４
がリストとなります。
空欄に１つ入る度の部分構造解析は、
大変単純で、今セルに入った数字をリストから外すだけです。
ls(0)=3
ls(1)=4
ls(2)=5
　　・
　　・
　　・
ls(10)=13
ls(11)=14


リスト法のメリットは、重複チェックが不要になる点です。
ですから、
　　　　If g > 0 Then
　　　　　　For j = 0 To g - 1
　　　　　　　　ji = iz(j)
　　　　　　　　jj = jz(j)
　　　　　　　　If x(ji, jj) = x(gi, gj) Then
　　　　　　　　　　h = 0
　　　　　　　　　　Exit For
　　　　　　　　End If
　　　　　　Next
　　　　End If
などがいらなくなるのです。
いちいち重複検査をしないわけですから、
当然生成速度の向上が期待できるわけです。
いよいよプログラミングに挑戦して頂きますが、
いきなりでは難しいと思いますので次話で考え方を説明します。

第１話へ　第３話へ

初心者のためのc++ vc++ c言語 入門 基礎から応用までへ
初心者のための excel 2007 2010 2013 vba マクロ 入門 基礎から応用まで
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
vb講義トップへ
ＶＢ講義基礎へ
専門用語なしのC++入門へ
専門用語なしのJava入門へ
専門用語なしのVBA入門

数独のページ
魔方陣のページ
数学研究室に戻る
本サイトトップへ