Figure Out the Android Lock Pattern
Python 2.7, 493 430 bytes

exec("L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]IL];S=sorted;F=lambda t:''.join(str(i)It)\ndef N(x):\n s=' '.join(F(S(i))Ix)\nIL:s=s.replace(i[::2],i[:2]+' '+i[1:])\n return S(set(s.split()))\ndef P(s):\n e=0\nIL:e|=-1&lt;s.find(i[::2])&lt;s.find(i[1])\n return[zip(s[:-1],s[1:]),L][e]\nx=N(input());print[F(i)I__import__('itertools').permutations({iI`x`if i.isdigit()})if x==N(P(F(i)))]".replace('I',' for i in '))


The single line version wraps the program with exec("...".replace('I',' for i in ')) so that all for-loops and generators can be shorted with a single I and saves 15 bytes over this more readable version:

L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]for i in L]
S=sorted;F=lambda t:''.join(str(i)for i in t)
def N(x):
 s=' '.join(F(S(i))for i in x)
 for i in L:s=s.replace(i[::2],i[:2]+' '+i[1:])
 return S(set(s.split()))
def P(s):
 e=0
 for i in L:e|=-1&lt;s.find(i[::2])&lt;s.find(i[1])
 return[zip(s[:-1],s[1:]),L][e]
x=N(input())
print[F(i)for i in __import__('itertools').permutations({i for i in`x`if i.isdigit()})if x==N(P(F(i)))]


The program takes the input in the manner shown (e.g. {(1,4),(3,4),(5,4),(8,5)}) or as a list of string (e.g. ['14','34','54','85']) (or in other python friendly formats) and returns the output as a list of strings. So we technically have an ordered container of ordered containers.

The function N normalizes a pattern so that two patterns can be easily compared. The normalization sorts the pairs denoting edges (so '02' instead of '20'), use string replacement to expand double edges (e.g. '02' becomes '01 12'), splits the edges into a set to remove duplicates, and sorts the result.

The function F flattens tuples of ints/strings to strings, so we can normalize paths produced in different ways.

The list L contains all lines on screen.

We then take each permutation of all digits in the normalized pattern and compute a valid path or L if invalid (which never normalizes to list of pairs like real paths would), or a list of pairs indicating the order nodes are visited if valid. If this normalizes to the same pattern then we have a valid solution and include it in the final list.

The main check needed to validate a permutation as a string s is -1&lt;s.find(i[::2])&lt;s.find(i[1]), which detects an error with a line i. For instance with the line '210' the code detects an error if '20' occurs (i.e. it's index is greater than -1) and '1' occurs after it. We don't have to worry about 1 not occurring because the 1 will show up in the normalized pattern when it wasn't in the input.



NOTE: I know replacing str(i)for i in t with map(str,t) and {i for i in`x`if i.isdigit()} with set('012345678')&amp;set(`x`) would make the original code shorter, but this would still be slightly longer that substituting I.