Search code examples
prologzebra-puzzle

Prolog Logic Puzzle not working?

I have been working on this Prolog logic problem for awhile. It is getting incorrect results and it is taking awhile to run the program itself which is what concerns me more. The logic problem goes as follows:

Alex, Bret, Chris, Derek, Eddie, Fred, Greg, Harold, and John are nine students who live in a three story building, with three rooms on each floor. A room in the West wing, one in the centre, and one in the East wing. If you look directly at the building, the left side is West and the right side is East. Each student is assigned exactly one room. Can you find where each of their rooms is:

  1. Harold does not live on the bottom floor.
  2. Fred lives directly above John and directly next to Bret (who lives in the West wing).
  3. Eddie lives in the East wing and one floor higher than Fred.
  4. Derek lives directly above Fred.
  5. Greg lives directly above Chris.

Here is the code that I have written, that takes awhile to complete and gives incorrect results: 

rooms([west,center,east]).
floors([bottom,middle,top]). 

students([alex,bret,chris,derek,eddie,fred,greg,harold,john]).

student(S) :-
        students(L), member(S,L).

empty_building(building(floor(_,_,_),floor(_,_,_),floor(_,_,_))).

location(P,1,1,building(floor(P,_,_),_,_)).
location(P,1,2,building(floor(_,P,_),_,_)).
location(P,1,3,building(floor(_,_,P),_,_)).
location(P,2,1,building(_,floor(P,_,_),_)).
location(P,2,2,building(_,floor(_,P,_),_)).
location(P,2,3,building(_,floor(_,_,P),_)).
location(P,3,1,building(_,_,floor(P,_,_))).
location(P,3,2,building(_,_,floor(_,P,_))).
location(P,3,3,building(_,_,floor(_,_,P))).

puzzle_soln(BLDG) :-
    empty_building(BLDG), 
    location(harold,HFN,_,BLDG), 
    location(fred,FFN,FRN,BLDG), 
    location(john,JFN,JRN,BLDG),
    location(bret,BFN,BRN,BLDG),
    location(eddie,EFN,ERN,BLDG),
    location(derek,DFN,DRN,BLDG),
    location(greg,GFN,GRN,BLDG),
    location(chris,CFN,CRN,BLDG),
    location(alex,_,_,BLDG),        

    HFN \= 1,                           
    FFN is JFN + 1,                     
    FRN = JRN,
    1 =:= abs(FRN - BRN),               
    FFN = BFN,
    BRN is 1,                           
    ERN is 3,                           
    EFN is FFN + 1,                     
    DFN is FFN + 1,                      
    DRN = FRN,
    GFN is CFN + 1,                     
    GRN = CRN.

Here is a link to a site that has the problem and the solution: https://www.brainbashers.com/showpuzzles.asp?puzzle=ZQJZ

Any help would be appreciated.

Solution

  • You are getting the correct answer.

    ?- puzzle_soln(X).
X = building(floor(alex, john, chris), floor(bret, fred, greg), floor(harold, derek, eddie))

    same as this (counting floors from the bottom)

    West    Centre  East
====    ======  ====
Harold  Derek   Eddie
Bret    Fred    Greg
Alex    John    Chris

    If you want to speed it up you can interleave generation and testing:

    puzzle_soln(BLDG) :-
  empty_building(BLDG),
  BRN is 1,
  ERN is 3,
  location(harold,HFN,_,BLDG),
  HFN \= 1,
  location(fred,FFN,FRN,BLDG),
  location(john,JFN,JRN,BLDG),
  FFN is JFN + 1,
  EFN is FFN + 1,
  DFN is FFN + 1,
  FRN = JRN,
  location(bret,BFN,BRN,BLDG),
  1 =:= abs(FRN - BRN),
  FFN = BFN,
  location(eddie,EFN,ERN,BLDG),
  location(derek,DFN,DRN,BLDG),
  DRN = FRN,
  location(greg,GFN,GRN,BLDG),
  location(chris,CFN,CRN,BLDG),
  GFN is CFN + 1,
  GRN = CRN,
  location(alex,_,_,BLDG).

    Old version: 869,727 inferences, 0.533 CPU in 0.533 seconds

    New version: 310 inferences, 0.000 CPU in 0.000 seconds

    CLP(FD) solution: 61,356 inferences, 0.011 CPU in 0.011 seconds