1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
module Main
    where
-- 严蔚民、吴伟民：《数据结构》（第二版）清华大学出版社 Page 149
-- 4皇后问题建模

level::Int -> [(Int, Int)]
level n = [(n,x) | x <- [0..3]]

listlevel :: Int -> [[(Int, Int)]]
listlevel n = [[(n,x)] | x <- [0..3]]

-- collision : 2 point has collision
collision :: (Int, Int) -> (Int, Int) -> Bool
collision (x,y) (i,j) = x == i || y == j || x-i == y-j || x-i == j-y

validexpand x [] = True
validexpand x (y:ys) = not (collision x y) && (validexpand x ys)

expand :: [(Int, Int)] -> [[(Int, Int)]] -> [[(Int,Int)]]
-- if there is one param being empty list, the answer is empty list
expand [] _ = [] 
expand _ [] = []
expand (x:xs) [y]   -- 2nd param has single element
    | (validexpand x y) = reverse (x:y) : (expand xs [y])
    | otherwise = (expand xs [y])
expand xs (y:ys) = (expand xs [y]) ++ (expand xs ys)

pool:: Int -> [ [(Int, Int)] ]
pool 0 = listlevel 0
pool n = expand (level n) (pool (n-1))

queue4 = pool 3

main = putStrLn $ show queue4