计算可能的"蛇"密码

Question

我们都知道移动设备上的新密码屏幕.它由要连接的点阵组成.

唯一密码是点矢量.这些点可以通过以下限制连接到自己:

• 一个点只能连接到另一个点
• 如果目标点和自由点在同一条线上,则将强制线路连接到更近的点.一个例子:

由于之前未连接中间点,因此无法将顶点连接到底部.

第一个限制使得它可以找到树的图形数量.这是我无法找到计算方法的第二个限制.

是否有更简单的方法来计算可能性的数量,或者唯一的方法是生成所有可能性并计算它们？

Answer 1

由于在无向图中计算简单路径的一般问题是#P-complete,并且如评论中所指出的那样,计算网格中自我避免路径计数的类似问题被推测为难,我认为这是合适的考虑如何在o((n*n)!)时间内解决问题(在你的情况下n = 3).

我们必须记住通常适用于"真实"智能手机的其他特殊情况:

• 如果已经访问过中间节点,我们可以跨越中间节点.例如,通常可以去(0,0) - >(1,1) - >(0,2) - >(2,0)

有一种简单的动态编程方法应该能够解决至少5x5的情况:设f(i,j,visited)是我们当前在顶点(i,j)的方式的数量,并且visited是集合我们之前访问过的节点.我们可以通过尝试所有可能的移动和递归来使用动态编程来计算f.我们可以表示visited为位掩码.那么可能性的总数将是sum(i,j, f(i,j, {(i,j)})).

结果如下:

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

从信息理论的角度来看,即使对于n = 4,似乎也非常安全.

下面是我使用的C++实现.由于结果可能非常大,程序会计算出一些大质数的模数,因此我们可以使用中国剩余定理重构解.

#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;
    }
}