blob: cb134c6ff77c3287674308542081486a1f4a8387 (
plain) (
blame)
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
|
module lqueen
// The Queens Problem, slow version.
(&&) 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
// The second alternative of TryCols is added to make sure Save is never
// called with an empty list.
TryCols::Int Int [Int] [[Int]] -> [[Int]]
TryCols 0 row board boards = boards
TryCols col row [] boards = TryCols (col-1) row [] queens
where
queens = Queens (row+1) [col] 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
Save::Int Int [Int] -> Bool
Save c1 rdiff [c2] = cdiff<>0 && cdiff<>rdiff && cdiff<> 0 - rdiff
where
cdiff = c1 - c2
Save c1 rdiff [c2:cols]
| cdiff==rdiff || cdiff==0 || cdiff==0-rdiff = False
| otherwise = Save c1 (inc rdiff) 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 [] []
|
