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?

  • 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
  • 4
    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
up vote 8 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 $3\times3$ 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.

  • 3
    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
  • 19
    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
  • 4
    @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

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

  • 2
    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
  • 1
    the 2 dots are correct.. so the rest probably too – tobi Jun 28 '15 at 1:36
  • How did you brute force it? What was the algorithm? – Archisman Panigrahi Dec 25 '15 at 15:48
  • I just validated the 320 possibilities for 3 dots. By exploiting rotational and mirror symmetry there are only 9 cases for the first 2 dots, where for each case the number of possibilities of the third point can be easily calculated. Note that when not starting in a corner and then going to a corner one can go back and "jump over" the starting point to reach another corner. – coproc May 28 at 15:37

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

389112 is using 4 or more.

For what it is worth, I coded this problem and found 139,880 paths meeting the criteria. I don't know of any good way of validating this answer, but I can independently verify that my code gets the right answer for the number of paths with 3 points, which is 304. To see this, note that the valencies of the 9 points look like this: $$\begin{array}{ccc} 5 & 7 & 5 \\ 7 & 8 & 7 \\ 5 & 7 & 5 \end{array} $$ This is because a node at a corner can see the 5 non-corners, a node at the centre of a side can see the 7 other nodes that are not directly opposite and the node in the centre of the square can see all the 8 other nodes. Now count paths with 3 points by considering the middle point: if it has valency $n$, then it contributes $n(n-1)$ paths of length 3 ($n$ choices for the edge going in and $n - 1$ for the edge going out). So the number of paths with 3 points is:

$$4 \times 5 \times 4 + 4 \times 7 \times 6 + 8 \times 7 = 80 + 168 + 56 = 304 $$

The integer sequences http://oeis.org/A247943 and http://oeis.org/A247944 now record what I believe to be the state of the art on this question. Anyone who disagrees with the above analysis and calculations is encouraged to comment on those sequences.

  • An argument along the same lines applied to the middle edge in a path of 4 points confirm that my code is also getting the right answer of 1400 for that case. – Rob Arthan Sep 21 '14 at 16:55
  • I was testing how it works on Android, and there you can pass over an already used node. So 2->1->3 is allowed, but not 1->3->2. A 3 node pattern therefore have 320 combinations. There is a total of 389112 valid combinations for 4 to 9 nodes. I don't have enough reputation on this site to post an answer with code. – some Aug 19 '17 at 12:41

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!

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

protected by user61527 Apr 17 '14 at 15:40

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

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.