1/*
2 *	nqueens(N, Queens)
3 * 	Sterling & Shapiro program 14.2 p210
4 *
5 *	There is a bug in attack/3.
6 */
7
8:- module(nqueens).
9
10:- local select/3.
11
12getbug :- writeln('\nCheck that you are in "module(nqueens).", then'),
13	writeln('to start the program type "nqueens(4, Qs).".\n').
14
15bug :-
16	nl,
17	explanation.
18
19explanation :-
20writeln(' \n \
21 \n \
22N-1 should be N+1 in the last clause \n \
23Same bug as missing26, but in a simple  \n \
24generate and test context. \n \
25 \n \
26GOAL:	queens(4,Qs). \n \
27CORRECT: [3,1,4,2] ? ; \n \
28	 [2,4,1,3] ? ; \n \
29	 no (more) solutions \n \
30BUGGY: 	 no (more) solutions \n \
31').
32
33% ============================================================================
34
35nqueens(N, Qs) :-
36	range(1, N, Ns),
37	permutation(Ns, Qs),
38	safe(Qs).
39
40
41/*
42 *  range(M, N, Ns)
43 *  Ns is the list of integers between M and N inclusive
44 */
45range(M, N, [M|Ns]) :-
46	M < N,
47	M1 is M + 1,
48	range(M1, N, Ns).
49range(N,N,[N]).
50
51
52permutation(Xs, [Z|Zs]) :-
53	select(Z, Xs, Ys),
54	permutation(Ys, Zs).
55permutation([], []).
56
57
58/*
59 *  select(X, HasXs, OnelessXs) <-
60 *  The list OneLessXs is the result of removing
61 *  one occurence of X from the list HasXs.
62 */
63select(X, [X|Xs], Xs).
64select(X, [Y|Ys], [Y|Zs]) :-
65	select(X, Ys, Zs).
66
67/*
68 *  safe/1
69 */
70safe([Q|Qs]) :-
71	safe(Qs),
72	not attack(Q, Qs).
73safe([]).
74
75
76attack(X, Xs) :-
77	attack(X, 1, Xs).
78
79attack(X, N, [Y|_Ys]) :-
80	X is Y + N.
81attack(X, N, [Y|_Ys]) :-
82	X is Y - N.
83attack(X, N, [_Y|Ys]) :-
84	N1 is N - 1,		% fix: N1 is N + 1
85	attack(X, N1, Ys).
86
87