序言 - PCP求解

Question

我不知道是否有使用序言謂詞的（可以理解）的方式來蠻力解決郵政信件的問題？

例如：

?- pcp(["1","11"),("10111","101")], S). 
S = [2,1,1] 

Answer 1

好吧，這裏是一個可能的方案，該方案採用廣度優先搜索，找到越來越大的問題的解決方案。

1 ?- [user]. 

開始在大小的​​解決方案1 ​​

|: pcp(Ts,S) :- pcp(Ts,S,1). 

嘗試找到在當前大小的解決方案的搜索，如果你沒有找到一個嘗試下一個大小

|: pcp(Ts,S,N) :- pcp_solve(Ts,("",""),S,N). 
|: pcp(Ts,S,N) :- N2 is N+1, pcp(Ts,S,N2). 

如果你的正確尺寸的解決方案的結尾，字符串完全一致，那麼問題就解決了

|: pcp_solve(_,("",""),[],0). 

檢查解決方案

大步：獲得由字符串元組列表中的解決方案索引的元組元素，添加該元組中從最後一步弦弦，符合一切是相同的，至少留一個的字符串爲空，然後進入解決方案的下一部分。 （顯然，如果字符串不匹配在某些時候matchreduce會失敗。）

|: pcp_solve(Ts,A,[I|S],N) :- N>0, N2 is N-1, nth1(I,Ts,T), 
|: bothappend(A,T,AT), matchreduce(AT,ATr), pcp_solve(Ts,ATr,S,N2). 

這裏有謂詞的休息：

|: bothappend((A1,B1),(A2,B2),(A3,B3)) :- append(A1,A2,A3), append(B1,B2,B3). 
|: matchreduce(([],B),([],B)) :- !. 
|: matchreduce((A,[]),(A,[])). 
|: matchreduce(([X|A],[X|B]),(Ao,Bo)) :- matchreduce((A,B),(Ao,Bo)). 

追加和NTH1謂詞都在名單庫（SWI-Prolog），但可以輕鬆實現！

|: :- use_module(library(lists)). 
% library(error) compiled into error 0.01 sec, 9,640 bytes 
% library(lists) compiled into lists 0.03 sec, 22,996 bytes 
|: 
% user://1 compiled 0.12 sec, 25,600 bytes 
true. 

這是你的測試用例：

2 ?- pcp([("1","11"),("10111","101")], S). 
S = [2, 1, 1] ; 
S = [2, 1, 1, 2, 1, 1] ; 
S = [2, 1, 1, 2, 1, 1, 2, 1, 1] ; 
S = [2, 1, 1, 2, 1, 1, 2, 1, 1|...] . 

和一對夫婦從維基百科：

3 ?- pcp([("a","baa"),("ab","aa"),("bba","bb")], S). 
S = [3, 2, 3, 1] ; 
S = [3, 2, 3, 1, 3, 2, 3, 1] ; 
S = [3, 2, 3, 1, 3, 2, 3, 1, 3|...] . 

4 ?- pcp([("bb","b"),("ab","ba"),("c","bc")], S). 
S = [1, 3] ; 
S = [1, 2, 3] ; 
S = [1, 2, 2, 3] ; 
S = [1, 3, 1, 3] ; 
S = [1, 2, 2, 2, 3] ; 
S = [1, 2, 3, 1, 3] ; 
S = [1, 3, 1, 2, 3] ; 
S = [1, 2, 2, 2, 2, 3] ; 
S = [1, 2, 2, 3, 1, 3] ; 
S = [1, 2, 3, 1, 2, 3] ; 
S = [1, 3, 1, 2, 2, 3] ; 
S = [1, 3, 1, 3, 1, 3] ; 
S = [1, 2, 2, 2, 2, 2, 3] ; 
S = [1, 2, 2, 2, 3, 1, 3] ; 
S = [1, 2, 2, 3, 1, 2, 3] ; 
S = [1, 2, 3, 1, 2, 2, 3] ; 
S = [1, 2, 3, 1, 3, 1, 3] ; 
S = [1, 3, 1, 2, 2, 2, 3] ; 
S = [1, 3, 1, 2, 3, 1, 3] ; 
S = [1, 3, 1, 3, 1, 2, 3] ; 
S = [1, 2, 2, 2, 2, 2, 2, 3] ; 
S = [1, 2, 2, 2, 2, 3, 1, 3] ; 
S = [1, 2, 2, 2, 3, 1, 2, 3] ; 
S = [1, 2, 2, 3, 1, 2, 2, 3] ; 
S = [1, 2, 2, 3, 1, 3, 1, 3] ; 
S = [1, 2, 3, 1, 2, 2, 2, 3] ; 
S = [1, 2, 3, 1, 2, 3, 1, 3] ; 
S = [1, 2, 3, 1, 3, 1, 2, 3] ; 
S = [1, 3, 1, 2, 2, 2, 2, 3] ; 
S = [1, 3, 1, 2, 2, 3, 1, 3] ; 
S = [1, 3, 1, 2, 3, 1, 2, 3] ; 
S = [1, 3, 1, 3, 1, 2, 2, 3] ; 
S = [1, 3, 1, 3, 1, 3, 1, 3] ;