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

取自加德纳的拼图

constraint-programming clpfd prolog

2

Stanko · 技术社区 · 8 年前

我试图用Prolog解决以下难题:

编号为0、…、9的十个单元格内接一个10位数字,这样每个单元格(例如i)表示该数字中数字i出现的总数。找到这个号码。答案是6210001000。

这是我在Prolog中写的,但我被卡住了,我认为我的十位数谓词有问题:

%count: used to count number of occurrence of an element in a list

count(_,[],0).
count(X,[X|T],N) :-
    count(X,T,N2),
    N is 1 + N2.
count(X,[Y|T],Count) :-
    X \= Y,
    count(X,T,Count).

%check: f.e. position = 1, count how many times 1 occurs in list and check if that equals the value at position 1
check(Pos,List) :-
    count(Pos,List,Count),
    valueOf(Pos,List,X),
    X == Count.

%valueOf: get the value from a list given the index
valueOf(0,[H|_],H).
valueOf(I,[_|T],Z) :-
    I2 is I-1,
    valueOf(I2,T,Z).

%ten_digit: generate the 10-digit number    
ten_digit(X):-
    ten_digit([0,1,2,3,4,5,6,7,8,9],X).

ten_digit([],[]).
ten_digit([Nul|Rest],Digits) :-
    check(Nul,Digits),
    ten_digit(Rest,Digits).

我如何解决这个难题?

3 回复 | 直到 8 年前

1

4

mat 8 年前

查看 clpfd 限制 global_cardinality/2 .

例如,使用SICStus Prolog或SWI:

:- use_module(library(clpfd)).

ten_cells(Ls) :-
        numlist(0, 9, Nums),
        pairs_keys_values(Pairs, Nums, Ls),
        global_cardinality(Ls, Pairs).

示例查询及其结果:

?- time((ten_cells(Ls), labeling([ff], Ls))).
1,359,367 inferences, 0.124 CPU in 0.124 seconds (100% CPU, 10981304 Lips)
Ls = [6, 2, 1, 0, 0, 0, 1, 0, 0, 0] ;
319,470 inferences, 0.028 CPU in 0.028 seconds (100% CPU, 11394678 Lips)
false.

这为您提供了一个解决方案,同时也表明了它的独特性。

2

CapelliC 8 年前

CLP(FD)规则……用简单的Prolog解决这个难题并不容易。。。

ten_digit(Xs):-
    length(Xs, 10),
    assign(Xs, Xs, 0).

assign([], _, 10).
assign([X|Xs], L, P) :-
    member(X, [9,8,7,6,5,4,3,2,1,0]),
    count(L, P, X),
    Q is P+1,
    assign(Xs, L, Q),
    count(L, P, X).

count(L, P, 0) :- maplist(\==(P), L).
count([P|Xs], P, C) :-
    C > 0,
    B is C-1,
    count(Xs, P, B).
count([X|Xs], P, C) :-
    X \== P,
    C > 0,
    count(Xs, P, C).

这远不如@mat解决方案有效:

?- time(ten_digit(L)),writeln(L).
% 143,393 inferences, 0.046 CPU in 0.046 seconds (100% CPU, 3101601 Lips)
[6,2,1,0,0,0,1,0,0,0]
L = [6, 2, 1, 0, 0, 0, 1, 0, 0|...] ;
% 11,350,690 inferences, 3.699 CPU in 3.705 seconds (100% CPU, 3068953 Lips)
false.

count/3以一种特殊的方式起作用…它将自由变量绑定到当前限制,然后检查不再有界。

编辑添加一个片段,片段变得非常快:

...
assign(Xs, L, Q),
!, count(L, P, X).

?- time(ten_digit(L)),writeln(L).
% 137,336 inferences, 0.045 CPU in 0.045 seconds (100% CPU, 3075529 Lips)
[6,2,1,0,0,0,1,0,0,0]
L = [6, 2, 1, 0, 0, 0, 1, 0, 0|...] ;
% 3 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 54706 Lips)
false.

3

1

Erwin Kalvelagen 8 年前

对不起,我无法抗拒。这个问题也可以方便地表示为混合整数规划(MIP)模型。比Prolog更像一点。

结果相同:

---- VAR n  digit i

              LOWER          LEVEL          UPPER         MARGINAL

digit0        -INF            6.0000        +INF             .          
digit1        -INF            2.0000        +INF             .          
digit2        -INF            1.0000        +INF             .          
digit3        -INF             .            +INF             .          
digit4        -INF             .            +INF             .          
digit5        -INF             .            +INF             .          
digit6        -INF            1.0000        +INF             .          
digit7        -INF             .            +INF             .          
digit8        -INF             .            +INF             .          
digit9        -INF             .            +INF             .