### Original Puzzle: Pattern Lock - Combinatorics Puzzle - Number of Possible Passwords

Source: Discussion with Ankush Jain (CSE IITB 2011 Alumnus, Morgan Stanley Analyst) a few months back. Discussion revived by Sangram Raje (CSE IITB 2008 Alumnus, Tower Research Analyst) today. Problem: Ever seen a pattern lock in Galaxy S2? Password is a series of connected line strokes. How many possible password combinations can you have? Some description about the problem: 1) Assuming the dots on the screen are like (1, 2, 3 in the first row), (4, 5, 6 in the second row) and (7, 8, 9 in the third row), you cannot go to 8 from 2, without going through 5. So, a password like * * 8 2 * * is not possible. 2) You cannot move over two lines twice You can move to a used point, but you cannot move to another used point from a used point I do not see a simple way to solve this. But even coding this looks very difficult to me. Any takers? Update : (19-07-2012) This is essentially an open ended question