第13講 プロシージャの再帰的使用による数独解答自動生成
第３話 ブロックの重複をチェックするには？
列や行の重複チェックと比べると、
ブロックの重複チェックはかなり難しいですね。
理由の1つは、列や行が1次元であるのに対して、
ブロックは２次元だからです。
さらに、難しくしている理由が２つあります。
その１つ目は、
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
列と行のチェックはすでにしてあるので、
チェックの重複を避けなければならないということです。
良問で難問である数独（問題）を生成するためには、
膨大な計算量を必要とします。
かなりの試行錯誤をしないと、
良問にして難問である数独の生成は難しいのです。
いえ、良問と難問という条件を削ったとしても、
難しいというのが正解です。
数独は
① 答え（解）が存在する
② 別解が存在しない
という矛盾する２つの要求を満たさなければならないからです。
適当にヒントを配置したのでは、
ほとんどの場合、
解なしか複数答えがあるのかどちらかになってしまいます。
ですから、膨大な計算量になりますから、
重複チェックの重複は避けたいのです。
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
例えば、中央のセルと型と重複していないかを調べる訳ですが、
２と４の位置にあるセルとの重複検査はすべに済んでいるので、
１と３の位置にあるセルのみと比較することになります。
ここで皆さんは、えっ？
７と９はどうなのと疑問を抱いたのではありませんか。
その検査は不要というか、
するとおかしなことになってしまいます。
gはセル番号でしたから、番号を１つずらしておきましょう。
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
数字は、０→１→２→３→・・・の順に埋まっていきます。
ですから、セル
| 4 |
の位置にあるときは、
数字は０，１，２，４の位置のセルしか埋まっていないのです。
ですから数字は、例えば次のように埋まっている訳です。
| 1 | 2 | 3 |
| 4 | 1 | |
（セル番号とセルの中に入っている数字を明確に区別しないと
訳がわからなくなります。
今度の表記は、セルに入っている数字です。）
セル番号０とセル番号４には同じ数字１が入っているので、
この場合には、
次のセル＝セル番号５のセルには進まないようにしなければならないです。
すなわち、
If h = 1 Then
・・・
・・・
h = 0
・・・
・・・
End If
If h = 1 Then
If g + 1 < n * n Then
Call f(g + 1, cn, n, x())
・・・
・・・
として、次のセルに進まないようにしてやらなければならないのです。
さて、
| 1 | 2 | 3 |
| 4 | 1 | |
という状態ですらから
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
重複検査は、０と２の位置のセルのみと行えば良いことがお分かりでしょうか。
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
さて、６の位置にあるときはどこと
重複チェックを行えば良いですか。
初心者のためのc++ vc++ c言語 入門 基礎から応用までへ
初心者のための excel 2007 2010 2013 vba マクロ 入門 基礎から応用まで
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座へ
vb講義トップへ
ＶＢ講義基礎へ
専門用語なしのC++入門へ
専門用語なしのJava入門へ
専門用語なしのVBA入門
数独のページ
魔方陣のページ
数学研究室に戻る
本サイトトップへ
