计算可能的“蛇”密码

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

唯一的密码是点的向量。这些点可以连接到自身，但有以下限制：

• 一个点只能连接到另外 1 个点
• 如果目标点和空闲点在同一条线上，则线路将被迫连接到更近的点。一个例子：

由于之前没有连接中间点，因此无法将顶部点与底部连接。

第一个限制使其查找树图的数量。这是第二个限制，我找不到计算方法。

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

由于计数的一般问题简单的路径在无向图中是#P-完成，正如评论中指出的那样，类似的计数问题网格中的自回避路径被推测很难，我认为考虑如何在 o((n*n)!) 时间内解决问题是适当的（在你的情况下 n=3）。

我们必须记住通常适用于“真实”智能手机的额外特殊情况：

• We can如果已经访问过中间节点，则遍历中间节点。例如，通常可以 (0,0) -> (1,1) -> (0,2) -> (2,0)

有一种简单的动态规划方法应该能够解决至少 5x5 的情况：让f(i,j,访问过)是当我们当前位于顶点 (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;
    }
}