# What is this type of puzzle called?

for these puzzles you're given a set of letter pairings that you line up into a code via the overlapping letters as an example:

you have pairs "CA", "CO", "DC" and "OD" for a 5-letter code. with the answer being CODCA (contains CO, OD, DC, CA in that order)

• Pattern matching? – Lawrence Jul 24 '18 at 6:10
• Pattern matching would be a generic category of puzzle though sadly it's starting to look like this particular puzzle type doesn't have a proper name – Goku Gohan Jul 24 '18 at 6:53
• An interesting term to look up for this puzzle is "Eulerian Path" en.wikipedia.org/wiki/Eulerian_path – LeppyR64 Jul 24 '18 at 11:06
• @LeppyR64 Quite true. Once you convert the letter pairs into the directed edges of a graph where the nodes are the letters, the puzzle becomes trivial. – Jaap Scherphuis Jul 24 '18 at 12:44
• @JaapScherphuis Or it has a whole bunch of solutions :) – LeppyR64 Jul 24 '18 at 20:06

It looks like a $1$-dimensional overlapping jigsaw puzzle,

or Marshall Squares in 1d.

They are very easy to make, just type in a string and then partition it accordingly.

For example:

AD DF DS FD FS SA SF

is derived from:

To solve or check for the uniqueness of a solution, we can check all $k!$ permutations, but we can improve on this using a recursive sieved tree algorithm.

First check the opening pairs for successful candidates, and store the result in a new array as [{pair},last letter, remaining array], and repeat the process on the new array.

For example, the new array for my example, starting from:

[{},NULL,[AD,DF,FD,DS,SF,FS,SA]]


would contain:

[{AD,DF},F,[DS,FD,FS,SA,SF]]
...
...


giving only 13 new entries.

The next level should produce entries like:

[{AD,DF,FD},D,[DS,FS,SA,SF]]


and repeat until:

[{AD,DF,FD,DS,SF,FS,SA},NULL,[]]


for example.

(Note that this means my example is not uniquely defined - ADFDSFSA also works!)

• Yea but I'm not looking to make them I'm looking for a proper name for them or a solver (which is what i was hoping to use the proper name for to see if anyone has written a solver) – Goku Gohan Jul 24 '18 at 6:52