combinatorics - Calculate possible "snake" passwords -

we know new password screens on mobile devices. consists of matrix of dots, connected.

a unique password vector of points. points can connected following restrictions:

• a point can connected 1 other point
• a line forced connect closer point if destination point , free point on same line. example:

since middle point not connected before, there no way connect top point bottom.

the first restriction makes find number of graphs trees. it's second restriction cannot find way calculate.

is there easier way calculate amount of possibilities, or way generate possibilities , count them?

since general problem of counting simple paths in undirected graph #p-complete, , pointed out in comments, similar problem of counting self-avoiding paths in grid conjectured hard, think appropriate think how can solve problem in o((n*n)!) time (with n=3 in case).

we have keep in mind additional special case applies on "real" smartphones:

• we can go across intermediate nodes, if have been visited. example possible go (0,0) -> (1,1) -> (0,2) -> (2,0)

there simple dynamic programming approach should able solve @ least 5x5 case: let f(i,j,visited) number of ways when @ vertex (i,j) , visited set of nodes visited earlier. can compute f using dynamic programming trying possible moves , recursing. can represent visited bitmask. total number of possibilities sum(i,j, f(i,j, {(i,j)})).

here results:

n = 2     64 n = 3     389497 n = 4     4350069824956 n = 5     236058362078882840752465 

seems pretty secure information-theoretical standpoint n = 4.

below c++ implementation used. since result can pretty large, program computes modulo large primes, can reconstruct solution using chinese remainder theorem.

#include <bits/stdc++.h> #include <cassert> using namespace std;  typedef long long ll;  const int n = 5; bool getbit(int visited, int i, int j) { return visited & (1<<(i*n + j)); } int setbit(int visited, int i, int j) { return visited | (1<<(i*n + j)); } bool inrange(int i) { return 0 <= && < n; } short dp[n][n][1<<(n*n)]; int mod; int f(int i, int j, int visited) {     short& res = dp[i][j][visited];     if (res != -1) return res;     res = 1;     (int di = -i; di <= n-i-1; ++di)         (int dj = -j; dj <= n-j-1; ++dj) {             if ((di == 0 && dj == 0) || abs(__gcd(di, dj)) != 1) continue;             int i2 = + di, j2 = j + dj;             while (inrange(i2) && inrange(j2) && getbit(visited, i2, j2)) {                 i2 += di;                 j2 += dj;             }             if (inrange(i2) && inrange(j2)) {                 res += f(i2, j2, setbit(visited, i2, j2));                 if (res >= mod) res -= mod;             }         }     return res; }  int primes[] = {     15013,     15017,     15031,     15053,     15061,     15073,     15077,     15083,     15091,     15101, };  int main(int argc, char **argv) {     int lo = 0;     int hi = sizeof primes / sizeof *primes - 1;     if (argc > 1) {         stringstream ss; ss << argv[1]; ss >> lo;         hi = lo;     }     (int p = lo; p <= hi; ++p) {         mod = primes[p];         cout << mod << " " << flush;         (int = 0; < n; ++i)             (int j = 0; j < n; ++j)                 (ll m = 0; m < (1<<(n*n)); ++m)                     dp[i][j][m] = -1;         ll answer = 0;         (int = 0; < n; ++i)             (int j = 0; j < n; ++j)                 answer = (answer + f(i, j, setbit(0, i, j))) % mod;         cout << answer << endl;     } }