Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- module Main where
- import Control.Monad
- import System.Environment
- -- As not two queens can share the same column, we can represent
- -- the board as a list of integers: the row each queen is located
- -- for a given column.
- type Board = [Int]
- -- Given a board, check if a new column can be added with a queen
- -- in the given row.
- isCorrect :: Int -> Board -> Bool
- isCorrect row [] = True
- isCorrect row xs = loop xs 1
- where
- loop [] _ = True
- loop (x:xs) n
- | row == x = False
- | (row+n) == x = False
- | (row-n) == x = False
- | otherwise = loop xs (n+1)
- -- Solve the n-queens problem. Start with an empty board and try to add
- -- new columns until the board is complete. For each column, all the
- -- possible rows are tried; if a row results in a conflict, that entire
- -- set of possibilities is discarded.
- -- Note: the code uses the list monads to get backtracking behavior.
- possibilities is discarded.
- nqueens :: Int -> [Board]
- nqueens n = step [1..n] n
- where
- step values 1 = do
- x <- values
- return [x]
- step values n = do
- x <- values
- y <- step values (n-1)
- guard $ isCorrect x y
- return (x:y)
- -- Ask the user for the board size, defaulting to 8, solve the n-queens
- -- problem, and print the results.
- main :: IO ()
- main = do
- args <- getArgs
- let n = case args of
- [] -> 8
- _ -> read $ head args
- let q = nqueens n
- mapM_ print q
- putStrLn $ "Number of different results: " ++ show (length q)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement