Solving and debugging a logic puzzle in Prolog

Question

I'm trying to solve the following logic puzzle using Prolog:

Determine the first and last name of each driver in the race, the sponsor for each race car, and in what position each driver ended the race.

The driver sponsored by Flash Automotive finished the race in third place. Howard, who wasn’t sponsored by Crank Motor Oil, didn’t finish the race in fifth place.
Ryan, whose last name wasn’t Right, wasn’t sponsored by NAPA Auto Parts. Barry Straight wasn’t sponsored by Fleet Bodyworks.
The driver sponsored by Crank Motor Oil placed one position higher than Sydney, whose last name wasn’t Element.
Mr. Chariot, whose first name wasn’t Adam, finished in first place. Howard placed one position lower than Mr. Right.
NAPA Auto Parts sponsored the driver who finished in fourth place, which wasn’t Barry.
The five drivers, in no particular order, are Adam, the second place driver, the driver sponsored by Tredco Tires, Mr. Right, and Mr. Rafe.

Using a similar approach as the one found here: http://www.anselm.edu/internet/compsci/faculty_staff/mmalita/HOMEPAGE/logic/aa6.txt

I came up with the following answer:

    race(Drivers) :- Drivers = [[howard,_,_,_],[barry,_,_,_],[ryan,_,_,_],
        [sydney,_,_,_],[adam,_,_,_],[_,straight,_,_],[_,chariot,_,_],
        [_,right,_,_],[_,element,_,_],[_,rafe,_,_],[_,_,flashautomotive,_],
        [_,_,crankmotoroil,_],[_,_,napaautoparts,_],[_,_,fleetbodyworks,_],
        [_,_,tredcotires,_],[_,_,_,1],[_,_,_,2],[_,_,_,3],[_,_,_,4],[_,_,_,5]],
        member([barry,straight,C,D], Drivers), C \= fleetbodyworks, 
            C \= napaautoparts, D \= 4,
        member([howard,_,G,H], Drivers), G \= crankmotoroil, H \= 5, H =:= X - 1,
        member([ryan,J,K,_], Drivers), J \= right, K \= napaautoparts,
        member([sydney,N,_,P], Drivers), N \= element,
        member([Q,chariot,_,T], Drivers), Q \= adam, T = 1,
        member([_,right,_,X], Drivers),
        member([_, _, _, crankmotoroil, DD], Drivers), DD =:= P + 1,
        member([EE,_,napaautoparts,HH], Drivers), HH = 4, EE \= barry,
        member([_,_,flashautomotive,LL], Drivers), LL = 3.

When loading this into the Windows SWI-Prolog IDE, it gives no errors, but while debugging it produces this result:

[debug] [1] 12 ?- race(X)
|    .
    T Call: (13) race(_G4168)
    T Fail: (13) race(_G4168)
false.

I'm obviously quite new to Prolog, but I'm wondering what might be causing this to fail and how to fix it (because the debugger as I understand how to use it is not very helpful in this instance). Also, is there a cleaner way to solve similar logic problems?

CapelliC CapelliC · Accepted Answer · 2015-12-12T10:05:15

Your representation of the 'search space' is not correct: in the example you linked, note that only one of the value slots is bound to a constant. Such constant will serve effectively to identify other variable elements after they get their correct place given the constraints.

Moreover, let Prolog applies the 'permutation game' performed by various member/2, and only after check for identities, differences, etc... After you get a solution, you can try to optimize the search process moving up the check, but always after the pertinent slots have been assigned...

A good choice would be to use the numeric field, so you can apply arithmetic in obvious way to enforce constraints. So, I tried to modify your code:

race(Drivers) :-
    Drivers = [
        [_,_,_,1],
        [_,_,_,2],
        [_,_,_,3],
        [_,_,_,4],
        [_,_,_,5]
    ],
        member([barry,straight,C,D], Drivers),
        member([howard,_,G,H], Drivers),
        member([ryan,J,K,_], Drivers),
        member([sydney,N,_,P], Drivers),
        member([Q,chariot,_,T], Drivers),
        member([_,right,_,X], Drivers),
        member([_,_,crankmotoroil,DD], Drivers),
        member([EE,_,napaautoparts,HH], Drivers),
        member([_,_,flashautomotive,LL], Drivers),

    C \= fleetbodyworks, C \= napaautoparts, D \= 4,
    G \= crankmotoroil, H \= 5, H =:= X - 1,
    J \= right, K \= napaautoparts,
    N \= element,
    Q \= adam, T = 1,
%   DD =:= P + 1,
    HH = 4, EE \= barry,
    LL = 3.

Note the comment line: if you uncomment it, no solution is available... Commenting out restrictions is the simpler debugging tool available for this simple minded schema.

Solving and debugging a logic puzzle in Prolog

2 Answers