Как использовать монаду Выбрать для решения n-queens?

Question

Я пытаюсь понять, как работает монада Select. По-видимому, это двоюродный брат Cont, и его можно использовать для поиска назад.

У меня есть этот список на основе решения проблемы н-королев:

-- 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, или мне нужно использовать версию трансформатора по спискам?

Answer 1

Select можно рассматривать как абстракцию поиска в «компактном» пространстве, руководствуясь некоторым предикатом. Вы упоминали SAT в своих комментариях, пытались ли вы моделировать проблему как экземпляр SAT и бросали его на решателя на основе Select (в духе this paper)? Вы можете специализировать поиск, чтобы связать конкретные ограничения N-queens внутри вашего и превратить SAT-решателя в решателя N-queens.

Answer 2

Вдохновленный ответ jd823592, и после того, глядя на пример SAT в paper, я написал этот код:

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.