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
|
/* Example: queens problem. */
/* Queens(n) : main entry function. This function returns a list of
* results to the n-queens problem. The results will be lists of numbers,
* for instance {2,3,1,4} which is to be interpreted as queens standing
* on (1,2), (2,4), (3,1) and (4,3).
*
* No typechecking is done on the arguments of the internal functions,
* only on Queens(n), since that is the only function that should be
* used by the outside world.
*/
Queens(n_IsPositiveInteger) <--
[
Local(result);
Set(result,{});
Queens(n,{},1 .. n,result); /* build result */
result; /* return result */
];
/* IsOnDiagonal determines if two queens are on a diagonal */
10 # IsOnDiagonal({_x1,_y1},{_x2,_y2})_(SubtractN(x1,x2) = SubtractN(y1,y2)) <-- True;
20 # IsOnDiagonal({_x1,_y1},{_x2,_y2})_(SubtractN(x1,x2) = SubtractN(y2,y1)) <-- True;
30 # IsOnDiagonal(_n,_m) <-- False;
/* QueenCollides determines if a new queen to be positioned on n collides
* with the queens on positions held in the list
*/
10 # QueenCollides(_n,_list) <--
[
Local(result);
Set(result, False);
While(And(Not(result), Not(Equals(list, {}))))
[
Set(result, IsOnDiagonal(n,Head(list)));
Set(list, Tail(list));
];
result;
];
/* If new queen does not collide with other queens, add to try list,
* and solve the n-1 queens problem
*/
TryAddQueen(_n,_element,_try,_use,_result)_
Not(QueenCollides(element,try)) <--
[
Queens(SubtractN(n,1),element:try,use,result);
];
/* Recursive solve n-queens problem.*/
/* All queens checked, so add the result. */
10 # Queens( 0,_try,_touse,_result) <-- DestructiveInsert(result,1,try);
20 # Queens(_n,_try,_touse,_result) <--
[
Local(tailuse,i);
Local(nextuse);
Set(tailuse, touse);
Set(i, 1);
While(Not(Equals(tailuse, {})))
[
Set(nextuse,FlatCopy(touse));
DestructiveDelete(nextuse,i);
TryAddQueen(n, {n,Head(tailuse)}, try, nextuse, result );
Set(tailuse,Tail(tailuse));
Set(i, AddN(i,1));
];
];
|
