2016-04-25 83 views
0

我的工作解決了利用蠻力算法密碼鎖的方法,但是我跑出來的想法,我怎麼能有效地做到這一點。 This image shows how my program is structured.蠻力一個密碼鎖

這個想法是,該算法應該適用於任何數量的行,每個行可以包含任意數量的列(理由上說,不超過50個總方格)。它應該首先嚐試將'2'放入第一個方塊,然後在下一個空方塊中放置'3',以此類推。如果該方法返回true,則停止。如果沒有它重新啓動,試圖將「3」進入第一方陣,那麼在接下來的「3」,...

鎖被認爲是開放的,當每一行中每平方有正確的數字。該方法然後返回true。它只會在每個可能的序列被嘗試時返回false,而且沒有任何工作(意味着程序中的其他地方出了問題)。

我們只只考慮第一行,並說,正確的順序是「3 - 4 - 9」。按照上面的形象,這應該返回true:

//Returns true for a = 0, b = 0, c = 1 --- x = 0, y = 1, z = 2 

allEmptySquares[a][b].putValue(allEmptySquares[a][b].getPossibleSolutions.someArray[c]); 
allEmptySquares[x][y].putValue(allEmptySquares[x][y].getPossibleSolutions.someArray[z]); 

我一直在使用for循環,並使得該方法遞歸試過,但我不能得到當溶液ž> c將其工作。

有關我應該如何寫這個的任何提示?

編輯:我更感興趣的是你的想法可能的解決方案,而不是你寫代碼對我來說。

編輯:我忘了提一個很大的細節。對於每個獲得新數字的方塊,其他方塊的替代方法將會減少。想想它像數獨。這意味着當someArray.length = 0時,該方法將按照第二段中的說明重新啓動。如果所有其他方塊都收到了正確的數字,最後一個方塊的someArray.length = 1。

編輯:可能的解決方案,並且該方塊是預填充的,在程序的其它地方決定,因此,該方法需要將作爲「通用」成爲可能。

+0

你明白這個問題太大,無法真正解決,對?在「合理範圍內」示例中有10^50個解決方案。你應該編寫代碼來解決一個更簡單的問題,比如3位數的鎖,然後向我們顯示代碼。 – markspace

+0

但是你有一個算法 - 你稱之爲蠻力。你似乎要求的是:「我怎麼實現這個算法?」 - 這是代碼。正如markpace指出的那樣,10^50非常大 - 例如,如果您每納秒檢查一個代碼,則需要3.16887646×10^33年... – gilleain

+0

另一方面,您已將一些優秀細節放入您的問題,但它仍然有點神祕。爲什麼從2開始,而不是1?爲什麼獲得可能的解決方案只返回[3,7,9]而不是[1 ... 9]? – gilleain

回答

1

你能適應我用數獨的設置,一旦...它仍然是蠻力,而是約束稍微複雜。

基本流程是選擇 - 約束 - 標記 - 回溯。首先爲第一個「打開」方塊分配一個值,(只需要第一個可能的值)。然後,運行約束檢查來限制其他方塊的所有值。如果它們中的任何一個僅限於單個值,請指定該值,然後重新運行約束添加。如果你發現自己在一個有效的任務中的一切,返回;如果您發現自己有多種選擇,請選擇一個並重試;如果你發現自己沒有任何正方形的有效選擇,請回到最後的選擇,然後嘗試下一個。

(成立「回到」設置最簡單的方法是用遞歸函數調用,因此調用堆棧是相同的搜索棧。)