Skip to content

Instantly share code, notes, and snippets.

@keneanung
Last active August 29, 2015 13:59
Show Gist options
  • Save keneanung/10834935 to your computer and use it in GitHub Desktop.
Save keneanung/10834935 to your computer and use it in GitHub Desktop.
My implementation of the n queens problem in several iterations
import System.Environment
import Data.List
import Control.Monad
--Remember: foldM for list monads uses EACH element as input for the next fold!!
queen :: Int -> [[Int]]
queen n = foldM foldingFunction [] [1..n]
where
-- Our folding function. It works like this:
-- list: a list of already known safe positions from the previous fold
-- _: our input. But we don't need it as the input is only there to restrict the number of elements in the result lists
-- The function itself returns a list of lists, with the inner lists each having a position prepended that is safe
foldingFunction list _ = [x:list | x <- [1..n] \\ list, safe (x:list)]
-- This checks the given list for a safe position. Recursion is not needed, because we know the tail of the list is safe
-- from the way we construct it.
safe :: [Int] -> Bool
safe [] = True
safe (x:xs) = and (map mappingFunction functions)
where
mappingFunction func = safeDiag (func) (func x 1) xs
functions = [ (+), (-) ]
safeDiag :: ( Int -> Int -> Int ) -> Int -> [Int] -> Bool
safeDiag _ _ [] = True
safeDiag f field (x:xs) = field /= x && safeDiag f y xs
where y = f field 1
main = print $ queen 5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment