38
$\begingroup$

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?

6 Answers 6

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.

  • 0
    @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 answer2015-06-28
8

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

  • 0
    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.2018-05-28
3

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

389112 is using 4 or more.

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.

  • 0
    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.2017-08-19
-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!

-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