Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Have you ever seen this interface?

Pattern lock

Nowadays, it is used for locking smartphones.

If you haven't, here is a short video on it.


The rules for creating a pattern is as follows.

  • We must use four nodes or more to make a pattern at least.
  • Once a node is visited, then the node can't be visited anymore.
  • You can start at any node.
  • A pattern has to be connected.
  • Cycle is not allowed.

How many distinct patterns are possible?

share|improve this question
1  
I think that the best way is just case by case analysis while using symmetry. For example, there are 48 ways of starting at the center. (4 possibilities for the first step, then two possibilities for the next step, then the steps are fixed, but there are six possibilities for where to stop). –  Phira May 5 '11 at 11:57
4  
I guess the problem is that of counting self-avoiding walks in the 2x2 grid. See Wikipedia and especially Mathworld. –  ShreevatsaR May 5 '11 at 12:07
1  
Loops are allowed though, see youtube.com/watch?v=vV2efG9WCmk&feature=related for example –  Listing May 5 '11 at 13:00
1  
Diagonals are allowed too, so user9325's calculations are invalid. –  TonyK May 5 '11 at 13:45
1  
I don't see a simple way to attack it. I would just write a program to generate the possibilities (9! is only 362880 and the shorter ones are even less) and check each one for whether it meets the rules. –  Ross Millikan Apr 5 '12 at 17:31
show 7 more comments

5 Answers

up vote 7 down vote accepted

I believe the answer can be found in OEIS. You have to add the paths of length 4 through 9 on a 3x3 grid, so 80+104+128+112+112+40=576

I have validated the 80 4 number paths. If we number the grid $$\begin{array}{ccc}1&2&3\\4&5&6\\7&8&9 \end{array}$$

The paths starting 12 are 1236, 1254, 1258, 1256 and there were 8 choices of corner/direction, so 32 paths start at a corner. Starting at 2, there are 2145,2147,2369,2365,2541,2547,2587,2589,2563,2569 for 10 and there are 4 edge cells, so 40 start at an edge. Starting at 5, there are 8 paths-four choices of first direction and two choices of which way to turn

Added per user3123's comment that cycles are allowed: unfortunately in OEIS there are a huge number of series titled "Number of n-step walks on square lattice" and "Number of walks on square lattice", and there is no specific definition to tell one from another. For 4 steps, it adds 32 more paths-four squares to go around, four places to start in each square, and two directions to cycle. So the 4 step count goes up to 112. For longer paths, the increase will be larger. But there still will not be too many.

share|improve this answer
2  
Wow, just 576? If we try 576 patterns, we can unlock any smartphone which uses that way. Shocked. –  Benjamin May 5 '11 at 12:41
    
Cycles are allowed so there are more patterns. But yes if it would use the proposed pattern its right –  Listing May 5 '11 at 13:02
10  
It's even easier to unlock a smartphone which uses this form of code. For most people, this is the most commonly swiped pattern on their phone. The pattern will be clearly visible on the screen as an oily deposit from the user's fingers. –  Chris Taylor May 5 '11 at 13:05
    
Note that if "circles are allowed" only means that the last step could close a circle, this would do less than multiply the result by 4, so you might get 2000 possibilities. –  Phira May 5 '11 at 13:38
2  
@RossMillikan This doesn't seem right, diagonal lines are allowed! connecting from 1->5 and from 1->6 is allowed! –  Madara Uchiha Apr 5 '12 at 16:59
show 4 more comments

I don't have the answer as "how to mathematically demonstrate the number of combinations". Still, if that helps, I brute-forced it, and here are the results.

  • 1 dot: 9
  • 2 dots: 56
  • 3 dots: 320
  • 4 dots: 1624
  • 5 dots: 7152
  • 6 dots: 26016
  • 7 dots: 72912
  • 8 dots: 140704
  • 9 dots: 140704

Total for 4 to 9 digits :389,112 combinations

share|improve this answer
1  
How do you get $56$ possibilities for $2$ dots? I only get $4\cdot 3+4\cdot 5+8=40$. –  celtschk Jul 9 '13 at 6:44
    
I now tried for $3$ dots and only get $160$ possibilities. –  celtschk Jul 9 '13 at 6:51
add comment

Was bored at work and solved it total combinations are 389432 if using 3 or more

389112 is using 4 or more.

share|improve this answer
add comment

Writing this as a program in python gives the following results:

path with 1 dot => 9 combinations

path with 2 dots => 40 combinations

path with 3 dots => 160 combinations

path with 4 dots => 656 combinations

path with 5 dots => 2776 combinations

path with 6 dots => 11776 combinations

path with 7 dots => 50488 combinations

path with 8 dots => 217408 combinations

path with 9 dots => 941368 combinations

share|improve this answer
add comment

Multiply the amount of nodes(9) by the number of rows and columns (9) and then multiply that by the amount of starts(9).

It would look like this: $9\times 9=81$, then, $81\times 9=729$, so it would be 729 possible answers that some one could use. Wait!, but you have to use 4 at a minimum so you multiply that by 4 like this: $729\times 4=2916$

$2,916$ possible answers!

share|improve this answer
add comment

protected by T. Bongers Apr 17 at 15:40

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.