7
$\begingroup$

I am trying to set a lock pattern for my phone with a snoopy guy behind. If he is able to see what my pattern looks like at the end, what is best possible sequence i can set so he will take maximum number of attempts to unlock the phone (assuming he can pry it from my hand)? Rules for the pattern: The pattern should be something that can be set on any android screen lock

The Android imposes these conditions on patterns:

  1. The dots in the pattern must all be distinct and connected with line segments and only at the end point of which you draw another line segment connecting another dot.
  2. If line segment passes through a previous unused dot X, then you can't use X as a start/end point again, though another line segment can pass through it.
  3. If line segment passes through a used dot X and endpoint is not used, it is a valid segment.
  4. The pattern can have only one start and end point for the pattern

For eg: Assume all dots have same position as a telephone keypad (so 1,1 is 1; 2,2 is 5 etc) if he sees the following pattern:

enter image description here

There are only two combinations he needs to try (6->5->2->1) or (1->2->5->6)

Right now the best i can come up with is this:

enter image description here

There are 4 possible combinations and they are (2->5->8) (5->2->8) (5->8->2) and (8->5->2)

Can anybody tell me a better pattern?

$\endgroup$
  • $\begingroup$ Are diagonals allowed? $\endgroup$ – bolt997 Jul 11 '17 at 9:41
  • 2
    $\begingroup$ @valuable_asset I am not an Android user. What are the pattern restrictions used while setting a lock for an Android phone? $\endgroup$ – LeppyR64 Jul 11 '17 at 9:56
  • 2
    $\begingroup$ The three point puzzle isn't working for all androids/phones (mine requires at least 4 points) @valuable_asset $\endgroup$ – Schneejäger Jul 11 '17 at 10:55
  • 2
    $\begingroup$ Your solution is invalid as you need at least 4 nodes to be used. $\endgroup$ – BreakingMyself Jul 11 '17 at 10:57
  • 1
    $\begingroup$ You could just get really good at almost touching your screen to move your thumb over numbers that aren't included in your pattern. $\endgroup$ – Ian MacDonald Jul 11 '17 at 15:45
7
$\begingroup$

The answer is

that, unfortunately, your answer of 4 is the best you can get. I'm sure there is a simple mathematical argument for this, but I just did it the dumb way and brute-forced all possible patterns.

But, if you don't want to use such a simple pattern, you should be able to generate more interesting looking patterns, such as this one:

enter image description here

$\endgroup$
  • $\begingroup$ I can solve this in only 2 attempts. $\endgroup$ – stack reader Jul 11 '17 at 11:17
  • $\begingroup$ @stackreader looks like you will not be unlocking this phone ;) [the third and fourth patterns are in fact a bit harder to spot.] $\endgroup$ – ffao Jul 11 '17 at 11:35
  • 1
    $\begingroup$ I think the four patterns are: 537264819, 357264819, 591846273, 951846273. The ones that are harder to spot are those that start at 5 instead of 3 or 9. $\endgroup$ – Engineer Toast Jul 11 '17 at 14:21
3
$\begingroup$

I have answer that works in a similar way with crossing the lines:

enter image description here

This doesn't increase the number of possible solutions that I can see but it is more complicated for the snooper to remember.

The solutions are:

(3>6>9>5>2>8>4>7>1), (3>6>9>5>2>8>4>1>7), (6>3>9>5>2>8>4>7>1) and (6>3>9>5>2>8>4>1>7).

$\endgroup$
  • $\begingroup$ This seems to use the same dots many times no? $\endgroup$ – stack reader Jul 11 '17 at 11:18
  • $\begingroup$ @stackreader No it crosses the lines which is valid, this is a screenshot from my actual phone :) $\endgroup$ – BreakingMyself Jul 11 '17 at 11:21
  • 2
    $\begingroup$ 1>7>4 is not legal because 4 has not been used when 1>7 is drawn. $\endgroup$ – ffao Jul 11 '17 at 11:37
  • $\begingroup$ Ah, so it is! So... still 4 solutions lol. That's what I get for staring at a picture instead of using my phone for it. $\endgroup$ – BreakingMyself Jul 11 '17 at 11:41
  • 1
    $\begingroup$ I think its more complex than mine but with same amount of combinations. If you assume complex is better, than it should be a winner! $\endgroup$ – valuable_asset Jul 11 '17 at 12:49
