如何使用Select monad來解決n皇后問題？

我想了解Select monad是如何工作的。顯然，它是Cont的表親，它可以用於回溯搜索。如何使用Select monad來解決n皇后問題？

我有這個基於列表的解決N皇后問題：

-- All the ways of extracting an element from a list. 
oneOf :: [Int] -> [(Int,[Int])] 
oneOf [] = [] 
oneOf (x:xs) = (x,xs) : map (\(y,ys) -> (y,x:ys)) (oneOf xs) 

-- Adding a new queen at col x, is it threathened diagonally by any of the 
-- existing queens? 
safeDiag :: Int -> [Int] -> Bool 
safeDiag x xs = all (\(y,i) -> abs (x-y) /= i) (zip xs [1..]) 

nqueens :: Int -> [[Int]] 
nqueens queenCount = go [] [1..queenCount] 
    where 
    -- cps = columsn of already positioned queens. 
    -- fps = columns that are still available 
    go :: [Int] -> [Int] -> [[Int]] 
    go cps [] = [cps] 
    go cps fps = [ps | (p,nfps) <- oneOf fps, ps <- go (p:cps) nfps, safeDiag p cps]

我努力適應這個解決方案中使用Select代替。

看來Select可以讓你抽象出用於比較答案的「評估函數」。該功能傳遞給runSelect。我感覺像我的解決方案中的safeDiag這樣的東西可以用作評估函數，但是如何構造Select計算本身？

另外，僅使用Select monad就足夠了，還是我需要在列表上使用變換器版本？

來源

2017-02-21 danidiaz

您確定要「選擇」monad嗎？我對「選擇」的理解是它試圖證明存在一種可能的解決方案（作爲證明證明）。「Select」的典型例子是SAT求解器。你可能會用'SelectT'強制通過列表monad，但我更確定你會真正使用select monad。 – Alec

@Alec我讀過「Select」適用於回溯搜索，而n-queens是這種類型的原型問題，所以我認爲這對monad來說是一個很好的用例。 – danidiaz

區別可能是回溯到找到所有解決方案和回溯，直到找到解決方案。然後，我再一次只玩過「選擇」，所以不要拿任何我認真說的話。 – Alec

Select可以被看作是在一個謂詞的引導下在「緊湊」空間中進行搜索的抽象概念。您在評論中提到了SAT，您是否嘗試將問題建模爲SAT實例，並根據Select（本着this paper的精神）將其解決？您可以專門進行搜索以硬連線 $\varphi$ 內的N皇后特定約束條件，並將SAT求解器轉換爲N皇后求解器。

來源

2017-02-22 12:02:46 jakubdaniel

通過jd823592的回答啓發，並在paper看SAT例子後，我寫了這個代碼：

import Data.List 
import Control.Monad.Trans.Select 

validBoard :: [Int] -> Bool 
validBoard qs = all verify (tails qs) 
    where 
    verify [] = True 
    verify (x : xs) = and $ zipWith (\i y -> x /= y && abs (x-y) /= i) [1..] xs 

nqueens :: Int -> [Int] 
nqueens boardSize = runSelect (traverse selectColumn columns) validBoard 
    where 
    columns = replicate boardSize [1..boardSize] 
    selectColumn candidates = select $ \s -> head $ filter s candidates ++ candidates

似乎到達（儘管速度緩慢），以一個有效的解決方案：

ghci> nqueens 8 
[1,5,8,6,3,7,2,4]

但是我不太瞭解它。特別是，sequence的工作方式爲Select，將可在整個電路板上工作的函數（validBoard）轉換爲採用單列索引的函數，看起來很神奇。

的sequence基於溶液具有把一個王后在列不排除選擇用於後續皇后同一列的可能性缺陷;我們最終不必要地探索註定的分支機構。

如果我們想通過先前的決定會影響我們的列選擇，我們需要超越Applicative和使用的Monad功率：

nqueens :: Int -> [Int] 
nqueens boardSize = fst $ runSelect (go ([],[1..boardSize])) (validBoard . fst) 
    where 
    go (cps,[]) = return (cps,[]) 
    go (cps,fps) = (select $ \s -> 
    let candidates = map (\(z,zs) -> (z:cps,zs)) (oneOf fps) 
    in head $ filter s candidates ++ candidates) >>= go

的單子版本仍然有問題，它只是檢查完成的董事會，當原來的基於清單的解決方案在發現部分完成的董事會發生衝突後立即回頭。我不知道如何使用Select來做到這一點。

來源

2017-02-22 20:57:13 danidiaz

「特別是'序列'爲'選擇'工作的方式似乎很神奇」 - 是的，這個應用實例是積極向上的。 – duplode

如何使用Select monad來解決n皇后問題？

回答

相關問題