patterns possible on 3x3 matrix of numbers

Question

Possible Duplicate:
android lock password combinations

Respected sir, I came across a question which asked for finding all the unique pattern possible given a 3x3 matrix with numbers from 1-9. which is same as android lock screen. Can you help me how to find it ?? I was thinking can we use floyd warshall for this and increment count whenever the value changes in the subsequent matrix??

Solution

Combinations of the Android pattern lock screen would not be from 1-9. Instead, they would be 4-9, as the lock pattern needs a minimum of four inputs, and anything below that is invalid (at least 2.3 onwards. I believe 2.2 and below allowed 3 point locks). Here's the breakdown of the combinations:

Moves = 4, combinations = 1624
Moves = 5, combinations = 7152
Moves = 6, combinations = 26016
Moves = 7, combinations = 72912
Moves = 8, combinations = 140704
Moves = 9, combinations = 140704

Total possibilities: 1624 + 7152 + 26016 + 72912 + 140704 + 140704 = 389112

A complete breakdown of the Math behind this given by a Google Engineer can be found here.

Comments

[user1502308]

hmmmm...Thanks!:) This is what I was looking for.:)

[user1502308]

But Can you tell me if I use floyd warshall and I declare a variable count to 0. And after matrix(4) which represents paths of length 4.I keep on incrementing the count whenever the value in matrix change. Will that give me the correct answer?

[Raghav Sood]

I don't know. It might work. If you do try it, please post the results here

[Bachiri Taoufiq Abderrahman]

Here is a medium article exposing the solution using python medium.com/@kabab/…