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