ROSECODE 254
Pattern Locks
Pattern locks are a popular mechanism to secure our cell phones.
Given a grid 3 * 3, the user define a path by joining some points on that grid:
We add the following constraints:
- the path starts with point 1
- we visit every point exactly once
One possible path is: 1,4,3,5,6,2,7,8,9
Actually, there are exactly 5040 possible paths with the above constraints.
There are 2 paths which reach the maximal length :
- 1,6,7,2,9,4,3,8,5
- 1,8,3,4,9,2,7,6,5
(The maximal length is 16.652...)
A path starting with 1,3,2 would not be valid,for when joining point 1 and 3 we have visited point 2.
How many possible paths are there on a 3*4 grid?
Which paths reach the maximal length?
Answer format: count/(comma separated list of points)
Example: 5040/1,6,7,2,9,4,3,8,5/1,8,3,4,9,2,7,6,5 // for a 3*3 grid.
[My timing : 40 sec]
Given a grid 3 * 3, the user define a path by joining some points on that grid:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
We add the following constraints:
- the path starts with point 1
- we visit every point exactly once
One possible path is: 1,4,3,5,6,2,7,8,9
Actually, there are exactly 5040 possible paths with the above constraints.
There are 2 paths which reach the maximal length :
- 1,6,7,2,9,4,3,8,5
- 1,8,3,4,9,2,7,6,5
(The maximal length is 16.652...)
A path starting with 1,3,2 would not be valid,for when joining point 1 and 3 we have visited point 2.
How many possible paths are there on a 3*4 grid?
Which paths reach the maximal length?
Answer format: count/(comma separated list of points)
Example: 5040/1,6,7,2,9,4,3,8,5/1,8,3,4,9,2,7,6,5 // for a 3*3 grid.
[My timing : 40 sec]