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

Comments

  1. wonderwice7:09 PM, April 10, 2012

    Coding at least is easy. Answer comes to 140240. I have assumed that a single number is not a valid password, and otherwise there is no restriction that all numbers must be used.

    ReplyDelete
  2. wonderwice7:20 PM, April 10, 2012

    Coding does not seem so hard. Even a brute force approach seems to finish in a few minutes to give 149507072.

    Code as follows, let me know if this looks okay:




    #include

    #define N 3
    #define NN 9

    void countPasswords (int* pickedArr, bool lastAlready, int lastPicked, int depth, int& count, int nextArr[][NN]) {
    if (depth >= (NN + 1)) {
    // return;
    }

    for (int i = 0; i < NN; i++) {
    if ((lastPicked >= 0) && (nextArr[lastPicked][i] == 0)) {
    continue;
    }

    bool lastThis = (pickedArr[i] > 0);

    if (lastAlready == true && lastThis == true) {
    continue;
    }

    ++ pickedArr[i];

    if (depth > 0) {
    ++ count;

    // for (int k = 0; k < NN; k ++) {
    // printf ("%d ", pickedArr[k]);
    // }

    // printf ("\n");
    }

    countPasswords (pickedArr, lastThis, i, depth + 1, count, nextArr);
    -- pickedArr[i];
    }

    }

    int main (void) {
    int pickedArr[NN];

    for (int i = 0; i < NN; i ++) {
    pickedArr[i] = 0;
    }

    int lastPicked = -1;
    int count = 0;
    int nextArr[NN][NN];

    for (int i = 0; i < NN; i++) {
    int i1 = (i / N);
    int i2 = (i % N);

    for (int j = 0; j < NN; j ++) {
    int j1 = (j / N);
    int j2 = (j % N);

    if (((i1 + j1) % 2 == 0) && ((i2 + j2) % 2 == 0)) {
    nextArr[i][j] = 0;
    } else {
    nextArr[i][j] = 1;
    }

    // printf ("%d ", nextArr[i][j]);
    }

    // printf ("\n");
    // printf ("\n");
    }

    int depth = 0;
    countPasswords (pickedArr, false, lastPicked, depth, count, nextArr);
    printf ("count %ld\n", count);
    }

    ReplyDelete
  3. Mitesh J Dave2:25 PM, April 19, 2012

    The solution is possible only on theoretical basis as per my knowledge.
    Because practically,the time lapse between two WRONG hits,increases exponentially.

    ReplyDelete
  4. pyrole2:15 AM, August 23, 2012

    I have an approach..please validate :)

    First lets define three functions:-
    T(k) = No of passwords using k vertices
    F(k) = No of passwords where starting point = end point
    G(k) = no of passwords where starting point is different from ending point

    Argument 1:- T(k) = F(k) + G(k)
    ie. All possible paths = Paths that start from a point and don't end at that point + Paths that start from a point and end at that point

    Argument 2:- T(k+1) = (k+1)*(2.T(k)+k-k.F(k))
    ie. If we add a vertex to our set of k vertices, the total number of paths =
    Number of paths with edge > 1, that start from the new vertex but don't end in the same vertex = T(k) + paths that start and end on the same new vertex = T(k)
    Plus number of paths with edge length one = k
    Minus number of paths that start with some other vertex and end at the same vertex = k.(F(k))
    For k+1 vertices...by symetry...All paths will be unique because we are defining unique starting vertices.

    Now we need to find F(k)
    Its actually easier to find G(k), so lets do that:-

    Argument 3:- G(k+1)= (2.G(k)+k)(K+1)
    No of paths which start with new vertex and does not end with the same vertex = (2.G(k) + k) why?...think

    Solving the recurrence relation for G(k) and replacing F(k) by T(k)-G(k) in argument 2 and solving that recurrence relation should give the answer.

    I am rusty with solving rec rel's...but comments are welcome...

    Jatin Patni

    ReplyDelete
  5. Kapil Dubey3:36 PM, October 17, 2012

    @Pyrole, your solution assumes that it is possible to move to any vertex from any vertex, which is not the case here
    like for example, we cannot move to 9 from 1 directly. So, we need to make a graph and then try to find the solution(which perhaps can be done by a little modification to DFS)

    ReplyDelete
  6. Pratik Poddar3:21 PM, September 12, 2026

    In the right ballpark, but double-check the pass-through rule: the count commonly cited for the 3x3 Android pattern lock (all len

    ReplyDelete
  7. Pratik Poddar3:22 PM, September 12, 2026

    149 million is far too many - there are at most 9! = 362,880 orderings of the dots, so any count above that signals a bug. From t

    ReplyDelete
  8. Pratik Poddar3:23 PM, September 12, 2026

    True - the lockout throttling is the practical defense. But the combinatorial question stands on its own: how big is the pattern

    ReplyDelete
  9. Pratik Poddar3:24 PM, September 12, 2026

    The decomposition into closed vs open paths is clean, but as Kapil points out below, the recurrence treats the graph as complete

    ReplyDelete
  10. Pratik Poddar3:25 PM, September 12, 2026

    Exactly right - the move graph is the 3x3 grid with the midpoint rule, and counting self-avoiding walks on it is a DFS/DP over su

    ReplyDelete
  11. Pratik Poddar3:26 PM, September 12, 2026

    Exactly right - the 3x3 grid is not a complete graph: 1 to 9 is impossible directly (it passes through 5, which then counts as vis

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more