優化數獨求解方法

爲一個任務製作一個數獨求解器，我遇到了解決數獨的空白單元格的問題。我可以很容易地解決具有獨特解決方案的細胞，但是當我遇到具有多種解決方案的單元格（在數獨的當前狀態下）時，我想轉到下一個空白處，嘗試填充儘可能多的數獨，然後「嘗試「價值觀並相應地分出我的解決方案。優化數獨求解方法

我的問題是，我不知道如何跟蹤我所處的空白值。

blank :: Sudoku -> Pos 
blank sudoku 
    | elem '.' $ toString sudoku = ((positInRow `div` 9), (positInRow `mod` 9)) 
    | otherwise = error "no blanks" 
    where 
     positInRow = fromJust $ elemIndex '.' $ toString sudoku 

nextBlank :: Sudoku -> Pos -> Pos 
nextBlank sudoku (x, y) 
    | elem '.' $ drop (x*9+y) $ toString sudoku = blank (fromString $ drop (x*9+y) $ toString sudoku) 
    | otherwise = error "no blanks"

這是我嘗試的解決方案，但如果我嘗試遞歸解決數獨，它會陷入無限循環尋找相同的「nextBlank」如果原來的一個空白不更新的價值數獨。

有沒有辦法正確實現這個功能？

來源

2017-05-25 420fedoras

首先讓我包你的代碼在一些樣板，所以我們可以運行東西容易：

module RandomNoise where 

import Data.Maybe 
import Data.List 

type Pos = (Int, Int) 
type Sudoku = String 

toString :: Sudoku -> String 
toString = id 

fromString :: String -> Sudoku 
fromString = id 

blank :: Sudoku -> Pos 
blank sudoku 
    | elem '.' $ toString sudoku = (positInRow `div` 9, positInRow `mod` 9) 
    | otherwise = error "no blanks" 
    where 
    positInRow = fromJust $ elemIndex '.' $ toString sudoku 

nextBlank :: Sudoku -> Pos -> Pos 
nextBlank sudoku (x, y) 
    | elem '.' $ drop (x*9+y) $ toString sudoku = blank (fromString $ drop (x*9+y) $ toString sudoku) 
    | otherwise = error "no blanks" 

testSudoku = "uiae.uiae.uiae.uiae" 

firstBlank = blank testSudoku 
secondBlankOrNot = nextBlank testSudoku firstBlank

如果你打開ghci中並加載一個文件的內容，你可以看到，

firstBlank = (0,4) 
secondBlank = (0,0)

和

drop (0*9+4) testSudoku

收率

".uiae.uiae.uiae"

所以這裏有幾個問題。

您不會從字符串中刪除足夠多的字母。您還需要刪除該位置指定的空白。
在nextBlank中，您需要將拖動的字符串的長度添加到空白處確定的索引中，然後再將它們轉換爲位置，否則您將獲得某種相對於最後一個空白位置的垃圾位置。我建議在字符串表示中使用索引，並將其作爲單獨函數的最後一步來計算位置。

來源

2017-05-25 07:29:40 Krom

優化數獨求解方法

回答

相關問題