What's the most complex pattern to decipher if you have seen the pattern

Question

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:

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:

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?

Answer 1

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:

Answer 2

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

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).

Answer 3

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)

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.

Answer 4

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.