Something About Post Correspondence Problem

The post correspondence problem was first introduced by Emil Post in 1946. It was defined as follows: Suppose you have an infinite number of different kinds of dominoes. There are two non-empty alphabet strings on the two sides (top and bottom) of each domino. What you need to do is to place dominoes side by side so that the combination of strings on each side are same.

There’s an example:

Dominoes	Top	Bottom
D1	a	baa
D2	ab	aa
D3	bba	bb

One solution would be (D3, D2, D3, D1), which makes the combination of the top and the bottom side of this set of dominoes are both “bbaabbbaa”.

Obviously, there is no efficient algorithm to solve the post correspondence problem. We can only find a proper answer by exhaustive search. However, there is still no break point for us to show where we can terminate the search process.

Also, DFS doesn’t work well on this problem because of the reason above. One algorithm we can apply is BFS, but how can we store the states?

The most common thought is to store the combinations on the top and bottom as follow:

1
2
3

class QueueElement(object):
    top = ""
    bottom = ""

But can you imagine how big a queue we need to store the state space, even in the easiest example above?

A better way to define a state is to be either the part of the bottom that goes past the top or vice versa. Since we only need to find one solution, the combinations “abba/abbaab” and “ac/acab” can be consider the same because what we need is a “ab” on bottom, and any sequence that can be added after “abba/abbaab” can also be added after “ac/acab”.

In this way, the state space becomes extremely smaller than before, which makes a great progress to search more sequences. However, the better state space cannot help us solve this problem perfectly. We need to combine BFS with iterative deepening to get closer to an answer.

Thus, to try my best to find an answer to the post correspondence problem, the program should be divided into two stages:

Use BFS to generate as many as possible states within the limit of memory.
Use iterative deepening starting from the frontier created in the first stage.

Reference