I am trying to count the number of android patterns, i.e. simple paths, without using brute force. The android pattern is a 3x3 graph:
1 2 3
4 5 6
7 8 9
• The possible length for a pattern is from 4 to 9 vertices.
• Two vertices which are separated by a vertex not yet used are not connected directly (in the graph schematized above, an example could be 1 and 7, that are separated by 4, so we cannot go directly from 1 to 7, we have to go from 1 to 4 and then from 4 to 7).
• The pattern can only use a vertex a single time, however, if a vertex has been already used, the pattern can pass through it (e.g. the pattern 4-5-6-2-8 is valid).
• Also, note that chess-horse-type moves are valid (e.g. 1-8-3).
If you have an answer for the part of counting the simple paths without the "conditional edges" (e.g. {1, 3}, when 2 has already been used) I would also appreciate it.