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