-- 8 Queens in Haskell
-- Expanded for Clarity
--
-- by Harold Lee
-- harold at hotelling dot net

-- Data types to make things clearer

type Queen = Int
type Board = [Queen]
type Solutions = [Board]

-- Helper functions

elemToList :: a -> [a]
elemToList x = [x]

nTimes :: Char -> Int -> String
nTimes c n = take n (repeat c)

-- The Main Function

main :: IO ()
main = do putStr (drawBoard solution)

-- Functions for Drawing the Solution

drawBoard :: Board -> String
drawBoard b = concat (map drawQueen b)

drawQueen :: Queen -> String
drawQueen q = (nTimes '.' (q-1)) ++ 
              "Q" ++ 
              (nTimes '.' (8-q)) ++
              "\n"

-- Code for finding a solution to the problem

boardSize = 8

solution :: Board
solution = queens (boardSize - 1)

queens :: Int -> Board
queens n = head (allQueens !! n)

allQueens :: [Solutions]
allQueens = (map elemToList allColumns) : (map addAQueen allQueens)

addAQueen :: Solutions -> Solutions
addAQueen boards = [ q:b | q <- allColumns, b <- boards, safe q b ]

safe :: Queen -> Board -> Bool
safe q b = safe' q b 1
  where safe' x (y:ys) n = notElem x [y, y+n, y-n] && safe' x ys (n+1)
        safe' x   _    n = True

allColumns :: [Queen]
allColumns = [ 1 .. boardSize ]