来自加德纳的拼图 [英] Puzzle taken from Gardner
问题描述
我正在尝试解决 Prolog 中的以下难题:
<块引用>编号为 0,...,9 的 10 个单元格刻有一个 10 位数字,这样每个单元格(例如 i)表示该数字中数字 i 出现的总次数.找到这个号码.答案是 6210001000.
这是我在 Prolog 中写的,但我被卡住了,我认为我的十位谓词有问题:
%count:用于统计一个元素在列表中出现的次数计数(_,[],0).计数(X,[X|T],N) :-计数(X,T,N2),N 是 1 + N2.计数(X,[Y | T],计数): -X \= Y,计数(X,T,计数).%check: f.e.position = 1,计算 1 在列表中出现的次数并检查它是否等于位置 1 处的值检查(位置,列表): -计数(位置,列表,计数),valueOf(Pos,List,X),X == 计数.%valueOf:从给定索引的列表中获取值valueOf(0,[H|_],H).valueOf(I,[_|T],Z) :-I2 是 I-1,valueOf(I2,T,Z).%ten_digit: 生成 10 位数字十位数(X):-十位数([0,1,2,3,4,5,6,7,8,9],X).十位数([],[]).十位数([Nul|Rest],Digits):-检查(空,数字),十位数字(休息,数字).
我该如何解决这个难题?
查看 clpfd 约束 global_cardinality/2
.
例如,使用 SICStus Prolog 或 SWI:
:- use_module(library(clpfd)).十个细胞(Ls):-numlist(0, 9, Nums),pair_keys_values(Pairs, Nums, Ls),global_cardinality(Ls, Pairs).
示例查询及其结果:
<预>?- 时间((ten_cells(Ls), labeling([ff], Ls))).1,359,367 次推理,0.124 秒内 0.124 CPU(100% CPU,10981304 唇)Ls = [6, 2, 1, 0, 0, 0, 1, 0, 0, 0];319,470 次推理,0.028 秒内 0.028 CPU(100% CPU,11394678 唇)假.这为您提供了一种解决方案,同时也表明它是独一无二的.
I'm trying to solve the following puzzle in 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.
This is what I wrote in Prolog but I'm stuck, I think there is something wrong with my ten_digit predicate:
%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).
How do I solve this puzzle?
Check out the clpfd constraint global_cardinality/2
.
For example, using SICStus Prolog or SWI:
:- use_module(library(clpfd)).
ten_cells(Ls) :-
numlist(0, 9, Nums),
pairs_keys_values(Pairs, Nums, Ls),
global_cardinality(Ls, Pairs).
Sample query and its result:
?- 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.
This gives you one solution, and also shows that it is unique.
这篇关于来自加德纳的拼图的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!