Jak korzystać z Monady wybrać, aby rozwiązać n-queens?

Question

Próbuję zrozumieć, jak działa monada Select. Najwyraźniej jest to kuzyn Cont i można go użyć do przeszukiwania wstecznego.

mam ten list opartych na rozwiązanie problemu n-królowych:

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

jestem stara się przystosować do korzystania z tego rozwiązania Select zamiast.

Wygląda na to, że Select pozwala na streszczenie "funkcji oceny", która służy do porównywania odpowiedzi. Ta funkcja jest przekazywana do runSelect. Mam wrażenie, że coś takiego jak safeDiag w moim rozwiązaniu może działać jako funkcja oceny, ale jak samemu ułożyć obliczenia Select?

Czy wystarczy sama monada Select, czy też muszę używać wersji transformatora na listach?

Answer 1

Select można postrzegać jako abstrakcję wyszukiwania w "zwartej" przestrzeni, kierując się pewnym predykatem. Wspomniałeś SAT w swoich komentarzach, czy próbowałeś modelować problem jako instancję SAT i rzucić go na solver w oparciu o Select (w duchu this paper)? Możesz wyspecjalizować wyszukiwanie, aby przerobić specyficzne więzy N-queens w swoim i zamienić solwer SAT w narzędzie N-queens solver.

Answer 2

Zainspirowany odpowiedź jd823592, a po patrząc na przykład SAT w paper, napisałem ten kod:

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 

Wydaje przybyć (choć powoli) do prawidłowego rozwiązania:

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

Nie rozumiem tego jednak bardzo dobrze. W szczególności, sposób sequence działa na transmisję funkcji (validBoard), która działa na całej tablicy na funkcje, które przyjmują indeks pojedynczej kolumny, wydaje się dość magiczny.

---

sequence -na rozwiązanie ma tę wadę, że wprowadzenie damę w kolumnie nie wyklucza się możliwości wyboru tej samej kolumnie dla kolejnych królowych; kończymy niepotrzebnie odkrywając zgubione gałęzie.

Jeśli chcemy, aby nasze wybory kolumna zostać dotknięte poprzednimi decyzjami, musimy wyjść poza Applicative i wykorzystać moc 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 

---

Wersja monadycznego nadal ma wątpliwości, że tylko ona sprawdza ukończone tablice, gdy oryginalne rozwiązanie oparte na listach wycofało się, gdy tylko częściowo ukończona tablica została uznana za będącą w konflikcie. Nie wiem, jak to zrobić, używając Select.