Calculate possible "snake" passwords

Question

We all know the new password screens on mobile devices. It consists of a matrix of dots, that are to be connected.

A unique password is a vector of points. The points can be connected to themselves with the following restrictions:

• A point can be connected to only 1 other point
• A line will be forced to connect to a closer point if the destination point and the free point are on the same line. An example:

Since the middle point was not connected before, There was no way to connect the top point to the bottom.

The first restriction makes this a find the number of graphs that are trees. It's the second restriction that I cannot find a way to calculate.

Is there a easier way to calculate the amount of possibilities, or the only way is to generate all possibilities and count them?

Answer 1

Since the general problem of counting simple paths in an undirected graph is #P-complete, and as was pointed out in the comments, the similar problem of counting self-avoiding paths in a grid is conjectured to be hard, I think it is appropriate to think about how we can solve the problem in o((n*n)!) time (with n=3 in your case).

We have to keep in mind an additional special case that usually applies on "real" smartphones:

• We can go across intermediate nodes, if those have already been visited. For example it is usually possible to go (0,0) -> (1,1) -> (0,2) -> (2,0)

There is a simple dynamic programming approach that should be able to solve at least up to the 5x5 case: Let f(i,j,visited) be the number of ways when we are currently at vertex (i,j) and visited is the set of nodes we visited earlier. We can compute f using dynamic programming by trying all possible moves and recursing. We can represent visited as a bitmask. The total number of possibilities will then be sum(i,j, f(i,j, {(i,j)})).

Here are the results:

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

Seems to be pretty secure from a information-theoretical standpoint even for n = 4.

Below is the C++ implementation I used. Since the result can be pretty large, the program computes it modulo some large primes, so that we can reconstruct the solution using the 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 <= i && i < 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;
    for (int di = -i; di <= n-i-1; ++di)
        for (int dj = -j; dj <= n-j-1; ++dj) {
            if ((di == 0 && dj == 0) || abs(__gcd(di, dj)) != 1) continue;
            int i2 = i + 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;
    }
    for (int p = lo; p <= hi; ++p) {
        mod = primes[p];
        cout << mod << " " << flush;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                for (ll m = 0; m < (1<<(n*n)); ++m)
                    dp[i][j][m] = -1;
        ll answer = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                answer = (answer + f(i, j, setbit(0, i, j))) % mod;
        cout << answer << endl;
    }
}