Finding NQueens written in Haskell

N-Queens.hs

-- Haskell NQueens
-- Name: Amos Gwa
-- Date: 22 November 2016
import Data.List

-- The position of the queens will be unique per row
-- because there will be no two queens in the same columns.
-- For example, this n = 4 with configuration of [1,2,3,4] is
-- Q X X X
-- X Q X X
-- X X Q X
-- X X X Q
-- Therefore, we can generate the position of Queen in each row
-- as permutation of numbers 1..n
permutatePossibleBoard:: Int-> [[Int]]
permutatePossibleBoard n = filter (notConsecutive) $ permutations [1..n]

-- After the permutation, we only need to filter out
-- the configuration that has violation of diagonal.
-- Two queens are in diagonal if their ROW dist and COL dist
-- are the same. In our configuration, we have our ROW position.

-- This will create a tuple with (column, row). Our columns are
-- consistent. For the above configuration it will be [(1,1)..(4,4)]
createTuple:: [Int] -> [(Int, Int)]
createTuple [] = []
createTuple x = [(col, row) | (col,row) <- zip [1..length x] x ]

-- Check if the given configuration is valid or not by checking
-- if the distance of col and row for the two queen positions are
-- the same.
isValid:: [(Int,Int)] -> Bool
isValid [(_,_)] = True
isValid ((init_col,init_row):xs) = (and $ map (\(col, row) -> (abs(init_col - col) /= abs(init_row - row))) xs ) && isValid xs

-- Convert the given configuration to tuple that has both col and row position.
-- Then pass it to isValid to check.
checkDiagonal:: [Int] -> Bool
checkDiagonal [] = True
checkDiagonal x = isValid $ createTuple x

-- Filter all of the configs that doesn't meet the rules.
nQueensConfig:: Int -> [[Int]]
nQueensConfig boardSize = filter (checkDiagonal) $ permutatePossibleBoard(boardSize)

-- Draw board
drawAnswers:: [[Int]] -> String
drawAnswers [] = ""
drawAnswers (x:xs) =  (drawEachConfig x $ length x) ++ "\n" ++ drawAnswers xs

drawEachConfig:: [Int] -> Int -> String
drawEachConfig [] _ = ""
drawEachConfig (x:xs) size = concat( intersperse " " $ [if (idx == x) then "Q" else "X" | idx <- [1..size]] ) ++ "\n" ++ drawEachConfig xs size

-- Display all of the configs
nQueens:: IO()
nQueens = do
 putStrLn ("Enter the size of the board : ")
 size <- readLn :: IO Int 
 let answers = nQueensConfig size
 case length(answers) of 
  0 -> putStrLn ("No Solution")
  otherwise -> do putStrLn(drawAnswers answers)

-- Just display the number of Soln
nQueensNumSoln:: IO()
nQueensNumSoln = do
 putStrLn ("Enter the size of the board : ")
 size <- readLn :: IO Int 
 putStrLn( show (length $ nQueensConfig size))

-- Optimization : Remove arrays with consecutive numbers because they are in diagonal.
-- This saves execution time by ~50%.
notConsecutive:: [Int] -> Bool
notConsecutive (x:[]) = True
notConsecutive (x:xs) = (abs( x - ( head xs ) ) /= 1 ) && notConsecutive xs