import Control.Monad
import System.Environment

-- | data types for the puzzle
type Row    = Int
type State  = [Row]
type Thread = [Row]

-- | utility functions
empty = null

-- | Check for infeasible states
infeasible :: Int -> (State, Thread) -> Bool
infeasible n ([], _)    = False
infeasible n ((r:rs),t) = length rs >= n || attack r rs || infeasible n (rs, t)

feasible n st = not $ infeasible n st

-- | Check if a row is attacking another row of a state
attack :: Row -> [Row] -> Bool
attack r rs = r `elem` rs
            || r `elem` (upperDiag rs)
            || r `elem` (lowerDiag rs)
  where
    upperDiag xs = zipWith (-) xs [1..]
    lowerDiag xs = zipWith (+) xs [1..]

-- | Check if it is a goal state
isGoal :: Int -> (State, Thread) -> Bool
isGoal n (rs,t) = (feasible n (rs,t)) && (length rs == n)

-- | Perform a move
move :: Int -> (State, Thread) -> (State, Thread)
move x (s,t)  = (x:s, x:t)

choices n = [1..n]
moves n   = pure move <*> choices n

emptySt = ([],[])

-- | Breadth-first search
bfs :: Int -> [(State, Thread)] -> (State, Thread)
bfs n []                     = error "Could not find a feasible solution"
bfs n sts | (not.empty) goal = head goal
          | otherwise        = bfs n sts2
  where
    goal = filter (isGoal n) sts2
    sts2 = filter (feasible n) $ (moves n) <*> sts

-- | Depth-first search
dfs :: Int -> (State, Thread) -> [(State, Thread)]
dfs n st | isGoal n st     = [st]
         | infeasible n st = [emptySt]
         | otherwise       = do x   <- [1..n]
                                st2 <- dfs n $ move x st
                                guard $ st2 /= emptySt
                                return st2

main = do
  [narg] <- getArgs
  let n = read narg :: Int
  print (bfs n [emptySt])
  print (head $ dfs n emptySt)