solvingsudoku-universityofnottingham-資料下載頁(yè)
2025-05-02 22:41本頁(yè)面
【導(dǎo)讀】WhatisSudoku?renamedSudoku(~“singlenumber”);mustgohere?inthiscolumn.Andsoon…easypuzzle.easy=["2138","5","76","13","981257","318","982","569784",rows::Matrixa?[Rowa]. Columns. cols::Matrixa?[Rowa]. AndBoxes. boxs::Matrixa?[Rowa]. valid::Grid?Bool. validg=allnodups(rowsg)?allnodups(colsg)?
【正文】 nates instantly! 29 But… solve39。 gentle No solution after two hours we need to think further! For a gentle example, pruning leaves around 381 grids to consider, which is still a huge number: 443426488243037769948249630619149892803 30 Reducing The Search Space ? After pruning there may still be many choices that can never lead to a solution。 ? But such bad choices will be duplicated many times during the collapsing process。 ? Discarding these bad choices is the key to obtaining an efficient Sudoku solver. 31 Blocked Matrices Let us say that a matrix is blocked if some square has no choices left, or if some row, column, or box has a duplicated single choice: Key idea a blocked matrix can never lead to a solution. 1 1 2 1 3 4 3 32 Expanding One Choice Transform a matrix of lists into a list of matrices by expanding the first square with choices: expand :: Matrix [a] ? [Matrix [a]] 1 2 3 4 1 2 2 3 4 1 2 1 3 4 1 2 33 Our Final Solver solve’’ :: Grid ? [Grid] solve’’ = search . prune . choices search :: Matrix [Char] ? [Grid] search m | blocked m = [] | plete m = collapse m | otherwise = [g | m39。 ? expand m , g ? search (prune m39。)] 34 Notes ? Using fix prune rather than prune makes the program run slower in this case。 ? No need to filter out valid grids, because they are guaranteed to be valid by construction。 ? This program can now solve any newspaper Sudoku puzzle in an instant! 35 The Result This program has saved my life my Sudoku addiction is finally cured!! Subliminal Message Haskell is the world39。s greatest programming language.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1