misconception about how prolog works

user_11333604 0
Viewed 125

So I am currently learning prolog and I can't get my head around how this language works. "It tries all the possible solutions until it finds one, if it doesn't it returns false" is what I've read that this language does. You just Describe the solution and it finds it for you

With that in mind, I am trying to solve the 8 queens problem ( how to place 8 queens on a chess board without anyone threatening the others). I have this predicate, 'safe' that gets a list of pairs, the positions of all the queens and succeeds when they are not threatening each other.

When I enter in the terminal

 ?- safe([(1,2),(3,5)]).
true ?
| ?- safe([(1,3),(1,7)]).
no
| ?- safe([(2,2),(3,3)]).
no
| ?- safe([(2,2),(3,4),(8,7)]).
true ?

it recognizes the correct from the wrong answers, so it knows if something is a possible solution

BUT

when I enter

| ?- safe(L).

L = [] ? ;

L = [_] ? ;

it gives me the default answers, even though it recognizes a solution for 2 queens when I enter them.

here is my code

threatens((_,Row),(_,Row)).
threatens((Column,_),(Column,_)).
threatens((Column1,Row1),(Column2,Row2)) :-
    Diff1 is Column1 - Row1,
    Diff2 is Column2 - Row2,
    abs(Diff1) =:= abs(Diff2).

safe([]).
safe([_]).

safe([A,B|T]) :-
    \+ threatens(A,B),
    safe([A|T]),
    safe(T).

One solution I found to the problem is to create predicates 'position' and modify the 'safe' one

possition((0,0)).
possition((1,0)).
...
...
possition((6,7)).
possition((7,7)).

safe([A,B|T]) :-
    possition(A),
    possition(B),
    \+ threatens(A,B),
    safe([A|T]),
    safe(T).

safe(L,X):-
    length(L,X),
    safe(L).

but this is just stupid, as you have to type everything explicitly and really really slow, even for 6 queens.

My real problem here, is not with the code itself but with prolog, I am trying to think in prolog, But all I read is Describe how the solution would look like and let it work out what is would be Well that's what I have been doing but it does not seem to work, Could somebody point me to some resources that don't teach you the semantics but how to think in prolog Thank you

prolog
3 Answers

but this is just stupid, as you have to type everything explicitly and really really slow, even for 6 queens.

Regarding listing the positions, the two coordinates are independent, so you could write something like:

position((X, Y)) :-
    coordinate(X),
    coordinate(Y).

coordinate(1).
coordinate(2).
...
coordinate(8).

This is already much less typing. It's even simpler if your Prolog has a between/3 predicate:

coordinate(X) :-
    between(1, 8, X).

Regarding the predicate being very slow, this is because you are asking it to do too much duplicate work:

safe([A,B|T]) :-
    ...
    safe([A|T]),
    safe(T).

Once you know that [A|T] is safe, T must be safe as well. You can remove the last goal and will get an exponential speedup.

user_43917430

Describe how the solution would look like and let it work out what is would be

demands that the AI be very strong in general. We are not there yet.

You are on the right track though. Prolog essentially works by enumerating possible solutions and testing them, rejecting those that don't fit the conditions encoded in the program. The skill resides in performing a "good enumeration" (traversing the domain in certain ways, exploiting domain symmetries and overlaps etc) and subsequent "fast rejection" (quickly throwing away whole sectors of the search space as not promising). The basic pattern:

findstuff(X) :- generate(X),test(X).

And evidently the program must first generate X before it can test X, which may not be always evident to beginners.

Logic-wise,

findstuff(X) :- x_fulfills_test_conditions(X),x_fullfills_domain_conditions(X).

which is really another way of writing

findstuff(X) :- test(X),generate(X).

would be the same, but for Prolog, as a concrete implementation, there would be nothing to work with.

That X in the program always stands for a particular value (which may be uninstantiated at a given moment, but becomes more and more instantiated going "to the right"). Unlike in logic, where the X really stands for an unknown object onto which we pile constraints until -ideally- we can resolve X to a set of concrete values by applying a lot of thinking to reformulate constraints.

Which brings us the the approach of "Constraint Logic Programming (over finite domains)", aka CLP(FD) which is far more elegant and nearer what's going on when thinking mathematically or actually doing theorem proving, see here:

https://en.wikipedia.org/wiki/Constraint_logic_programming

and the ECLiPSe logic programming system

http://eclipseclp.org/

and

This is still technically Prolog (in fact, implemented on top of Prolog) but allows you to work on a more abstract level than raw generate-and-test.

user_8844630

Prolog is radically different in its approach to computing. Arithmetic often is not required at all. But the complexity inherent in a solution to a problem show up in some place, where we control how relevant information are related.

place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-place_queen(I,Cs,Us,Ds).

place_queens([],_,_,_).
place_queens([I|Is],Cs,Us,[_|Ds]):-
  place_queens(Is,Cs,[_|Us],Ds),
  place_queen(I,Cs,Us,Ds).

gen_places([],[]).
gen_places([_|Qs],[_|Ps]):-gen_places(Qs,Ps).

qs(Qs,Ps):-gen_places(Qs,Ps),place_queens(Qs,Ps,_,_).

goal(Ps):-qs([0,1,2,3,4,5,6,7,8,9,10,11],Ps).

No arithmetic at all, columns/rows are encoded in a clever choice of symbols (the numbers indeed are just that, identifiers), diagonals in two additional arguments.

The whole program just requires a (very) small subset of Prolog, namely a pure 2-clauses interpreter.

If you take the time to understand what place_queens/4 does (operationally, maybe, if you have above average attention capabilities), you'll gain a deeper understanding of what (pure) Prolog actually computes.

user_8740240
Related