What is this type of puzzle called?

Question

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 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 06:53
An interesting term to look up for this puzzle is "Eulerian Path" https://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

JMP · Answer 1 · 2018-07-24T14:37:29.013

4

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:

ADSFDFSA

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]]
...
[{FD,DF},F,[AD,DS,FS,SA,SF]]
[{FD,DS},S,[AD,DF,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!)

edited Jul 24 '18 at 14:37

answered Jul 24 '18 at 06:18

JMP

35,612
7
78
151

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 06:52
1

Your example starts and ends on the same letter, which automatically allows multiple solutions by cyclically shifting parts, i,e. ADSFDFSA -> SADSFDFS -> FSADSFDF -> DFSADSFD -> FDFSADSF -> SFDFSADS -> DSFDFSAD. – Jaap Scherphuis Jul 24 '18 at 13:55
That's interesting I'm not a programmer my self though I have done some script editing for some IRC bots back when i used to use mIRC and have written a number of .bat files back when I used to use Dos ... how would I go about using that method? (I also know how to use the browsers console(chrome) to some extent) – Goku Gohan Jul 25 '18 at 08:37
you need fairly sophisticated coding skills and a modern language, such as JavaScript, which will work in your browser. Try https://developer.mozilla.org/en-US/ for a good reference site. – JMP Jul 25 '18 at 09:06

What is this type of puzzle called?

1 Answers1