The longest path of Android screen lock pattern

Question

To assume that we have 9 points. Each one can only be visited by once. The path, such as from the upper left corner to bottom right corner, is also allowed. Can anyone provide an algorithm to calculate the longest path for a screen lock pattern?

Answer 1

You need to provide distance metrics first.
Let's assume the following:
-Horizontal or vertical move can be long 1 for one step or 2 for two steps.
-Diagonally you will have length 1.41 for one step (Square root of 2, pythagorean theorem) or 2.83 for two steps (Square root of 8).
-Like a knight in chess you will have length 2.24 (Square root of 5)

So now you need to find just the maximum sum of this possible steps. If you go with "Best first search" as mentioned above, it will be troublesome because the longest path does not choose alwayst the first best option.
For the following graph:
123
456
789
One option is 519467382, which would have length about 17.7
So maybe it is safer to try calculating all options as mentioned, but you can also keep in mind that because of the symmetry you need to calculate the lengths just for starting nodes 1, 2 and 5. The other nodes would give the same results, so no need for calculations....

Answer 2

It is similar to the travelling salesman problem (TSP), but instead of the shortest path you look for the longest one, and the path is not closed.

For the 9 points case I wouldn't be afraid of just trying all possible paths since there are just 9! = 362880 of them. And this number could potentially be reduced since 3 by 3 regular grid is highly symmetrical.

Another approach (since the path is not closed) could be doing a best-first search from a node with "best" being the one that has the longest path so far. You'll do this from each node remembering the longest path of them all. But this is just a quick thought and I have no proof this would actually work.

Answer 3

Basically a TSP problem with a bit of modification that disallow stepping over points that hasn't been visited.

3x3 can be easily brute-forced. For slightly larger problems, the dynamic programming algorithm for TSP modified also works in {O(2^n*n^2)} time.

https://repl.it/@farteryhr/AndroidLockscreen#index.js

3x3: 17.779271744364845

591643728
573461928
591827346
537281946
573829164
519283764
537649182
519467382

4x4: 45.679014611640504 (0123456789abcdef)

92d6c3875e1f4b0a
68793c2d5e1f4b0a
92d6c3875b4f1e0a
68793c2d5b4f1e0a
a1e5f0b46d2c7839
5b4a0f1e6d2c7839
a1e5f0b4687c2d39
5b4a0f1e687c2d39
a4b5f0e19783d2c6
5e1a0f4b9783d2c6
a4b5f0e192d387c6
5e1a0f4b92d387c6
9786c3d2a4b0e1f5
6d293c78a4b0e1f5
9786c3d2a1e0b4f5
6d293c78a1e0b4f5

5x5: 91.8712723085273 (0123456789abcdefghijklmno)

ci6o0j5dbea9f8g4k3m1n7l2h
cg8k4f9bdae5j6i0o1m3l7n2h
ci6o0n1h7m2l3g8k4fe5jb9ad
c8g4k3l7h2m1n6i0o5ef9bjad
cg8k4l3h7m2n1i6o0ja9fd5eb
c6i0o1n7h2m3l8g4k9aj5dfeb
c8g4k9fdbeaj5i6o0n2l3h1m7
c6i0o5jbdaef9g8k4l2n1h3m7

Answer 4

I calculated manually and I got the longest one to be 561943728 which has a length of 17.76 (take distance between two nearest dots to be 1 unit). If anyone can beat this then show your pattern!

Answer 5

The longest path would be 567 348 192 which is about 18.428

There are atleast 8 such patterns, one other is 567 381 932 (traverse length 18.428). Put a mirror image around those patterns and you get 4 patterns from one such pattern.