如何使用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皇后问题？

回答

相关问题