Prolog - PCP solver

Question

I'm wondering if there's an (understandable) way to brute force solve Post correspondence problem using prolog predicates?

for example:

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

Answer 1

Ok, here's a possible program, which uses breadth first search, to find increasingly bigger solution to the problem.

1 ?- [user].

Start the search at solutions of size 1

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

Try finding a solution at the current size, and if you don't find one try the next size

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

If at the end of your solution of the correct size, the strings are matched completely then the problem is solved

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

Big step for checking the solution: get the tuple element indexed in the solution from the list of string tuples, append the strings in this tuple to the strings from the last step, match everything that's the same, leaving at least one of the strings empty, then go onto the next part of the solution. (Obviously, if the strings don't match at some point matchreduce will fail.)

|: 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).

Here are the rest of the predicates:

|: 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)).

The append and nth1 predicates are in the lists library (SWI-Prolog) but can be implemented easily!

|: :- 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.

Here's your test case:

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|...] .

And a couple from wikipedia:

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] ;