選択モナドを使ってn-queensを解く方法は？

Question

私はSelectモナドの仕組みを理解しようとしています。明らかに、それはContのいとこで、バックトラック検索に使用できます。私が代わりにSelectを使用するには、このソリューションを適応させるのに苦労してい

-- 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] 

：

私はN-クイーン問題のこのリストベースのソリューションを持っています。

Selectは、回答を比較するために使用される「評価関数」を抽象化できるようです。その関数はrunSelectに渡されます。私のソリューションではsafeDiagのようなものが評価関数として機能するかもしれないと感じていますが、計算自体をSelectのように構成する方法はありますか？

また、Selectのモナドだけで十分ですか、またはリストの上にトランスフォーマーバージョンを使用する必要がありますか？

Answer 1

Selectは、いくつかの述語によって誘導される「コンパクト」空間での検索の抽象化として見ることができます。あなたはあなたのコメントでSATを述べました。問題をSATインスタンスとしてモデリングしてSelect（精神的にはthis paper）に基づくソルバーに投げかけましたか？ 内のN-queens固有の制約をハードワイヤリングし、SATソルバをN-queensソルバーに変えるように検索を専門にすることができます。

Answer 2

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が動作する方法は、ボード全体で機能する関数（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を使ってそれを行う方法を知らない。