数独（ナンプレ）を解くアルゴリズムの要点とパフォーマンスの検証№1

最終更新日：2017-11-26

数独（ナンプレ）を解くアルゴリズムの要点とパフォーマンスの検証№1

数独（ナンプレ）を解くアルゴリズムを例に、アルゴリズムの要点と、それによるパフォーマンスを検証します、

数独（ナンプレ）を解くVBAに挑戦

数独は、一般に「ナンバープレース（ナンプレ）」と呼ばれ、外国では「sudoku」と呼ばれているようです、この数独をExcelマクロVBAで解いてみようと言う事です。解き方は、とにかく片っ端から数字を当てはめていくという、なんとも芸の無い方法です。

ここでは、とにかく全ての数字を当てはめていくという、いわば全数チェックでの解法を使いました。

考察するまでもなく、かなりの無駄がある事は明白です。

しかし、このアルゴリズムは、間違いなく解を得る事ができ、かつ、そのアルゴリズムは非常に簡単なものです。

言わば、より良いアルゴリズムが不明な場合に、最期の手段といえるものでもあります。

さらに、このアルゴリズムは、絶対に不可欠なものでもあります。

少なくとも、数独を解く場合には、最期に複数候補のマスが複数残ってしまった場合には、

この全数チェックを行う事は必然であり、最も確実な方法でもあります。

とはいえ、最初から全数チェックは、いかにも芸がなく、PCのパフォーマンスに全てを委ねてしまっています。

この全数チェックの試行回数が膨大であり、間違いなく無駄だと感じます。

もっと効率的なアルゴリズムがあるはずです。

数独を解く場合のセオリーはいくつかあるようです。

しかし、ここでは、そのような一般的な数独を解くセオリー等は考慮せず、

あくまで、プログラミングのテクニックで、より有効なアルゴリズムを探してみたいと思います。

各マスに入れられる数値は1～9の全てではなく、縦・横・枠内に重複しない数値のみ入れられる訳です。

概ね、１つのマスに入れられる数値の種類は、2～6程度になります。

もちろん、初級問題なら、いきなり１つしか入れられないマスもあったり、

上級問題なら、7つも入れられる可能性のあるマスも存在はするでしょうが・・・

では、全数チェックすると言う事は、その組み合わせは、

入れる事が可能な候補数値の掛け算になってしまいます。

6×6×5×5×4×4×3×3×2×2

10個のマスでも、とんでもない組み合わせ数になってしまいます。

でも、先のアルゴリズムは、本当に全数チェックをしているのでしょうか？

そんな事はありませんね、全数チェックしていたら、とても短時間で解を求めることなど無理ですから。

数値を仮置きし、次のマスに進む、これ繰り返していくと、どこかで破綻します。

つまり、1～9のいずれの数値も入れられなくなってしまう状態が発生します。

その場合は、手前に戻って、数値を入れ直します。

つまり、破綻した時点で、それ以降はチェックしていないのです。

数独（ナンプレ）を解くVBAに挑戦


  
    
      Option Explicit


      Private tryCnt As Long


Sub main()

　　Debug.Print Timer

　　Dim SuAry(1 To 9, 1 To 9) As Integer

　　Dim i1 As Integer

　　Dim i2 As Integer

　　

      　　tryCnt = 0

　　Erase SuAry

　　For i1 = 1 To 9

　　　　For i2 = 1 To 9

　　　　　　If Cells(i1, i2) = "" Then

　　　　　　　　Cells(i1, i2).Font.Color = vbBlue

　　　　　　Else

　　　　　　　　SuAry(i1, i2) = Cells(i1, i2)

　　　　　　End If

　　　　Next

　　Next

　　

　　Call trySu(SuAry)

　　

　　Range("A1:I9").Value = SuAry

　　Debug.Print Timer

　　

　　If getBlank(SuAry(), i1, i2) = False Then

      　　　　MsgBox "解読成功" & vbLf & tryCnt

　　Else

　　　　MsgBox "あれれ・・・"

　　End If

End Sub


Function trySu(ByRef SuAry() As Integer) As Boolean

　　Dim i1 As Integer

　　Dim i2 As Integer

　　Dim su As Integer

　　If getBlank(SuAry(), i1, i2) = False Then

　　　　trySu = True

　　　　Exit Function

　　End If

　　For su = 1 To 9

　　　　If chkSu(SuAry(), i1, i2, su) = True Then

　　　　　　SuAry(i1, i2) = su

      　　　　　　tryCnt = tryCnt + 1

　　　　　　Cells(i1, i2) = su

　　　　　　If trySu(SuAry) = True Then

　　　　　　　　trySu = True

　　　　　　　　Exit Function

　　　　　　End If

　　　　End If

　　Next

　　SuAry(i1, i2) = 0

　　Cells(i1, i2) = ""

　　DoEvents

　　trySu = False

End Function


Function getBlank(ByRef SuAry() As Integer, ByRef i1 As Integer, ByRef i2 As Integer) As Boolean

　　For i1 = 1 To 9

　　　　For i2 = 1 To 9

　　　　　　If SuAry(i1, i2) = 0 Then

　　　　　　　　getBlank = True

　　　　　　　　Exit Function

　　　　　　End If

　　　　Next

　　Next

　　getBlank = False

End Function


Function chkSu(ByRef SuAry() As Integer, ByVal i1 As Integer, ByVal i2 As Integer, ByVal su As Integer) As Boolean

　　Dim ix1 As Integer

　　Dim ix2 As Integer

　　Dim i1S As Integer

　　Dim i2S As Integer

　　chkSu = False

　　

　　'横をチェック

　　For ix2 = 1 To 9

　　　　If ix2 <> i2 Then

　　　　　　If SuAry(i1, ix2) = su Then

　　　　　　　　chkSu = False

　　　　　　　　Exit Function

　　　　　　End If

　　　　End If

　　Next

　　'縦をチェック

　　For ix1 = 1 To 9

　　　　If ix1 <> i1 Then

　　　　　　If SuAry(ix1, i2) = su Then

　　　　　　　　chkSu = False

　　　　　　　　Exit Function

　　　　　　End If

　　　　End If

　　Next

　　'枠内をチェック

　　i1S = (Int((i1 + 2) / 3) - 1) * 3 + 1

　　i2S = (Int((i2 + 2) / 3) - 1) * 3 + 1

　　For ix1 = i1S To i1S + 2

　　　　For ix2 = i2S To i2S + 2

　　　　　　If ix1 <> i1 Or ix2 <> i2 Then

　　　　　　　　If SuAry(ix1, ix2) = su Then

　　　　　　　　　　chkSu = False

　　　　　　　　　　Exit Function

　　　　　　　　End If

　　　　　　End If

　　　　Next

　　Next

　　chkSu = True

End Function