Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend that you are you want to know how secure their password is. Your job is to calculate all the ways that a particular pattern can be made.
How Android patterns work
Patterns are drawn on a 3x3 grid of nodes. In a pattern one visits a series of nodes without ever lifting their finger from the screen. Each node they visit is connected to the previous node by a edge. There are two rules to keep in mind.
You may not visit any one node more than once
An edge may not pass through an unvisited node
Note that, while typically very hard to perform and thus not very common in real android lock combinations, it is possible to move like a Knight. That is, it is possible to move from one side to a non-adjacent corner or the other way around. Here are two examples of patterns employing such a move:
Here is a an animated Gif of it being performed.
Solving a pattern
A typical pattern might look something like this:
With a simple pattern like this one it there are two ways two draw the pattern. You can start at either of the two loose ends and traveling through the highlighted nodes to the other. While this is true for many patterns particularly ones that human beings typically employ this is not true for all patterns.
Consider the following pattern:
There are two immediately recognizable solutions. One starting in the upper left:
And one starting in the bottom center:
However because a line is permitted to pass through a point once it has already been selected there is an additional pattern starting in the top middle:
This particular pattern has 3 solutions but patterns can have anywhere between 1 and 4 solutions[citation needed].
Here are some examples of each:
1.
2.
3.
4.
I/O
A node can be represented as the integers from zero to nine inclusive, their string equivalents or the characters from a to i (or A to I). Each node must have a unique representation from one of these sets.
A solution will be represented by an ordered container containing node representations. Nodes must be ordered in the same order they are passed through.
A pattern will be represented by an unordered container of pairs of nodes. Each pair represents an edge starting connecting the two points in the pair. Pattern representations are not unique.
You will take a pattern representation as input via standard input methods and output all the possible solutions that create the same pattern via standard output methods.
You can assume each input will have at least one solution and will connect at least 4 nodes.
You may choose to use a ordered container in place of an unordered one, if you so desire or are forced to by language selection.
Test Cases
With the nodes arranged in the following pattern:
0 1 2
3 4 5
6 7 8
Let {...} be an unordered container, [...] be a ordered container, and (...) be a pair.
The following inputs and outputs should match
{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}
An imgur album of all the test cases as pictures can be found here. Patterns are in blue solutions in red.
Scoring
This is code golf. Fewest bytes wins.
