40

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?

hrkrshnn
  • 6,287
Benjamin
  • 525
  • I am sorry, but these "rules" are too vague to do any calculation. What is a "pattern"? Where does it have to start? to end? Does it have to be connected? Can it include circles? – Phira May 05 '11 at 11:32
  • Thanks, I edited my question. – Benjamin May 05 '11 at 11:40
  • 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 05 '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 05 '11 at 12:07
  • 1
    Loops are allowed though, see http://www.youtube.com/watch?v=vV2efG9WCmk&feature=related for example – Listing May 05 '11 at 13:00
  • 1
    Diagonals are allowed too, so user9325's calculations are invalid. – TonyK May 05 '11 at 13:45
  • @user3123: oh, I didn't know that. It would be better if I knew at the moment I asked. – Benjamin May 05 '11 at 14:38
  • What made you interested in this problem? Is it homework? – Matthew Conroy Apr 05 '12 at 16:41
  • 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 05 '12 at 17:31
  • It is the number of self-avoiding walks of at least 3 steps in a certain graph. Unfortunately there is no simple way to enumerate them, so brute-force computation seems to be the way to go. – Robert Israel Apr 05 '12 at 18:16
  • @Benjamin, have you seen this? http://www.youtube.com/watch?v=prIQXLYiI_g – An old man in the sea. Apr 17 '14 at 15:14
  • It doesn't have to be self-avoiding, you can certainly visit a node several times, cross over your path, ... using symmetry and "reflection on the borders" it should be possible to cobble together a recurrence for patterns of lenght $n$... – vonbrand Apr 17 '14 at 16:38
  • Benjamin's description agrees with my phone which does not allow self-intersections. Also note that there is no edge between two nodes if the straight line joining the nodes contains another node. – Rob Arthan Sep 20 '14 at 16:07
  • Sorry! By "does not allow self-intersections", I meant that the path can't visit a node more than once, but it can cross itself at non-nodes. – Rob Arthan Sep 20 '14 at 20:04
  • One of these rules is invalid. I know for a fact that on android smartphones, once a node is visited, you can visit it again. – Travis Tubbs Mar 13 '19 at 20:52

6 Answers6

10

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

Mithlesh Upadhyay
  • 4,787
Toin's Raméo
  • 117
  • 2
    How do you get $56$ possibilities for $2$ dots? I only get $4\cdot 3+4\cdot 5+8=40$. – celtschk Jul 09 '13 at 06:44
  • I now tried for $3$ dots and only get $160$ possibilities. – celtschk Jul 09 '13 at 06:51
  • 1
    the 2 dots are correct.. so the rest probably too – tobi Jun 28 '15 at 01:36
  • 2
    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 '18 at 15:37
10

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.

Nick
  • 1,231
Ross Millikan
  • 374,822
  • 4
    Wow, just 576? If we try 576 patterns, we can unlock any smartphone which uses that way. Shocked. – Benjamin May 05 '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 05 '11 at 13:02
  • 21
    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 05 '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 05 '11 at 13:38
  • @user9325: In fact it is much smaller if you mean by closing a circle going back to the starting point. For four steps you get the 32. For 6 steps there are 48 by the same argument but with 6 starting points. For 8 steps there are 64. So this only brings us to 720. – Ross Millikan May 05 '11 at 13:45
  • @Chris: this is a point often overlooked in (amateur) cryptography analysis-maybe there is a way better than brute force. Think of the substitution cyphers published in the newspaper that people have no trouble with. There are $26!\approx 4E26$ keys, a rather large number. – Ross Millikan May 09 '11 at 13:22
  • 6
    @RossMillikan This doesn't seem right, diagonal lines are allowed! connecting from 1->5 and from 1->6 is allowed! – Madara's Ghost Apr 05 '12 at 16:59
  • @Truth: I didn't see that in the problem specification. "Connected" to me prohibited diagonal moves. You are right, if they are allowed the total will be higher. – Ross Millikan Apr 05 '12 at 17:19
  • To my (and OP's) defense I'll say nothing in the specifications stated that only vertical/horizontal lines could be made. Any node can connect to any node. See my (more accurate) question here – Madara's Ghost Apr 05 '12 at 17:21
  • i write program; for 4 dots i got 1400 pattern!!! why you say 1624 state? http://www.iranled.com/forum/thread-29844-post-250111.html#pid250111 –  Apr 05 '15 at 18:22
  • You can find the pattern that is not listed?!?! –  Apr 05 '15 at 18:27
  • this answer is just totally wrong.. not just that diagonals like 1 to 5 are allowed.. its also possible to e.g. go from 1 to 8 – tobi Jun 28 '15 at 01:28
  • @tobi: in a math context, the original poster owes us the rules. Given the rules, we can find the number of paths. Can you go $1 \to 9$ despite the fact that $5$ is in the way? If so, the number of codes is just $9 \cdot 8 \cdot 7 \cdot 6$ If not, it is a little harder. – Ross Millikan Jun 28 '15 at 04:39
  • @RossMillikan: no you can't. and yes, its a little harder. it's not just n! "the original poster owes us the rules".. well in the short clip the op linked you can see a diagonal way. but i guess toins rameo already gave the correct answer – tobi Jun 28 '15 at 19:05
  • When I've tested this on Android 11, the connection $1 \to 9$ is permitted if and only if $5$ was already visited. If you physically try to create this forbidden connection by carefully tracing your finger from $1 \to 9$ before $5$ has been visited, you will create 2 nodes, $1 \to 5$ and $5 \to 9$ (and likewise for $9 \to 5 \to 1$; $3 \to 6 \to 9$; and all other sets of 3 collinear points). Does the current answer factor this in? – JamesTheAwesomeDude Feb 14 '24 at 22:04
3

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

389112 is using 4 or more.

user642796
  • 52,188
Ryan
  • 39
0

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.

Rob Arthan
  • 48,577
  • 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
-3

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!

user127096
  • 9,683
jamil hamlet
  • 9
-3

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

Finance
  • 1,247