代码之家 › 专栏 › 技术社区 › MasterYork42

Prolog逻辑难题不起作用?

zebra-puzzle prolog

MasterYork42 · 技术社区 · 6 年前

我一直在研究这个Prolog逻辑问题有一段时间了。它得到了错误的结果,运行程序本身需要一段时间,这是我更关心的。逻辑问题如下:

亚历克斯、布雷特、克里斯、德里克、埃迪、弗雷德、格雷格、哈罗德和约翰是九名学生,他们住在一栋三层楼的大楼里,每层楼有三个房间。一个房间在西翼,一个在中央,一个在东翼。如果你直视大楼,左边是西,右边是东。每个学生只分配一个房间。你能找到他们每个房间的位置吗:

哈罗德不住在底层。
弗雷德住在约翰的正上方,与布雷特(住在西翼)紧挨着。
埃迪住在东翼,比弗雷德高一层。
德里克住在弗雷德的正上方。
格雷格住在克里斯的正上方。

以下是我编写的代码,它需要一段时间才能完成,并给出错误的结果:

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.

以下是指向存在问题和解决方案的站点的链接: https://www.brainbashers.com/showpuzzles.asp?puzzle=ZQJZ

任何帮助都将不胜感激。

2 回复 | 直到 6 年前

Tomas By 6 年前

你得到了正确的答案。

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

与此相同(从底部数楼层)

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

如果要加快速度,可以交错生成和测试:

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).

旧版本:869727推断,0.533秒0.533 CPU

新版本:310推论,0.000秒0.000 CPU

CLP(FD)解决方案:61356个推论,0.011秒0.011 CPU

joel76 6 年前

CLP(FD)可用于此谜题:

:- 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).

这就给出了解决方案(不幸的是2次!)

编辑现在,只有一个解决方案!

?- 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.