A Surprisingly Hard Problem (Post Correspondence)
loopycode.com
loopycode.com
So the first thing which comes to my mind: This is unsolveable unless there is some tricky way to reduce the problem somehow to a simpler (finite) one.
As it was proven, there is no such way in this case.
Looking at a, the first tile has an excess of one a in the bottom, as does the second tile. The third tile has an excess of one a in the top. Hence, we can conclude that half the tiles in any solution must be the third. Looking at b, the first tile has an excess b in the bottom, the second has an excess b in the top, and the third is balanced. Hence, the first tile and the second tile must be used in equal numbers.
For the second example, with just two tiles (a/baa and ab/aa), note that each tile introduces an excess a in the bottom, and so it is immediate that there is no possible solution.
So, just by a counting argument in th second example, we've reduced the number of possibilities we need to exam to zero. For the first example, the counting argument doesn't eliminate the possiblity of a solution, but at least gives us some information about the distribution of tiles in any possible solution (1/4 #1, 1/4 #2, 1/2 #3).
For some sets, you can also use counting arguments on the length of strings on the tiles. For the second exampl, not that the first tile makes the bottom string longer by 3 and the top string longer by 1. The second tile extends both strings equally. Hence, any solution must consist entirely of repitions of the second tile, or the strings won't come out the same length. But the top and bottom strings aren't the same on #2, so that won't work. No solution is possible.
The second trick is to realize that in any solution, if you take the first N tiles, then either the two strings must be the same, or one of them must be a prefix of the other and the smaller string must continue with a tile that continues to match the other string. For many sets of tiles, this is a severe constraint.
For example #1, consider the first tile. The only tile for which one string is a prefix of the other is #3. Any solution must start with that tile, giving us the strings bba/bb. The second solution tile must start with an a in the bottom. Only tile #2 can provide that, giving us bbaab/bbaa. The third solution tile needs to start with a b in the top. Only #3 fits, giving bbaabbba/bbaabb. Now we need a ba in the bottom to continue matching, and only #1 provides that, giving is bbaabbbaa/bbaabbbaa, which is a solution.
I think this is what makes this problem interesting. For many tile sets, it will be easy to come up with a solution, because that prefix requirement as you extend the proposed solution will eliminate many possibilities. After you find out that this doesn't always work, the question arises under what circumstances IS the problem always solvable. Wikipedia says that if you only have two different kinds of tile, it is solvable. If you have 7 or more, it is undecidable. If you have 3 to 6, it is not known if it is decidable or not. Another intesting question would be given a random set of tiles chosen from some predefined distribution, what is the probability that the problem is solvable for that particular tile set?
It always amazes me how autistic computer scientists are. But nice article.