Advertisement
Guest User

N Queens in Haskell

a guest
Feb 17th, 2012
1,849
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. module Main where
  2.  
  3. import Control.Monad
  4. import System.Environment
  5.  
  6.  
  7. -- As not two queens can share the same column, we can represent
  8. -- the board as a list of integers: the row each queen is located
  9. -- for a given column.
  10. type Board = [Int]
  11.  
  12.  
  13. -- Given a board, check if a new column can be added with a queen
  14. -- in the given row.
  15. isCorrect :: Int -> Board -> Bool
  16. isCorrect row [] = True
  17. isCorrect row xs = loop xs 1
  18.     where
  19.     loop [] _ = True
  20.     loop (x:xs) n
  21.         | row == x = False
  22.         | (row+n) == x = False
  23.         | (row-n) == x = False
  24.         | otherwise = loop xs (n+1)
  25.  
  26.  
  27. -- Solve the n-queens problem. Start with an empty board and try to add
  28. -- new columns until the board is complete. For each column, all the
  29. -- possible rows are tried; if a row results in a conflict, that entire
  30. -- set of possibilities is discarded.
  31. -- Note: the code uses the list monads to get backtracking behavior.
  32. possibilities is discarded.
  33. nqueens :: Int -> [Board]
  34. nqueens n = step [1..n] n
  35.     where
  36.     step values 1 = do
  37.         x <- values
  38.         return [x]
  39.     step values n = do
  40.         x <- values
  41.         y <- step values (n-1)
  42.         guard $ isCorrect x y
  43.         return (x:y)
  44.  
  45.  
  46. -- Ask the user for the board size, defaulting to 8, solve the n-queens
  47. -- problem, and print the results.
  48. main :: IO ()
  49. main = do
  50.     args <- getArgs
  51.     let n = case args of
  52.         [] -> 8
  53.         _ -> read $ head args
  54.     let q = nqueens n
  55.     mapM_ print q
  56.     putStrLn $ "Number of different results: " ++ show (length q)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement