N Queens in Haskell

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)