You are viewing paulmck

Previous Entry | Next Entry

Puzzle: How many unlock paths?

BookAndGlasses
I was recently at dinner with some Linux kernel hackers who were showing off their smartphones. These phones have an interesting unlock mechanism: the phone displays an 3-by-3 array of circles, and the user traces out a path among the circles. If the path is correct, the phone unlocks.

The paths are not arbitrary. From what I could see, here are the rules governing them:

  1. Paths are composed of a series of straight line segments.
  2. Each line segment connects a pair of circles.
  3. If the preceding line segment arrived at a given circle, then the next line segment must leave that same circle.
  4. A given circle may be visited only once.
  5. A line segment may pass over a given circle without visiting it only if that circle has already been visited. (Attempting to pass over a not-yet-visited circle will instead visit that circle.)

How many unique paths are there?

Tags:

Comments

( 7 comments )
(Anonymous)
Jul. 24th, 2011 03:09 am (UTC)
http://www.quora.com/How-many-combinations-does-Android-9-point-unlock-have

You missed a condition. There's also a minimum sequence length.
paulmck
Jul. 24th, 2011 05:05 am (UTC)
Thank you for the info
Should be an easy fix. ;-)
paulmck
Jul. 24th, 2011 05:15 am (UTC)
And in fact...
All that is required is to initialize "sum" in trynext() to 1 only if the path length is at least 4.
Johannes Weiner
Aug. 4th, 2011 02:31 pm (UTC)
Rule 1?
I think this breaks the first rule: http://i.imgur.com/lfjJj.jpg
paulmck
Aug. 4th, 2011 03:27 pm (UTC)
Re: Rule 1?
The photo shown at that URL looks to me like a series of straight line segments.
(Anonymous)
Aug. 11th, 2011 06:39 pm (UTC)
blogposting

Interesting post. Thank you!
(Anonymous)
Aug. 26th, 2011 03:36 pm (UTC)
no of possible patterns
if im right i have a android v 2.2 and it calls 3 incorrect circles a fowl ( as in counted 30 sec. lock after 5 incorrect tries) so the minimum condition should be 3 if it is whats the num. of patterns possible i dont have a haskell programming background so i cant relly get what they are trying to say in those codes
( 7 comments )