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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
module squeen
/*
The Queens Problem.
Or: How to put n queens on a n*n chessboard in such a way that they
cannot attack each other.
The result of this program is the number of possible solutions for
the queens problem for a certain boardsize together with one solution.
When BoardSize is 8 the result will be: (92,[4,2,7,3,6,8,5,1]),
which means the queens are on a4, b2, c7, d3, e6, f8, g5 and h1.
Strictness annotations are used at certain points, because that makes
this program more than twice as fast (the strictness analyzer is not
able to deduce this strictness information). However, other Clean programs
for the Queens problem exist without strictness annotations added by the
programmer that are only 40% slower than this solution (lqueen.icl).
*/
(&&) infixr 3 :: !Bool Bool -> Bool
(&&) a b
= code {
push_b 0
jmp_false l1
pop_b 1
jsr_eval 0
pushB_a 0
pop_a 1
.d 0 1 b
rtn
:l1
pop_a 1
.d 0 1 b
rtn
}
(||) infixr 2 :: !Bool Bool -> Bool
(||) a b
= code {
push_b 0
jmp_true l2
pop_b 1
jsr_eval 0
pushB_a 0
pop_a 1
.d 0 1 b
rtn
:l2
pop_a 1
.d 0 1 b
rtn
}
not :: !Bool -> Bool
not True = False
not False = True
(<) infix 4 :: !Int !Int -> Bool
(<) a b = code inline {
ltI
}
(>) a b :== b < a
(+) infixl 6 :: !Int !Int -> Int
(+) a b = code inline {
addI
}
inc :: !Int -> Int
inc a = a + 1
(-) infixl 6 :: !Int !Int -> Int
(-) a b = code inline {
subI
}
(==) infix 4 :: !Int !Int -> Bool
(==) a b = code inline {
eqI
}
(<>) infix 4 :: !Int !Int -> Bool
(<>) a b = not (a == b)
length :: [a] -> Int
length xs = len 0 xs
where
len :: Int [a] -> Int
len i [] = i
len i [_:xs] = len (i+1) xs
hd :: [a] -> a
hd [x:xs] = x
//import StdEnv
BoardSize :== 8 // The size of the chessboard.
// Finding all solutions for the queens problem.
Queens::Int [Int] [[Int]] -> [[Int]]
Queens row board boards
| row>BoardSize = [board : boards]
| otherwise = TryCols BoardSize row board boards
TryCols::Int Int [Int] [[Int]] -> [[Int]]
TryCols 0 row board boards = boards
TryCols col row board boards
| Save col 1 board = TryCols (col-1) row board queens
| otherwise = TryCols (col-1) row board boards
where queens = Queens (row+1) [col : board] boards
/* The strictness analyzer can't derive strictness for the first and second
argument of Save, because they are not used in the first alternative
of that function. However, Save is strict in these arguments (in the
context of this program) and adding the strictness annotations speeds
up this program considerably. */
Save::!Int !Int [Int] -> Bool
Save c1 rdiff [] = True
Save c1 rdiff [c2:cols]
| cdiff==0 || cdiff==rdiff || cdiff==0-rdiff = False
| otherwise = Save c1 (rdiff+1) cols
where cdiff = c1 - c2
/* The Start Rule: Calculate the list of solutions, show the first
solution and the length of that list. */
Start::(Int,[Int])
Start = (length solutions, hd solutions)
where solutions = Queens 1 [] []
|
