亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

Javascript - 如何優化我的數獨?

Javascript - 如何優化我的數獨?

人到中年有點甜 2023-08-18 16:51:19
我想創建一個數獨求解器,但我注意到對于專家級數獨,需要幾秒鐘才能顯示結果......這是我的一段代碼:function possible(board, y, x, n) {    for (let i = 0; i < 9; i++) {        if (board[y][i] === n || board[i][x] === n) {            return false;        }    }    const xSquare = Math.floor(x / 3) * 3;    const ySquare = Math.floor(y / 3) * 3;    for (let j = 0; j < 3; j++) {        for (let i = 0; i < 3; i++) {            if (board[ySquare + i][xSquare + j] === n) {                return false;            }        }    }    return true;}function solve(board) {    for (let y = 0; y < 9; y++) {        for (let x = 0; x < 9; x++) {            if (board[y][x] === 0) {                for (let n = 1; n <= 9; n++) {                    if (possible(board, y, x, n)) {                        board[y][x] = n;                        if (solve(board)) {                            return board;                        }                    }                }                board[y][x] = 0;                return false;            }        }    }    return board;}我的函數 possible() 是查看 x 軸和 y 軸是否具有相同的數字,以及正方形(3x3)是否與當前框具有相同的數字。我的函數solver()函數用于查看數組中是否不再有0以及可能的函數possible()是否返回true。我認為我的問題來自于 possible () 函數中的 double for ,它從整個數組開始,但我不知道如何讓它停止在這種情況下......
查看完整描述

2 回答

?
吃雞游戲

TA貢獻1829條經驗 獲得超7個贊

我認為我的問題來自于 possible () 函數中的 double for

這對我來說看起來不錯。雙 for 循環可能非常慢,但在這種情況下,每個循環僅進行 3 次迭代,因此內部主體僅執行 9 次。這沒什么大不了的。

不過,還有更快的方法來實施“可能性檢查”。例如,通過跟蹤每行、列和塊中使用了哪些值。如果將其存儲為位掩碼,則很容易計算(只需幾個位數學運算)給定單元格可能的值:根本沒有循環。

您可以用來加速求解器的主要技術是添加迭代約束傳播:迭代地查找可以直接填充而無需搜索的單元格,例如Naked Singles和Hidden Singles。根據我的經驗,傳播是慢速求解器和快速求解器之間最大的區別,但當然高效的實現也很重要。


查看完整回答
反對 回復 2023-08-18
?
揚帆大魚

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 選項轉移到更合理的選項。 這將導致更快失敗,進而意味著需要覆蓋的選項更少。

我想到的最后一點優化是,通過為每行、列和方塊提供可用選項列表,可以加快每個字段的可用選項的計數。

  • 更新字段時,只需從[行、列、方]中刪除新值即可。

  • 檢查字段的可用性時,檢查該字段是否適用于每個[行、列、方塊]

這將消除上述電路板檢查帶來的大部分開銷。不幸的是我目前正在工作,但如果我有時間,我稍后會嘗試做一些基準測試。


查看完整回答
反對 回復 2023-08-18
  • 2 回答
  • 0 關注
  • 126 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號