第１０講 数独の問題を解くプログラムＶｅｒ０
第７話　まとめ
ここでは問題解析のまとめをして、Ｓｕｂ sakuseiの変更点について説明して第１０講の締めとします。
For i3 = 0 To 8
　　If i2 <> i3 And mah(i1, i3) > 0 Then dhs(i1, i2, mah(i1, i3) - 1) = 1　　　　　　　　　 ・・・①
Next
For i3 = 0 To 8
　　If i1 <> i3 And mah(i3, i2) > 0 Then dhs(i1, i2, mah(i3, i2) - 1) = 1　　　　　　　　　 ・・・②　　　　　
Next
i1s = Int(i1 / 3)
i2s = Int(i2 / 3)
For i3 = 0 To 2
　　For i4 = 0 To 2
　　　　If 3 * i1s + i3 <> i1 And 3 * i2s + i4 <> i2　　＊（実際にはここで改行はなし）
　　　　And mah(3 * i1s + i3, 3 * i2s + i4) > 0 Then ＊（実際にはここで改行はなし）　　・・・③
　　　　dhs(i1, i2, mah(3 * i1s + i3, 3 * i2s + i4) - 1) = 1
　　Next
Next

まずパーツ①によって

**

の入っている行には

*6 ** ** ** *4 ** ** ** **

６，４が入っていることが認識され

i3+1 １ ２ ３ ４ ５ ６ ７ ８ ９
dhs(3,5,i3) × × × ○ × ○ × × ×

となります。そして、パーツ②によってさらに列

*4
**
**
**
5
**
**
**
**

に４，５が入っているという認識が加わり、

i3+1 １ ２ ３ ４ ５ ６ ７ ８ ９
dhs(3,5,i3) × × × ○ ○ ○ × × ×

となります。さらに、パーツ③によって

**

の入っているブロック

** 4 **
1 ** 5
** 8 **

には１，８が入っているという認識が加わり、

i3+1 １ ２ ３ ４ ５ ６ ７ ８ ９
*dhs(3,5,i3) ○ × × ○ ○ ○ × ○ ×

となります。○×を反転させると候補リストになります。

i3+1 １ ２ ３ ４ ５ ６ ７ ８ ９
*候補リスト × ○ ○ × × × ○ × ○


そして、問題解析の最後のパーツ
For i3 = 0 To 8
　　If dhs(i1, i2, i3) = 0 Then
　　　w = cnn(i1, i2)
　　　dhs1(i1, i2, w) = i3 + 1
　　　cnn(i1, i2) = cnn(i1, i2) + 1
　 End If
Next
によって、座標（３，５）のセルの候補リスト

i3 ０ １ ２ ３ ４ ５ ６ ７ ８
dhs1(3,5,i3) ２ ３ ７ ９ ０ ０ ０ ０ ０

ができあがります。cnn(3, 5)は、実際に入れることのできる数字の最大個数
（これは結局2つ上の表の○の個数）で４です。

実際には、

i3+1 １ ２ ３ ４ ５ ６ ７ ８ ９
*dhs(3,5,i3) ○ × × ○ ○ ○ × ○ ×

は、プログラム上では

i3 ０ １ ２ ３ ４ ５ ６ ７ ８
*dhs(3,5,i3) １ ０ ０ １ １ １ ０ １ ０

であることに注意して、トレースしてみましょう。
まずi3=0のとき、dhs(3,5,0)=１で条件dhs(i1, i2, i3) = 0をクリアできず、
　 If dhs(i1, i2, i3) = 0 Then
　　　w = cnn(i1, i2)
　　　dhs1(i1, i2, w) = i3 + 1
　　　cnn(i1, i2) = cnn(i1, i2) + 1
　 End If
は実行されません。次にi3=1となり、dhs(3,5,1)=0で条件dhs(i1, i2, i3) = 0をクリアし、
初期化によってcnn(i1, i2)は０だったので、w = 0となります。よって、次の２行で、
dhs1(3, 5, 0) = 2（なぜならi3+1=1+1=2)，cnn(i1, i2) = 1となります。
3回目のループでi3=2となり、dhs(3,5,2)=0で条件dhs(i1, i2, i3) = 0をクリアし、ｗ = 1，dhs1(3, 5, 1) = 3，cnn(i1, i2) = 2
以下
i3=3でdhs(3,5,3)=1で条件dhs(i1, i2, i3) = 0をクリアできずＩｆ文は実行されません。
i3=4でdhs(3,5,4)=1で条件dhs(i1, i2, i3) = 0をクリアできずＩｆ文は実行されません。
i3=5でdhs(3,5,5)=1で条件dhs(i1, i2, i3) = 0をクリアできずＩｆ文は実行されません。
i3=6でdhs(3,5,6)=０で条件dhs(i1, i2, i3) = 0をクリアし、Ｉｆ文が実行され
　　　　w = 2，dhs1(3, 5, 2) = 7，cnn(i1, i2) = 3
i3=7でdhs(3,5,7)=1で条件dhs(i1, i2, i3) = 0をクリアできずＩｆ文は実行されません。
i3=8でdhs(3,5,6)=０で条件dhs(i1, i2, i3) = 0をクリアし、Ｉｆ文が実行され
　　　　w = 3，dhs1(3, 5, 3) = 9，cnn(i1, i2) = 4
のように処理され、最終的に

i3 ０ １ ２ ３ ４ ５ ６ ７ ８
dhs1(3,5,i3) ２ ３ ７ ９ ０ ０ ０ ０ ０

cnn(i1, i2) = 4となるのです。


さて、Ｓｕｂ sakuseiの変更点の意味は何でしょう。
Sub sakusei(g As Integer)
　　　　　　　　　　　・
　　　　　　　　　　　・
　　　　　　　　　　　・　
　　mx = cnn(i, j)
　　For k = 0 To mx - 1
　　　　mah(i, j) = dhs1(i, j, k)
　　　　　　　　　　・
　　　　　　　　　　・
　　　　　　　　　　・
End Sub

Ver（－１）では
For k = 1 To 9　　　　　　　　（n*nとなっていますがｎ＝３ですので、実際にはn*nは９です。）
　　mah(i, j) = k
でそれぞれのセルに１から９までの数字を入れていました。
Ver０では、問題解析をした結果、座標（３，５）のセルには２，３，７，９しか入れられないことがわかっています。
したがって、１，４，５，６，８の試行はする必要がないのです。
mx = cnn(i, j)
For k = 0 To mx - 1
　　mah(i, j) = dhs1(i, j, k)

現在座標（３，５）のセルにいて、mx = cnn(3, 5) = 4です。したがって、mx - 1=３なので、
Ｆｏｒ文で試行されるのは

k ０ １ ２ ３
dhs1(3,5,k) ２ ３ ７ ９

の部分だけで、２，３，７，９だけが試行されるわけです。
Ver（－１）では１，４，５，６，８も試行されていたので、Ver０でかなり無駄が排除され効率的になっていることがわかります。


第６話へ　第11講第１話へ
VB入門講義応用編トップへ

VB入門講義トップへ