{- This is the n Queens problem. -}

module Main where

queens :: Int -> [[Int]]
queens size  = queens' size size

queens' :: Int -> Int -> [[Int]]
queens' 0     _    = [[]]
queens' (n+1) size = [q:qs | qs <- queens' n size, q <- [1..size],
			     not (threatens q qs)]

threatens :: Int -> [Int] -> Bool
threatens q qs = q `elem` qs || q `elem` (diagonals 1 qs)

diagonals :: Int -> [Int] -> [Int]
diagonals _  []    = []
diagonals n (q:qs) = (q+n) : (q-n) : diagonals (n+1) qs

main = appendChan stdout "Enter board size: " abort $
       readChan stdin abort $ \input -> 
       let line1 : ~(line2 : _) = lines input
	   size = read line1
           solns = read line2
       in if size == 0 then done else  -- This causes the size to actually read
         appendChan stdout "Number of solutions: " abort $
         appendChan stdout (concat (map (\x -> showBoard size x)
                                        (take solns (queens size))))
  	 abort done

showBoard :: Int -> [Int] -> String

showBoard size pos =
  concat (map showRow pos) ++ "\n"
    where
      showRow n = concat [if i == n then "Q " else ". " | i <- [1..size]]
                  ++ "\n"