2

我目前正在编写一个程序来解决脑筋急转弯, 屏幕

这是如何工作的:仅使用数字 1-9 一次,制作四个角,每个对角线 = 26 提示使中间 7

无论如何,我的代码基本上从“111111111”开始并计数,每次检查它是否匹配所需的参数。

代码:

    Public Class Main
    Dim count As Integer
    Dim split() As Char
    Dim done As Boolean
    Dim attempts As Integer
    Private Sub IncreaseOne()
        If count < 999999999 Then
            count += 1
        Else
            done = True
        End If
        If CStr(count).Contains("0") Then

            count = CStr(count).Replace("0", "1")
        End If
    End Sub

    Private Sub Reset()
        count = 111111111
        attempts = 0
    End Sub

    Private Sub IntToLbl()
        split = CStr(count).ToCharArray
        lbl1.Text = split(0)
        lbl2.Text = split(1)
        lbl3.Text = split(2)
        lbl4.Text = split(3)
        lbl5.Text = split(4)
        lbl6.Text = split(5)
        lbl7.Text = split(6)
        lbl8.Text = split(7)
        lbl9.Text = split(8)
        lblAttempts.Text = "Attempt: " & attempts
    End Sub
    Private Sub Check()
        attempts += 1
        If split(0) + split(1) + split(7) + Int(8) = 26 And split(0) + split(2) + split(4) + split(6) + split(8) = 26 And split(1) + split(3) + split(4) + split(5) + split(7) = 26 Then
            If CStr(count).Contains("1") And CStr(count).Contains("2") And CStr(count).Contains("3") And CStr(count).Contains("4") _
                And CStr(count).Contains("5") And CStr(count).Contains("6") And CStr(count).Contains("7") And CStr(count).Contains("8") _
                    And CStr(count).Contains("9") Then
                ListBox1.Items.Add("A" & attempts & ":   " & CStr(count))
            End If
        End If
    End Sub

    Private Sub Act()
        While done = False
            IncreaseOne()
            IntToLbl()
            Check()
        End While
        tr.Abort()
    End Sub
    Dim suspended As Boolean = False
    Dim tr As New System.Threading.Thread(AddressOf Act)
    Private Sub Button1_Click(sender As Object, e As EventArgs) Handles btnSolve.Click

        If suspended = True Then
            tr.Resume()
            suspended = False
        Else
            If tr.IsAlive = False Then
                Reset()
                tr.Start()
                CheckForIllegalCrossThreadCalls = False
            Else
                Dim Reply = MsgBox("Thread is running! Stop the thread?", MsgBoxStyle.YesNo, "Error!")
                If Reply = MsgBoxResult.Yes Then
                    tr.Suspend()
                    suspended = True
                End If
            End If
        End If
    End Sub

    Private Sub Main_FormClosing(sender As Object, e As FormClosingEventArgs) Handles  Me.FormClosing
        tr.Abort()
    End Sub

    Private Sub tr2_Tick(sender As Object, e As EventArgs) Handles tr2.Tick
        IncreaseOne()
        IntToLbl()
        Check()
    End Sub
End Class
4

3 回答 3

4

在使用线程之前,您应该 1) 降低算法复杂度和 2) 提高其效率。

1) 对于复杂性,由于数字只能出现一次,所以你有 9 个!= 362.880 次测试,比全扫描少 27.557 倍。
我想那时你已经在大多数计算机上实时了,但也可能有一些组合,你可以在测试所有子组合之前停止测试(expl:如果第一个对角线不是 26,则不需要测试其他项目的排列)。有了这个,您可以减少更多的测试次数。另一种减少案例计数的方法是使用对称性。在这里,1 步或 2 步旋转,水平或垂直翻转都不会影响结果,这使得 X16 的测试计数再次减少。

2)为了提高效率,使用整数数组而不是字符串将为您带来巨大的速度提升。

我做了一个jsfiddle(在javascript中,所以),那只是测试9!元素并使用数组,它会立即给出结果,所以我没有进一步寻找早期停止/对称性。

一种解决方案是,例如:3,2,7,5,9,6,1,4,8
这使得:

3        6
  2    1
     7
   4   5
 8       9

这似乎没问题。

小提琴在这里:http: //jsfiddle.net/HRdyf/2/

这些数字是这样编码的:5个第一个数字用于第一个对角线,中心项目的索引为2,其他4个数字用于第二个对角线,除了它的中心项目。(可能有更有效的方法来编码数组,如前所述,允许更早地停止一些测试。)


Rq:我们可以用数学找到所有解决方案:

