Generating a set of permutation given a set of numbers and some conditions on the relative positions of the elements

Question

I am looking for an algorithm which, given a set of numbers {0, 1, 2, 4, 5...} and a set of conditions on the relative positions of each element, would check if a valid permutation exists. The conditions are always of type "Element in position i in the original array must be next(adjacent) to element in position j or z".
The last and first element in a permutation are considered adjacent.

Here's a simple example:

Let the numbers be {0, 1, 2, 3}
and a set of conditions: a0 must be next to a1, a0 must be next to a2, a3 must be next to a1
A valid solution to this example would be {0,1,3,2}.

Notice that any rotation/symmetry of this solution is also a valid solution. I just need to prove that such a solution exists.

Another example using the same set:
a0 must be next to a1, a0 must be next to a3, a0 must be next to a2.

There is no valid solution for this example since a number can only adjacent to 2 numbers.

The only idea I can come up with right now would be to use some kind of backtracking.
If a solution exists, this should converge quiet fast. If no solution exists, I can't imagine any way to avoid checking all possible permutations. As I already stated, a rotation or symmetry doesn't affect the result for a given permutation, therefor it should be possible to reduce the number of possibilities.

Answer 1

Formulate this as a graph problem. Connect every pair of numbers that need to be next to each other. You are going to end up with a bunch of connected component. Each component has a number of permutations (lets call them mini-permutations), and you can have a permutation of the components.

When you create the graph make sure each component follows a bunch of rules: no cycles, no vertices with more than two vertices etc.

Answer 2

Basically you want to know if you can create chains of numbers. Put each number into a chain which keeps track of the number and up to two neighbors. Use the rules to join chains together. When you join two chains you'll end up with a chain with two loose ends (neighbors). If you can get through all the rules without running out of loose ends then it works.