patterns possible on 3x3 matrix of numbers [duplicate]

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

Answer 1

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.