让我们称 c1、c2、c3、c4 为四个角,c 为中心点,d11、d12、d21、d22 为两条对角线的剩余两个点。然后
1) c1 + c2 + c3 + c4 = 26
2) c1 + d11 + m + d12 + c3 = 26
3) c2 + d21 + m + d22 + c4 = 26
4) 所有点都不同,并且在 1.. 9 范围。
5)(从 4 开始):所有点的总和 = 45(从 1 到 9 的总和)

6) 来自 5) 和 1) --> d11 + d12 + m + d21 + d22 = 45 - 26 = 19
(内点总数 = 总数 - 角点总数)

7) 现在加上 2) 和 3) 并使用 1) 和 6) 我们有 19 + 26 + m = 26 + 26
所以 --->>> m=7
8) 考虑到 1) 和 4) 和 7),我们看到如果
不同时使用 9 和 8,我们不能用四个不同于 7 的整数达到 26,(没有 7
和 9 我们可以达到的最大值是 8+6+5+4 = 25,没有 7 和 8 的最大值是 9 +6+5+4 = 24 )
所以 --> 两个角的值为 9,8。
9) 使用 8)、1)、7) 和 4) :另外两个角只能是 6,3 或 5,4(如果 r1 和 r2 不是 9 或 8 个角,我们有 r1+ r2 = 9 )

此时:中心为 7,角为 [4,5,8,9] 或 [3,6,8,9](和排列)
对于 [4,5,8,9] - > 保持 [1 ,2,3,6] (sum = 12)
对于 [3,6,8,9] - > 仍然是 [1,2,4,5] (sum = 12)

我们不能在同一对角线上有 9 和 8,因为 8 + d11 + 7 + d12 + 9 = 26 使得 d11 + d12 = 2 考虑到 4 是不可能的)

让我们考虑角点 = [4,5,8,9] 的情况,并查看从 9 开始的对角线的末端。它可能是 4 或
5。4 : 9 + d11 + 7 + d12 + 4 = 26 --> d11 + d12 = 6 --> (3,1) 是 d11 和 d12 的唯一解 --> 对于 d21 和 d22 仍然是 (2,6)。
5 ->> d11 + d12 = 7 --> 没有解决方案,给定 4) 并且 4 和 5 正在使用中

现在,corners = [3,6,8,9] 的情况,还要考虑从 9 开始的对角线的末端。它可能以 6 或 3
3 结束:d11 + d12 = 7 (5, 2) 仅解决方案 (4, 3 和 6,1 无法工作,因为 3 和 6 正在使用中)
6 : d11 + d12 = 10 无解。(6,4 / / 7,3 / 8,2 / 9,1 均使用二手图。)

---> 所以从 9 开始的对角线只能以 4 或 3 结束。
扣除 ---> 以 8 开始的对角线将以 5(当另一个以 4 结束时)或 6(当另一个结束时)结束3)。

有多少解决方案?
选择 9 所在位置的 4 种可能性,然后是 9 对角线末端的 2 种选择(4 或 3),然后是 8 对角线的 2 种选择(从楼上或楼下开始),然后 d11, d12 剩下 4 种可能性;d21, d22 选择:[3,1] + [2,6] 如果我们选择 4 作为 9 的结尾,[5,2] + [1,4] 如果我们选择 3 作为 9 的结尾。

4 *2 * 2 * 4 产生 64 种解决方案的组合。

于 2013-08-17T07:02:15.517 回答
1

这是在编码之前需要进行一些分析(铅笔/纸和减法)的问题之一。由于至少一条对角线必须有 9,因此该序列(对角线)的可能性很小。该序列中的下一个数字只能是 8、7 或 6,每个数字只有几种可能性。

  9 8 6 2 1 
  9 8 5 3 1 
  9 8 4 3 2 
  9 7 6 3 1  remaining 2 4 5 8 = 19
  9 7 5 4 1  remaining 2 3 6 8 = 19
  9 7 5 3 2  remaining 1 4 6 8 = 19 *
  9 6 5 4 2

(我可能错过了一些???)

一旦知道了这几个序列,那么剩余数字的总和加上序列中的一个数字必须等于 26。

编辑: 更多的铅笔/纸质作品显示了那些只有在中心作品中带有 7 的序列。

编辑: MSDN 网站上的 John Wein 提出了这个数学。

  • 所有可能数字的总和 (1-9) = 45
  • diag1val(26) + diag2val(26) - sum = 中心平方值 - 52-45 = 7
  • sum -cornervals - centerval = 4个raidal框的值 -> 45 - 26 - 7 = 12
  • 12 只能是 1,2,3,6 或 1,2,4,5 的组合
于 2013-08-17T15:19:49.460 回答
0

如果你有一个简单的“尝试所有可能性”的方法,那么并行化代码肯定可以让它更快。这很容易,因为不需要在线程之间共享变化的数据。

于 2013-08-16T23:22:22.573 回答