这个题目是为了将10幢房子按放到一个10*10的格子中, 每个格子最多只能放一幢房子. 最终目的是使房子按放之后, 任何一幢房子的横轴,纵轴以及对角线都看不到其它的房子.

example.hs

module Main where

-- 是否存在重复的元素
-- [1,2,3] -> False
-- [1,1,3] -> True
isUnique :: (Eq a) => [a] -> Bool
isUnique = isUnique' []

isUnique' :: (Eq a) => [a] -> [a] -> Bool
isUnique' _ [] = True
isUnique' xs (x:xs') | x `elem` xs = False
                     | otherwise   = isUnique' (x:xs) xs'

ndinsert :: a -> [a] -> [[a]]
ndinsert x [] = [[x]]
ndinsert x l@(y:yq) = (x:l) : map (y:) (ndinsert x yq)

-- 所有排列组合
-- [1,2,3] ->  [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xq) = concat (map (ndinsert x) (permutations xq))

n :: Int
n = 9

rows :: [Int]
rows = [0..n]

solutions :: [[Int]]
solutions = [vec | vec <- permutations rows          -- 枚举出所有可能的排列
                 , isUnique [vec!!i + i | i <- rows] -- 列号+行号重复的元素在同一对角线 (西南-东北方向 /), 排除
                 , isUnique [vec!!i - i | i <- rows] -- 列号-行号重复的元素在同一对角线 (西北-东南方向 \), 排除
            ]

prettify :: [Int] -> String
prettify xs = concat $ map pos2str xs
    where pos2str i = take i (repeat '*') ++ "H" ++ take (n-i) (repeat '*') ++ "\n"

main :: IO ()
main = mapM_ putStrLn $ map prettify solutions