VBAで再帰を使ったバックトラッキング

1から5までの整数を1度ずつ使って5桁の整数を作るとき、何通りの整数が作れるか？

高校数学の基本問題である。一瞬で解ける簡単な問題だ。

しかし、それを全て書き出せと言われてたらどうだろう。かなり面倒な作業になる。こういう作業はコンピュータに任せるのがいい。

そこで、ExcelのVBAを利用して作ってみようと考えた人もいるはずだ。あいにくVBAにはPythonのpermutationsのような便利な関数は用意されていない。だから、自分でコードを書かなければならない。

もちろん、順列を書き出すコードはインターネットで検索すれば簡単に見つかる。幾人ものレビューによって洗練されたコードもある。既存のアルゴリズムを自分で書くのは、いわゆる「車輪の再発明」だからと忌避する人もいる。だが、それは仕事でコードを書く時の話だ。プログラミングを学ぶのが目的なら、自分で書くべきなのだ。

というわけで、順列を書き出すためのコードを書いた。

Option Explicit

'-----------------------------------------------------------
' 再帰を使ったバックトラッキング
'
' 1-5の数字を5つ使った数の順列を全て書き出す
'
'-----------------------------------------------------------
' (Tips)
' 1-5の数字を3つ使った数の順列を書き出したい場合は、
' 配列を (1 To 3) にすればいい
'-----------------------------------------------------------


' 数字格納用
Private answerArr(1 To 5) As Long

' 配列初期値
Private Const INIT_NUM As Long = 0

' 候補数字の最大値
Private Const MAX_CANDIDATE As Long = 5


Private Sub Main()

    Dim i As Long
    
    ' 配列初期化
    For i = LBound(answerArr) To UBound(answerArr)
        answerArr(i) = INIT_NUM
    Next
    
    Call BackTracking(LBound(answerArr))
    
    Debug.Print "FINISH"
End Sub


Private Sub BackTracking(currentCol As Long)

    Dim i As Long
    
    ' 候補数字
    Dim candidateNum As Long
    ' 既に使ったかフラグ
    Dim alreadyUsed As Boolean
    
    candidateNum = 0
    alreadyUsed = False
    
    ' 候補数字変更ループ
    Do While True
        
        ' 候補数字設定
        candidateNum = candidateNum + 1
        
        ' 候補数字を使い切った場合
        If candidateNum > MAX_CANDIDATE Then
            ' 初期値に戻す
            answerArr(currentCol) = INIT_NUM
            ' 前の列へ
            Exit Sub
        End If
        
        ' 候補数字を既に使っているか調べる
        For i = LBound(answerArr) To currentCol - 1
        
            If answerArr(i) = candidateNum Then
                alreadyUsed = True
                Exit For
            End If
            
        Next
        
        ' 既に使っている場合
        If alreadyUsed Then
        
            ' フラグを降ろして次の候補数字へ
            alreadyUsed = False
            
        ' まだ使っていない場合
        Else
            ' 候補数字で確定させる
            answerArr(currentCol) = candidateNum
            
            ' 最終列の場合
            If currentCol = UBound(answerArr) Then
                ' 書き出す
                Call WriteArr
                
            ' 最終列でない場合
            Else
                ' 次の列へ移動
                Call BackTracking(currentCol + 1)
            End If
            
        End If

    Loop

End Sub

' 配列の中身を書き出す
Private Sub WriteArr()

    Dim tmp As Variant
    Dim str As String
    
    For Each tmp In answerArr
        str = str & tmp
    Next
    
    Debug.Print str
End Sub

バックトラッキングは案外難しい。自力で作れるようになれば初心者脱出と言ってもいいはずだ。

再帰も理解するのがなかなか難しい。参考書などでは「自分自身を呼び出している」と説明されていることもあるが、「自分と全く同じサブルーチンを呼び出している」と考えると理解しやすいかもしれない。

また、再帰が理解できないなら、再帰なしで作ってみるのもいいだろう。きっとプログラミング能力の向上につながるはずだ。実は、再帰は使わないで済むなら、使わない方がいいことも多いのだ。

VBAからプログラミングを始めた人にとっては、なかなか高いハードルかもしれない。バックトラッキングと再帰アルゴリズムについて知りたければ「8クイーン問題」「ナイトツアー」などをアルゴリズムの解説書などで学べばいいだろう。アルゴリズムはやはり書籍の方が学びやすいのだ。