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  
 
 [ 3 post ] 

 Relevant Pages 

1. IP number change on fortress.uccb.ns.ca AKA w3.uccb.ns.ca

2. Problem compiling 'ns' using tcl7.6

3. what's wrong with my cin program?

4. What's wrong with this program?

5. Where am I wrong?(this has to be wrong, it can't be so simple)

6. What's wrong with this program??

7. program error -- what's wrong?

8. can anybody help me wht's wrong in my program

9. What's Wrong With My Program

10. What's wrong with this program

11. What's wrong with my little program ?

12. What's wrong with my program?

 

 
Powered by phpBB® Forum Software