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.

2 answers

  • answered 2018-04-17 04:51 joel76

    CLP(FD) is usefull for this puzzle :

    :- use_module(library(clpfd)).
    %
    %   7 8 9
    %   4 5 6
    %   1 2 3
    solve(L) :-
        L = [A, B, C, D, E, F ,G, H, J],
        L ins 1..9,
        all_distinct(L),
        % 1. Harold does not live on the bottom floor.
        H #> 3,
        % 2. Fred lives directly above John and directly next to Bret
        % (who lives in the West wing).
        F #= J + 3,
        B #= F - 1,
        B in 1 \/ 4 \/ 7,
        % 3. Eddie lives in the East wing and one floor higher than Fred.
        E #> F,
        E in 3 \/ 6 \/ 9,
        (   (   F in 1..3 #<==> E in 4..6) #\/ (  F in 4..6 #<==> E in 7..9)),
        % answer edited after Mat's remark
        % (   (   F in 1..3 #<==> E in 4..6) ; (  F in 4..6 #<==> E in 7..9)),
        % 4. Derek lives directly above Fred.
        D #= F + 3,
        % 5. Greg lives directly above Chris.
        G #= C + 3,
        label(L).
    

    Which gives the solution(unfortunately 2 times !)

    EDIT now, only one solution !

    ?- solve( [A, B, C, D, E, F ,G, H, J]).
    A = 1,
    B = 4,
    C = 3,
    D = 8,
    E = 9,
    F = 5,
    G = 6,
    H = 7,
    J = 2.
    

  • answered 2018-04-17 04:51 Tomas By

    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