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

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