Possible Duplicate:
Combination of smartphones' pattern password
I have the following problem:
As you can see, this is a 9 dot pattern. I'm looking to find the number of all possible combinations according to several rules. Here are the rules of the problem:
- Only straight lines can be used to connect the dots.
- At least 4 dots must be connected.
- If you connect 2 dots directly, when there's a dot in between, it will also be crossed (so if you try to connect 1->3, you'll actually connect 1->2->3). This rules exist if rule #6 is not in effect.
- Diagonal lines are allowed (you can connect from 2->6, even from 4->9).
- You must use one continuous line to connect all dots (The continuous line can be broken into straight lines only).
- Once a dot is connected, it may not be connected again.
Examples for valid connections:
1->2->3->6 1->(5)->9->(8)->7 1->6->7->4->2->3->9->8->5 //Note that when passing from 3 to 9, 6 is not selected again.
Invalid:
1->2->3 1->2->3->2 4->(5)->6->5
I honestly don't know how to even begin to approach this. And would appreciate any help :)