CODEWITHSUNDEEP
prolog
PopKernel
PopKernel

Reputation: 4270

Prolog gives up after failing once?

I'm still learning Prolog so forgive me if I make some basic error here. I've added annotations to explain what I think the code is doing, in case I'm wrong. Forgive me if I'm explaining the obvious in places.

n_queens(NumQueens, Answer) :-
        length(Answer, NumQueens), %Answer must be a list of length NumQueens
        queens_are_safe(Answer). %All queens in Answer must be safe       

queens_are_safe([]). %If there are no queens, nobody's in danger
queens_are_safe([Queen | Queens]) :-
        queen_is_safe(Queen, Queens), %Is the queen safe from her peers?
        queens_are_safe(Queens). %Recursively check the other queens

queen_is_safe(_, []).
queen_is_safe(NewQueen, [Queen | Queens]) :-
        not(same_column(NewQueen, Queen)),
        not(same_row(NewQueen, Queen)),
        not(diagonal(NewQueen, Queen)),
        queen_is_safe(NewQueen, Queens). %Recursively ensure NewQueen is safe from other queens

diagonal(X/Y, X1/Y1) :- Y1 - Y = X1 - X. %If the X and Y deltas are equal, arguments are diagonal
same_column(X/_, X/_). %If the X coordinates are the same, it's the same column.
same_row(_/Y, _/Y). %If the Y coordinates are the same, it's the same row.

What I expect Prolog to do is generate a list of Queens, bind it to Answer, and repeat until it finds a list of values that satisfy all the conditions. E.g, if NumQueens is 2, it would test [0/0, 0/0], then [1/0, 0/0], and so forth.

However I suspect I'm very wrong here. The trace stack fails here:

Exit: (12) samecolumn(_15108/_15110, _15108/_15116) ? creep
Fail: (11) not(user:samecolumn(_15048, _15054)) ? creep

Clearly the problem is it uses the _15108 as the X values for same_column. I'd expect it to then try same_column but with different values for X. But it doesn't try again, it fails and returns false for the query n_queens(8,Ans). Why is this?

Upvotes: 0

Views: 174

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

I get the following error when trying to run your code in SWI-Prolog:

?- n_queens(8, Ans).
ERROR: not/1: Undefined procedure: samecolumn/2
ERROR:   However, there are definitions for:
ERROR:         same_column/2

Are you using a Prolog that silently fails when trying to call an undefined predicate? You shouldn't, or you should configure it to throw an error in that case. For example in YAP the default behavior is the broken one you see:

   ?- n_queens(8, Ans).
no

But you can fix it like this:

   ?- set_prolog_flag(unknown, error).
yes
   ?- n_queens(8, Ans).
     ERROR!!
     EXISTENCE ERROR- procedure samecolumn/2 is undefined, called from context  prolog:$query/2
                 Goal was user:samecolumn(_131242,_131243)

Edit: Just to make this explicit, as the messages show, one of the immediate problems is thus that you are trying to call a predicate samecolumn/2 which is not defined; you probably meant to call same_column/2.

After this, the code will still not be correct due to the goal Y1 - Y = X1 - X in diagonal/2. You would probably want diagonal(2/3, 3/4) to succeed, for example, but the goal 4 - 3 = 3 - 2 does not succeed in Prolog:

?- 4 - 3 = 3 - 2.
false.

This is because Prolog does not treat terms like 4 - 3 as arithmetic expressions to evaluate to a number like 1. You probably want the =:= operator which evaluates both operands to numbers and then compares those:

?- 4 - 3 =:= 3 - 2.
true.

But even after all this, this code will not work. Your program never specifies anywhere that the variables in the Queens should be bound to integers 1 to NumQueens. Prolog doesn't just make up these numbers for you! You might want to look into constraint programming with clpfd.

Upvotes: 1

Related Questions