时间戳

首页 > 解决方案 > 简化 CLP 难题中的约束

prolog - 简化 CLP 难题中的约束

问题描述

在当地的游戏之夜，四个小伙子正在参加拼字游戏和国际象棋比赛。利亚姆在国际象棋中击败了马克，詹姆斯获得第三名，16 岁的小伙子获胜。利亚姆在拼字游戏中排名第二，15 岁获胜，詹姆斯击败 18 岁，19 岁获得第三。凯文比马克小 3 岁。在国际象棋中排名最后的人在拼字游戏中排名第三，并且只有一个小伙子在两场比赛中获得相同的位置。

我觉得我的解决方案比需要的更笨重：

:- use_module(library(clpfd)).

check(AJ, AK, AL, AM, CJ, CK, CL, CM, SJ, SK, SL, SM) :-
    AJ in 15..16 \/ 18..19,
    AK in 15..16 \/ 18..19,
    AL in 15..16 \/ 18..19,
    AK in 15..16 \/ 18..19,
    all_different([AJ, AK, AL, AM]),
    CJ in 1..4, CK in 1..4, CL in 1..4, CM in 1..4,
    SJ in 1..4, SK in 1..4, SL in 1..4, SM in 1..4,
    all_different([CJ, CK, CL, CM]),
    all_different([SJ, SK, SL, SM]),
    CL #< CM,
    CJ #= 3,
  ( AJ #= 16, CJ #= 1 ;
    AK #= 16, CK #= 1 ;
    AL #= 16, CL #= 1 ;
    AM #= 16, CM #= 1 ),
    SL #= 2,
  ( AJ #= 15, SJ #= 1 ;
    AK #= 15, SK #= 1 ;
    AL #= 15, SL #= 1 ;
    AM #= 15, SM #= 1 ),
    AK #= AM - 3,
  ( CJ #= 4, SJ #= 3 ;
    CK #= 4, SK #= 3 ;
    CL #= 5, SL #= 3 ;
    CM #= 4, SM #= 3 ),
  ( CJ #=  SJ, CK #\= SK, CL #\= SL, CM #\= SM ;
    CJ #\= SJ, CK #=  SK, CL #\= SL, CM #\= SM ;
    CJ #\= SJ, CK #\= SK, CL #=  SL, CM #\= SM ;
    CJ #\= SJ, CK #\= SK, CL #\= SL, CM #=  SM ).

有没有更好的方法来表达约束？

建议后的改进版本：

:- use_module(library(clpfd)).

check(AJ, AK, AL, AM, CJ, CK, CL, CM, SJ, SK, SL, SM) :-
    permutation([AJ, AK, AL, AM], [15, 16, 18, 19]),
    permutation([CJ, CK, CL, CM], [1, 2, 3, 4]),
    permutation([SJ, SK, SL, SM], [1, 2, 3, 4]),
    CL #< CM,
    CJ #= 3,
  ( AJ #= 16, CJ #= 1 ;
    AK #= 16, CK #= 1 ;
    AL #= 16, CL #= 1 ;
    AM #= 16, CM #= 1 ),
    SL #= 2,
  ( AJ #= 15, SJ #= 1 ;
    AK #= 15, SK #= 1 ;
    AL #= 15, SL #= 1 ;
    AM #= 15, SM #= 1 ),
    AK #= AM - 3,
  ( CJ #= 4, SJ #= 3 ;
    CK #= 4, SK #= 3 ;
    CL #= 5, SL #= 3 ;
    CM #= 4, SM #= 3 ),
  ( CJ #=  SJ, CK #\= SK, CL #\= SL, CM #\= SM ;
    CJ #\= SJ, CK #=  SK, CL #\= SL, CM #\= SM ;
    CJ #\= SJ, CK #\= SK, CL #=  SL, CM #\= SM ;
    CJ #\= SJ, CK #\= SK, CL #\= SL, CM #=  SM ).

标签： prologclpfdzebra-puzzle

解决方案

这是一个 SWI-Prolog 版本，使用全局约束element/3来访问/查找来自不同列表的索引/值。（可以将此模型视为element/3:-) 中的练习。）

:- use_module(library(clpfd)).

go :-
        % At the local games evening, four lads were competing in the Scrabble and 
        % chess competitions.
        N = 4,
        length(Lads,N),
        Lads = [James,Kevin,Liam,Mark],
        Lads = [1,2,3,4],
        Lads ins 1..N,
        LadsS = ['James','Kevin','Liam','Mark'],
        
        length(Chess,N),
        Chess ins 1..N,
        
        length(Scrabble,N),
        Scrabble ins 1..N,

        length(Ages,N),
        Ages ins 15..16 \/ 18..19,

        all_different(Chess),
        all_different(Scrabble),
        all_different(Ages),

        element(Ages15,Ages,15),
        element(Ages16,Ages,16),
        element(Ages18,Ages,18),
        element(Ages19,Ages,19),
        
        % Liam beat Mark in chess, James came third and the 16 year old won.
        element(Liam,Chess,ChessLiam),
        element(Mark,Chess,ChessMark),
        ChessLiam #< ChessMark,
        element(James,Chess,3),
        element(Ages16,Chess,1),

        % Liam came second in Scrabble, the 15 year old won; James beat the 18 year old 
        % and the 19 year old came third.
        element(Liam,Scrabble,2),
        element(Ages15,Scrabble,1),

        element(Ages18,Scrabble,ScrabbleAges18),
        element(James,Scrabble,ScrabbleJames),
        ScrabbleJames #< ScrabbleAges18,
        element(Ages19,Scrabble,3),

        % Kevin is 3 years younger than Mark.
        element(Kevin,Ages,AgesKevin),
        element(Mark,Ages,AgesMark),  
        AgesKevin + 3 #= AgesMark,
        
        % The person who came last in chess, came third in Scrabble and only one lad
        % got the same position in both games.
        element(ChessPlace4,Chess,4),
        element(ChessPlace4,Scrabble,3),

        sums(Chess,Scrabble,0,Sums),
        Sums #= 1,
        
        % Can you determine the ages of the lads and the positions in the two games?

        flatten([Chess,Scrabble,Ages,Sums],Vars),
        label(Vars),
        
        writeln(chess=Chess),
        writeln(scrabble=Scrabble),
        writeln(ages=Ages),
        sol(LadsS,Ages,Scrabble,Chess),
        nl,
        
        fail,
        nl.
go.


sums([],[],Total,Total).
sums([C|Chess],[S|Scrabble],Total0,Total) :-
        B in 0..1,
        C #= S #<==> B #= 1,
        Total1 #= Total0 + B,         
        sums(Chess,Scrabble,Total1,Total).

sol([L|Lads],[A|Ages],[S|Scrabble],[C|Chess]) :-
        format("~w (~d) Scrabble: ~d Chess: ~d~n",[L,A,S,C]),
        sol(Lads,Ages,Scrabble,Chess).

（完整程序可在此处获得：http: //hakank.org/swi_prolog/scrabble_contest.pl）

推荐阅读