What's wrong with this N queens program?
Author Message What's wrong with this N queens program?

I can't seem to get this program working, or rather, it sort of works,
but not for the general case.  Anyone care to look at it?

If I ask queens(4,[2,4,1,3]).    it knows that's true.
but if I ask queens(4,_).        it recurses in safe() until the stack
overflows.
John

queens(N,Qs):-
range(1,N,Ns),
permutation(Ns,Qs),
safe(Qs).

safe([Q|Qs]):-
safe(Qs),
not(attack(Q,Qs)).
safe([]).

attack(X,Xs):-
attack(X,1,Xs).
attack(X,N,[Y|Ys]):-
X is Y + N;
X is Y - N.
attack(X,N,[Y|Ys]):-
N1 is N + 1,
attack(X,N1, Ys).

permutation(Xs,[Z|Zs]):-
select(Z,Xs,Ys).
permutation(Ys,Zs).
permutation([],[]).

select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):-
select(X,Ys,Zs).

range(M,N,[M|Ns]):-
M<N,
M1 is M + 1,
range(M1,N,Ns).
range(N,N,[N]).

Mon, 14 Aug 1995 17:39:47 GMT  What's wrong with this N queens program?

Here is a fixed version of the queens program you posted.  It works.
The fix was that a . should be replaced by a , in permutation/2
(marked below).  Better indentation made it possible to find the bug.

% For SICStus
not(X) :- \+call(X).

queens(N,Qs):-
range(1,N,Ns),
permutation(Ns,Qs),
safe(Qs).

safe([Q|Qs]):-
safe(Qs),
not(attack(Q,Qs)).
safe([]).

attack(X,Xs):-
attack(X,1,Xs).
attack(X,N,[Y|Ys]):-
X is Y + N;
X is Y - N.
attack(X,N,[Y|Ys]):-
N1 is N + 1,
attack(X,N1, Ys).

permutation(Xs,[Z|Zs]):-
select(Z,Xs,Ys),                     % <- Here
permutation(Ys,Zs).
permutation([],[]).

select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):-
select(X,Ys,Zs).

range(M,N,[M|Ns]):-
M<N,
M1 is M + 1,
range(M1,N,Ns).
range(N,N,[N]).
--
Roland Karlsson             SICS, PO Box 1263, S-164 28 KISTA, SWEDEN

Telex: 812 6154 7011 SICS   Ttx: 2401-812 6154 7011=SICS

Mon, 14 Aug 1995 21:14:16 GMT  What's wrong with this N queens program?
I can't seem to get this program working, or rather, it sort of works,
but not for the general case.  Anyone care to look at it?

If I ask queens(4,[2,4,1,3]).    it knows that's true.
but if I ask queens(4,_).        it recurses in safe() until the stack
overflows.
John

queens(N,Qs):-
range(1,N,Ns),
permutation(Ns,Qs),
safe(Qs).

safe([Q|Qs]):-
safe(Qs),
not(attack(Q,Qs)).
safe([]).

attack(X,Xs):-
attack(X,1,Xs).
attack(X,N,[Y|Ys]):-
X is Y + N;
X is Y - N.
attack(X,N,[Y|Ys]):-
N1 is N + 1,
attack(X,N1, Ys).

permutation(Xs,[Z|Zs]):-
select(Z,Xs,Ys).
^^^
permutation(Ys,Zs).
permutation([],[]).

select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]):-
select(X,Ys,Zs).

range(M,N,[M|Ns]):-
M<N,
M1 is M + 1,
range(M1,N,Ns).
range(N,N,[N]).

That should be a comma.

Antonis.

===================================================================
Antonis Kotzamanidis                    Tel: 071 589 5111 Ext. 7524
Research Student                                     Room : WPL 209
Department Of Computing                         Fax : (71) 589 7127
Imperial College

London SW7 2BZ
ENGLAND
===================================================================

Mon, 14 Aug 1995 21:17:40 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages

Powered by phpBB® Forum Software