這可以通過線程運行得更快嗎？

這是如何工作的：使用數字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

來源

2013-08-16 jgetrost

我不我們希望代碼在開始之前承擔任何事情，它只知道有9個盒子，並且需要嘗試所有解決方案以查看哪些盒子可以工作。 – jgetrost

當然 - 因爲你基本上測試了幾十種不同的組合，所以你可以（例如）產生9個線程：一個用於從1開始的所有組合，另一個用於從2開始的所有組合，依此類推。 –

的例子或參考將不勝感激。 – jgetrost

在使用線程之前，應該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
這使得：

這似乎是確定。

小提琴是在這裏：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的範圍內。（從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
所以 - 8）考慮到1）和4）和7），我們看到我們不能達到26與四個整數
不同於7而不使用9和8，（我們可以達到的最大值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]（總和= 12）
對於[3,6,8,9] - >遺留[1,2,4,5]（總和= 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唯一的解決方案，d12和d12→剩餘（2,6）。
5 - >> d11 + d12 = 7 - > no solution，given 4）and that 4 and 5 are in use

現在角= [3,6,8,9]的情況下，也考慮它可能以6或3結尾
3：d11 + d12 = 7（5，2）唯一的解決方案（因爲3和6在使用中，因此4,3和6,1無法工作）
6：d11 + d12 = 10無解。（6,4// 7,3/8,2/9,1都使用一個用過的數字。）

--->所以由9開始的對角線只能以4或3結尾。
扣除 - - >由8開始的對角線將以5結尾（當另一個以4結尾時）或由6 （當另一個以3結尾時）結束。

有多少種解決方案？
4個可能性選擇9的位置，然後9個對角線端點的2個選項（4或3），然後8個對角線的2個選擇（從樓上或樓下開始），然後爲d11，d12剩下4個可能性; d21，d22選擇：如果我們選擇4作爲9的結尾，則選擇[3,1] + [2,6]，如果選擇3作爲9的結尾，選擇[5,2] + [1,4]。

4 * 2 * 2 * 4產生64種解決方案組合。

來源

2013-08-17 07:02:15 GameAlchemist

使用整數和回溯這種算法的速度可以大大提高。不需要多線程恕我直言。 – dbasnett

選擇了哪個答案？鏈接的第一部分代碼或多或少是一種強力方法。第二個答案（Rq :)表明，這個問題是安排兩個對角線的已知值，使角加起來的問題。 – dbasnett

mmm ...我無法回答這個問題，因爲我不是那個'選中'的人......甚至可能都是答案！ :-) – GameAlchemist

如果你有一個簡單的「嘗試所有的可能性」的方法，那麼paralellizing代碼肯定可以使其更快。而且這很容易，因爲不需要在線程間共享不斷變化的數據。

來源

2013-08-16 23:22:22 FrankPl

能否詳細說明一下？提供示例？參考？ – jgetrost

「絕對」 - >「在多處理器系統上」 – GSerg

這是在編碼之前需要一些分析（鉛筆/紙和減法）的那些問題之一。由於至少一個對角線必須有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

（I可能已經錯過一些???）

一旦這些少數序列是已知的，則剩餘數加上從序列號碼中的一個的總和必須等於26

編輯：多一點鉛筆/紙上作品表明，那些只有在7中心的序列工作。

編輯： MSDN網站上的John Wein提出了這個數學。

所有可能的數字的總和（1-9）= 45
diag1val（26）+ diag2val（26） - 和=中心平方值 - 52-45 = 7
總和 - cornervals - 的4 raidal盒centerval =值 - > 45 - 26 - 7 = 12
12只能是1,2,3,6一些組合或1,2,4,5-

來源

2013-08-17 15:19:49 dbasnett

這可以通過線程運行得更快嗎？

回答

相關問題