excel - 使用 VBA 求解九个未知变量方程的蛮力法

Question

尝试求解 the maths puzzle for Vietnamese eight-year-olds 时会出现此方程:a+(13*b/c)+d+(12*e)-f+(g*h/i)=87最近在互联网上疯传。在数学中，这样的方程称为 underdetermined system 。当然，它有多个解决方案，而暴力法似乎是找到所有解决方案的最简单方法。

我有兴趣了解如何使用 VBA 求解方程并在 MS Excel 工作表中呈现解决方案，因为由于缺乏 VBA 编程知识，我无法找到编写此类程序的方法。

我知道 Stack Overflow 上有类似的帖子，例如 this和 this但那里的答案对我没有多大帮助。

这是我的尝试:

Sub Vietnam_Problem()
Dim StartTime As Double

StartTime = Timer
j = 2   'initial value for number of rows
For a = 1 To 9
    For b = 1 To 9
        For c = 1 To 9
            For d = 1 To 9
                For e = 1 To 9
                    For f = 1 To 9
                        For g = 1 To 9
                            For h = 1 To 9
                                For i = 1 To 9
                                If a <> b And a <> c And a <> d And a <> e And a <> f And a <> g And a <> h And a <> i And b <> c And b <> d And b <> e And b <> f And b <> g And b <> h And b <> i And c <> d And c <> e And c <> f And c <> g And c <> h And c <> i And d <> e And d <> f And d <> g And d <> h And d <> i And e <> f And e <> g And e <> h And e <> i And f <> g And f <> h And f <> i And g <> h And g <> i And h <> i And a + (13 * b / c) + d + (12 * e) - f + (g * h / i) = 87 Then
                                Cells(j, 1) = a
                                Cells(j, 2) = b
                                Cells(j, 3) = c
                                Cells(j, 4) = d
                                Cells(j, 5) = e
                                Cells(j, 6) = f
                                Cells(j, 7) = g
                                Cells(j, 8) = h
                                Cells(j, 9) = i
                                j = j + 1
                                End If
                                Next i
                            Next h
                        Next g
                    Next f
                Next e
            Next d
        Next c
    Next b
Next a
Cells(2, 11) = j - 2 'number of solutions
Cells(2, 12) = Round(Timer - StartTime, 2)  'running time of VBA code
End Sub

它似乎可以工作，但它不太好而且很慢。

Answer 1

Anastasiya-Romanova 秀，由于您没有声明变量(a 到 j)，因此您的代码运行时这些变量默认为 Variant 类型。虽然变体非常有用，但不应该在这里使用它们。

我在我的机器上运行了未更改的代码，花了 851 秒才能完成。

由于 VBA 针对长整型进行了优化，只需在代码中添加一行将变量(a 到 j)声明为长整型，即可将我机器上的运行时间缩短至 120 秒。因此，仅使用适当的变量类型，速度就快了七倍!

我在 VBA 中解决这个难题的尝试速度要快得多。事实上，它比本页面迄今为止发布的任何内容都要快(而且短)得多。在我的同一台机器上，它在不到一秒的时间内返回所有 136 个正确的组合。

有很多关于 VBA 太慢的废话(世界、网络，甚至在本页!)。别相信。当然，编译语言可以更快，但很多时候这取决于您对如何处理语言的了解程度。自 20 世纪 70 年代以来，我一直在使用 BASIC 语言进行编程。

这是我为您的问题精心设计的越南谜题的解决方案。请将其放入新的代码模块中:

Option Explicit
Private z As Long, v As Variant

Public Sub Vietnam()
    Dim s As String
    s = "123456789"
    ReDim v(1 To 200, 1 To 9)
    Call FilterPermutations("", s)
    [a1:i200] = v
    End
End Sub

Private Sub FilterPermutations(s1 As String, s2 As String)

    Dim a As Long, b As Long, c As Long, d As Long, e As Long, f As Long, _
        g As Long, h As Long, i As Long, j As Long, m As Long, n As Long

    n = Len(s2)
    If n < 2 Then
        a = Mid$(s1, 1, 1):  b = Mid$(s1, 2, 1):  c = Mid$(s1, 3, 1)
        d = Mid$(s1, 4, 1):  e = Mid$(s1, 5, 1):  f = Mid$(s1, 6, 1)
        g = Mid$(s1, 7, 1):  h = Mid$(s1, 8, 1):  i = s2
        If a + (13 * b / c) + d + (12 * e) - f + (g * h / i) = 87 Then
            z = z + 1
            v(z, 1) = a:  v(z, 2) = b:  v(z, 3) = c
            v(z, 4) = d:  v(z, 5) = e:  v(z, 6) = f
            v(z, 7) = g:  v(z, 8) = h:  v(z, 9) = i
        End If
    Else
        For m = 1 To n
            FilterPermutations s1 + Mid$(s2, m, 1), Left$(s2, m - 1) + Right$(s2, n - m)
        Next
    End If

End Sub

方法#2:

Anastasiya，今天晚些时候，当我有更多时间时，我会尝试解释它。但与此同时，请检查我的下一步尝试。现在它更短，大约只需 1/10 秒即可完成。我现在使用堆的排列算法:

Option Explicit
Private z As Long, v As Variant

Public Sub VietnamHeap()
    Dim a(0 To 8) As Long
    a(0) = 1:  a(1) = 2:  a(2) = 3:  a(3) = 4:  a(4) = 5:  a(5) = 6:  a(6) = 7:  a(7) = 8:  a(8) = 9
    ReDim v(1 To 200, 1 To 9)
    Generate 9, a
    [a1:i200] = v
    End
End Sub

Sub Generate(n As Long, a() As Long)
    Dim t As Long, i As Long
    If n = 1 Then
        If a(0) + (13 * a(1) / a(2)) + a(3) + (12 * a(4)) - a(5) + (a(6) * a(7) / a(8)) = 87 Then
            z = z + 1
            For i = 1 To 9:  v(z, i) = a(i - 1):  Next
        End If
    Else
        For i = 0 To n - 2
            Generate n - 1, a
            If n Mod 2 = 1 Then
                t = a(0):  a(0) = a(n - 1):  a(n - 1) = t
            Else
                t = a(i):  a(i) = a(n - 1):  a(n - 1) = t
            End If
        Next
        Generate n - 1, a
    End If
End Sub

方法#3

这是一个更短的版本。谁能想出一个更短的版本或更快的版本？

Const q = 9
Dim z As Long, v(1 To 999, 1 To q)

Public Sub VietnamHeap()
    Dim a(1 To q) As Long
    For z = 1 To q: a(z) = z: Next: z = 0
    Gen q, a
    [a1].Resize(UBound(v), q) = v: End
End Sub

Sub Gen(n As Long, a() As Long)
    Dim i As Long, k As Long, t As Long
    If n > 1 Then
        For i = 1 To n - 1
            Gen n - 1, a
            If n Mod 2 = 1 Then k = 1 Else k = i
            t = a(k): a(k) = a(n): a(n) = t
        Next
        Gen n - 1, a
    Else
        If 87 = a(1) + 13 * a(2) / a(3) + a(4) + 12 * a(5) - a(6) + a(7) * a(8) / a(9) Then z = z + 1: For i = 1 To q: v(z, i) = a(i): Next
    End If
End Sub