2 回答

TA貢獻1829條經驗 獲得超7個贊
我認為我的問題來自于 possible () 函數中的 double for
這對我來說看起來不錯。雙 for 循環可能非常慢,但在這種情況下,每個循環僅進行 3 次迭代,因此內部主體僅執行 9 次。這沒什么大不了的。
不過,還有更快的方法來實施“可能性檢查”。例如,通過跟蹤每行、列和塊中使用了哪些值。如果將其存儲為位掩碼,則很容易計算(只需幾個位數學運算)給定單元格可能的值:根本沒有循環。
您可以用來加速求解器的主要技術是添加迭代約束傳播:迭代地查找可以直接填充而無需搜索的單元格,例如Naked Singles和Hidden Singles。根據我的經驗,傳播是慢速求解器和快速求解器之間最大的區別,但當然高效的實現也很重要。

TA貢獻1799條經驗 獲得超9個贊
目前,您正在遞歸地暴力破解每種可能的組合。我沒有任何神奇的解決方案來繞過暴力破解。然而我們可以讓暴力破解變得更聰明。
目前的方法:
你正在檢查每一個未填充的空間。第一次迭代中大約 70-75,隨后的每次迭代中減少一個。
對于每個這樣的字段,您嘗試用所有可能的數字填充它(最多 9 個選項,通常更少)
然后你在一個較少填充字段的板上遞歸地調用自己
直到您偶然發現第一個可能的解決方案。
您當前正在執行的操作數量介于 9^(開始時填充的 81 個位置)(上限,意味著在不修剪的情況下暴力破解每個選項)到更低的值 - 例如,您填充的值越多,就越頻繁你會失敗并修剪可能性樹的分支。實際計數類似于:7 * 7 * 7 * ... * 6 * 6 * ... * ... 直到完成。
因此,第一個可能的改進是更智能的修剪。當且僅當滿足以下條件時,董事會才是可能的:
它的所有字段都已填滿
所有未填寫的字段都有超過零個可能的選項。
目前,您僅檢查待填寫的字段,這意味著您可以創建稍后會立即被拒絕的面板。這會產生很多不必要的分支。一些偽代碼來說明:
function possibleCount(board, x, y) {
/*code to compute available options - e.g. number 0-9*/
return count
}
function boardPossible(board,x, y, n) {
board[x][y] = n
foreach (field in board) {
if (possibleCount(field) == 0) {
//if there is any field that is invalidated by inserting
//the value, we are stuck and we can prune the branch.
return false
}
}
}
這看起來需要大量額外的計算,但是我們在這里做出了權衡。我們將在每一步上花費更多的時間(計算可能的板選項)來盡早修剪大部分分支。此外,您可以通過簡單地先填充選項最少的字段
,將計算從最初的 7 * 7 * 7 ... * 6 * 6 選項轉移到更合理的選項。 這將導致更快失敗,進而意味著需要覆蓋的選項更少。
我想到的最后一點優化是,通過為每行、列和方塊提供可用選項列表,可以加快每個字段的可用選項的計數。
更新字段時,只需從[行、列、方]中刪除新值即可。
檢查字段的可用性時,檢查該字段是否適用于每個[行、列、方塊]
這將消除上述電路板檢查帶來的大部分開銷。不幸的是我目前正在工作,但如果我有時間,我稍后會嘗試做一些基準測試。
添加回答
舉報