0
$\begingroup$

How about this?

You can drag your finger outside of the grid to skip boxes in the center of a side (such as 4, 8, and 6)

enter image description here

Possible combinations for this pattern include:

1-7-9-3

1-4-7-9-3

1-7-8-9-3

1-7-9-6-3

1-4-7-8-9-3

1-7-8-9-6-3

1-4-7-9-6-3

1-4-7-8-9-6-3

And starting with 4-1-7, we have:

4-1-7-9-3

4-1-7-8-9-3

4-1-7-9-6-3

4-1-7-8-9-6-3

All of these patterns can be mirrored from left to right as well, so you have at least 24 potential matches.

$\endgroup$
  • $\begingroup$ Crossing an unused node automatically adds it, I tried multiple times to cheat the system lol. $\endgroup$ – BreakingMyself Jul 11 '17 at 20:02
  • 1
    $\begingroup$ Back to the drawing board then! Didn't realize this from the instructions in the OP. $\endgroup$ – DigitalShards Jul 12 '17 at 15:11
  • $\begingroup$ the easiest way is to try and make a pattern on an Android phone as all the parameters are built in. $\endgroup$ – BreakingMyself Jul 12 '17 at 15:25
0
$\begingroup$

As mentioned (and proved by brute force) in other answers, 4 is indeed the limit.

This is rambling and needs another round of slimming down, apologies.

You can see the basis of this from your own simple example of a line of 3.

Since you must end somewhere, there must be at least (see @BreakingMyself for a nice illustration of 4) 1 node with only one line connecting. For a potential end node, there is no ambiguity unless it is in a line of 3 (otherwise the pattern has the same possibilities as the pattern if that end node is removed). If the node is in a line of 3, we can have the other two with connections (or multiple connections / potential lines), and can reduce the pattern to an equivalent one.

Two possibilities:

X-*-*    ->    . X-*
               . *-X

One possibility:

X-*-*    ->    . *-X
  |              |

X-*-*    ->    . X-*
    |              |

  |              |
X-*-*    ->    . * X
  | |            | |

Impossible / no possibilities

X-*-*    ->    (impossible end)
  | |

  | |
X-*-*    ->    (impossible end)
  | |

Note that the only case with two possibilities is when you reach the "start", with only a pair of nodes left.

In the case where you only have a single one-connection node, you may only have 1 or 2 possible traversals (end is fixed, potentially ambiguous start).

In the case where you have two one-connection nodes, you may have 1, 2, or 4 possible traversals (1 or 2 possible ends, 1 or 2 potentially ambiguous starts).

Suppose there was a pattern with more than 4 possible traversals. This would need to either have 5+ potential end points, or 3+ potential endpoints and more than one ambiguous starts (e.g., a 3-node-line).

Consider a pattern with 3+ potential endpoints. There can only be a single start and end in a valid pattern. For some traversal of this pattern the start can be a valid endpoint, leaving at least one potential endpoint (singly-connected-node) that must be in the middle of the pattern. The only way to create a singly connected endpoint in the middle is with three nodes in a line, where you enter the middle, visit one end, and (perhaps) exit the other:

    X.         X.
    ||         ||
>---*|     >---*|
     |          |
    *L___>     *

The first is a case of "an impossible end", so there is no way for this singly-connected node to be an endpoint for another path. In the second, this must be the first and last times you visit each of these nodes, so it cannot be a valid starting point: we must enter through the middle, and either the top or the bottom must be our endpoint - making a 3rd endpoint elsewhere impossible, and thus a maximum of 4 possible traversals for any pattern.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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