The following makes a nice introductory tutorial for first-year EIE students.
Suppose we are given four infinite piles of dominoes:
b abc ca a
1: --- 2: --- 3: --- 4: ---
ca c a ab
Each has a sequence of letters on the top and a sequence of letters on the bottom. You can take dominoes from these piles and make a chain, like:
b ca b a
--- --- --- ---
ca a ca ab
Once you've made a chain, you can read off the top and bottom "words". In this case, the top word is "bcaba" and the bottom word is "caacaab".
Come up with a chain of dominoes where the top and bottom words are the same.
(A sneaky student might come up with "the empty chain" so you might need to refine the question to say "non-empty chain".)
Here's one answer:
a b ca a abc
--- --- --- --- ---
ab ca a ab c
How can we generalise that ad-hoc method to form an algorithm?
Find a valid starting tile. (Tile is valid if top is a prefix of bottom or vice versa.) If top=bottom then we're done. Otherwise ( * ) keep a note of the "leftover". Find a valid next tile given the current "leftover". If there's now no leftover, we're done, otherwise repeat from ( * ).
If there are multiple valid tiles at any point, try either, backtracking later if necessary.
If given the choice, which tile should you choose? It probably makes sense to choose a tile that makes the leftover as small as possible.
You show an instance to an expert. They immediately say "solvable". What might they have spotted? Contains a tile with top=bottom.
You show an instance to an expert. They immediately say "not solvable". What might they have spotted? No way to start. Or no way to end. Or every tile has top > bottom.
Now let's making it harder. Try adding one extra pile of dominos:
b abc ca a ba
1: --- 2: --- 3: --- 4: --- 5: ---
ca c a ab ab
Got to be careful here, because depth-first search could get stuck in a loop.
How can we avoid getting stuck in a loop?
Sometimes we can detect that we've got stuck in a loop, if leftover is not changing. But sometimes we can't. For instance:
baa a b
1: --- 2: --- 3: ---
a baa bbb
The only solution is 3,3,3,3,3,... but at what point do we stop and say we're in a loop? May just say that once you've gone 10 steps down a path, come back and try another? But try this one:
baa a b
1: --- 2: --- 3: ---
b baa a
which has to start with
baa b b baa
--- --- --- --- ...
b a a b
Here, the shortest solution requires 75 dominos!
In short, it's a very hard problem. Turns out it's undecidable -- you cannot write a program that will accept an arbitrary instance, and always report "solvable" or "not solvable" after a finite amount of time. It's called the "Post Correspondence Problem" and was first formulated by Emile Post in 1946.