取自加德纳的谜题
Puzzle taken from Gardner
我正在尝试解决 Prolog 中的以下难题:
Ten cells numbered 0,...,9 inscribe a 10-digit number such that each cell, say i, indicates the total number of occurrences of the digit i in this number. Find this number. The answer is 6210001000.
这是我在 Prolog 中写的,但我卡住了,我认为我的 ten_digit 谓词有问题:
%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).
我该如何解决这个难题?
检查 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.
这给了你一个解,也说明它是唯一的。
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 以一种特殊的方式运行...它将自由变量绑定到当前限制,然后检查不再有限制。
edit 添加剪辑,片段变得非常快:
...
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.
对不起,我忍不住了。这个问题也可以方便地表示为混合整数规划 (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 .
我正在尝试解决 Prolog 中的以下难题:
Ten cells numbered 0,...,9 inscribe a 10-digit number such that each cell, say i, indicates the total number of occurrences of the digit i in this number. Find this number. The answer is 6210001000.
这是我在 Prolog 中写的,但我卡住了,我认为我的 ten_digit 谓词有问题:
%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).
我该如何解决这个难题?
检查 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.
这给了你一个解,也说明它是唯一的。
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 以一种特殊的方式运行...它将自由变量绑定到当前限制,然后检查不再有限制。
edit 添加剪辑,片段变得非常快:
...
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.
对不起,我忍不住了。这个问题也可以方便地表示为混合整数规划 (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 .