-- debugged and completed version from SJP 2011 talk

-- import System.IO

--main :: IO ()
--main = do putStrLn (show (length (nq 12)))

-- :s +s enable timing
-- :s +t enable type info

nq :: Int -> [[Int]]
nq n = subtree n n []

-- subtree :: Int -> [Int] -> [[Int]]
subtree 0 n b = [b]
subtree c n b = concat $ 
              map (subtree (c-1) n) (children n b)


children :: Int -> [Int] -> [[Int]]
children n b = [ (q:b) | q <- [1..n] , safe q b ]

safe :: Int -> [Int] -> Bool
safe i []    = True
safe i (x:l) = safe' i (x:l) 1

safe' :: Int -> [Int] -> Int -> Bool
safe' _ [] _ = True
safe' i (x:l) d 
      | i == x    = False
      | i == x+d  = False
      | i == x-d  = False
      | otherwise = safe' i l (d+1)