एन-क्वींस को हल करने के लिए मोनाड का चयन कैसे करें?

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 को "कॉम्पैक्ट" स्पेस में एक खोज के एक अमूर्त के रूप में देखा जा सकता है, जो कुछ अनुमानित निर्देशित है। आपने अपनी टिप्पणियों में एसएटी का उल्लेख किया है, क्या आपने एसएटी इंस्टेंस के रूप में समस्या को मॉडलिंग करने की कोशिश की है और इसे Select (this paper की भावना में) के आधार पर एक सॉल्वर पर फेंक दिया है? आप अपने के अंदर एन-क्वींस विशिष्ट बाधाओं को हार्डवायर करने के लिए खोज को विशेषज्ञ बना सकते हैं और एसएटी सॉल्वर को एन-क्वींस सॉल्वर में बदल सकते हैं।

Answer 2

jd823592 के जवाब से प्रेरित होकर, और paper में सैट उदाहरण देखने के बाद, मैं इस कोड लिखा है:

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

:

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 

इसे आने में (हालांकि धीरे) लगता है एक वैध समाधान के लिए

हालांकि, मैं इसे बहुत अच्छी तरह समझ नहीं पा रहा हूं। विशेष रूप से, sequenceSelect के लिए काम करता है, एक फ़ंक्शन (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 

---

monadic संस्करण अभी भी समस्या है कि यह केवल पूर्ण बोर्डों की जांच करता है, जब मूल सूची-आधारित समाधान जैसे ही आंशिक रूप से पूर्ण बोर्ड के रूप में बैकट्रैक किया जाता है, तो एक संघर्ष होता है। मुझे नहीं पता कि Select का उपयोग करके ऐसा कैसे करें।