blob: f2762a2a151d7eb9d2db2b7bd14c17185f3d5121 (
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
|
module lqueen
// The Queens Problem, slow version.
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 [] []
|
