第8講 数独の問題を解くプログラムVer(−1)
第2話 Sub hyoujiの改良前半


       If cn = 1 Then Exit Sub

            If g + 1 < n * n * n * n Then
                sakusei (g + 1)
            Else
                cn = 1
                hyouji
                Exit Sub
            End If
の部分の追加および変更の理由は、
数独の問題では解答は1つしかありませんので、
解答が見つかればそれ以上の探索は必要ありませんので、
探索を打ち切らせるためです。
(正しい数独の問題は、解答が1つですが、
本当にその問題が正しい問題なのか、つまり答えが1つしかないのかを
検討させたい場合はこの追加および変更は必要ありません。)

さて、
        If mah(i, j) > 0 Then
           If g + 1 < hs Then
               sakusei (g + 1)
               Exit Sub
           Else
               cn = 1
               hyouji
               Exit Sub
           End If
         End If

では何をしているのでしょうか。
この説明は、次話にまわしたいと思います。

For l = 0 To j - 1 が For l = 0 To 8
および
For l = 0 To i - 1 が For l = 0 To 8
に変わった理由は、数独プログラム改良例では

0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53
54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80

セル0番から順番に数字を入れていきました。
行について調べるときは、自分より前のところに重複がないか調べれば良かったのです。
自分の後のところにはまだ数字は入っていなくて空欄なので自分より後ろは調べる必要がなかったのです。
列も同様です。

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

ところが数独の問題では、いくつかのセルに最初から数字が入っています。
すべての問題を解かせるプログラムですから、
数字はどこに入っているかは事前にはわかりません。

0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53
54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80

したがって、数独プログラム改良例のときにはセル4について調べるときにはセル
についてのみ調べれば良かったのですが、数独の問題を解く方では、、
セル5,6,7,8にも数字が入っている可能性があるので、結局行全体を調べなければならないのです。

列についても同様です。

            If ia > 0 Then
               For l = 0 To 2
                   For m = 0 To 2
                       If (j - ja + m) <> j And (i - ia + l) <> i Then
                           If mah(i, j) = mah(i - ia + l, j - ja + m) Then GoTo owari
                       End If
                   Next
               Next
            End If
の部分の変更も

0 1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53
54 55 56 57 58 59 60 61 62
63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80

数独プログラム改良例では順番に入っていくので
例えば、セル40番について調べるときは
自分より前の30313239
についてのみ調べれば良かったのです。だから、
            If ia > 0 Then
               For l = 0 To ia - 1
                   For m = 0 To n - 1
                       If (j - ja + m) <> j And (i - ia + l) <> i Then
                           If mah(i, j) = mah(i - ia + l, j - ja + m) Then GoTo owari
                       End If
                   Next
               Next
            End If
となっていたのですが、数独の問題を解くプログラムでは最初から41,48,49,50
にも数字が入っているという可能性があるのでピンクの小ブロック内を全部を調べなければならないので、
            If ia > 0 Then
               For l = 0 To 2
                   For m = 0 To 2
                       If (j - ja + m) <> j And (i - ia + l) <> i Then
                           If mah(i, j) = mah(i - ia + l, j - ja + m) Then GoTo owari
                       End If
                   Next
               Next
            End
となっているのです。

第1話へ 第3話へ

VB入門講義応用編トップへ

VB入門講義トップへ