\(A\) の要素のうち唯一 \(0\) であるものが \(p\) 行 \(q\) 列に存在するとします。\(A(p,q)\) を置き換える整数を \(x\ (1\leq x\leq N)\) として、\(x\) の値を全探索することを考えます。各 \(x\) の値において \(N^3\) 通りすべての \((i,j,k)\) に対して条件を満たすか確認していると全体で \(O(N^4)\) かかってしまうので、何らかの高速化を加える必要があります。

ここで、\(N^3\) 通りある \((i,j,k)\) の組の中には、\(A(A(i,j),k)=A(i,A(j,k))\) であるかどうかが \(x\) の値に依存しないものが多く存在することに着目します。実際、\(A(A(i,j),k)=A(i,A(j,k))\) であるかどうかが \(x\) の値に依存するのは、以下のいずれかの条件が成立するときのみです：

• \(i=p\) かつ \(j=q\)
• \(A(i,j)=p\) かつ \(k=q\)
• \(j=p\) かつ \(k=q\)
• \(i=p\) かつ \(A(j,k)=q\)

\(A(i,j)=p\) といった形の条件は少々扱いづらいため取り除いてしまいます。すると、\(A(A(i,j),k)=A(i,A(j,k))\) であるかどうかが \(x\) の値に依存する可能性があるのは、以下のいずれかの条件が成立するときのみであるということができます：

• \(i=p\)
• \(k=q\)

これらのいずれかを満たす \((i,j,k)\) の組は \(O(N^2)\) 個しか存在しません。よって、それら以外の組に対して \(A(A(i,j),k)=A(i,A(j,k))\) かどうかは最初に判定しておいて、\(x\) を全探索する際にはその \(O(N^2)\) 個の組だけを考えれば、全体の計算量が \(O(N^3)\) になります。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector a(n, vector<int>(n));
    int p, q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            if (!a[i][j]) p = i, q = j;
            --a[i][j];
        }
    }
    auto check = [&](int i, int j, int k) -> bool {
        return a[a[i][j]][k] == a[i][a[j][k]];
    };
    for (int i = 0; i < n; i++) {
        if (i == p) continue;
        for (int k = 0; k < n; k++) {
            if (k == q) continue;
            for (int j = 0; j < n; j++) {
                if (!check(i, j, k)) {
                    cout << 0 << endl;
                    return 0;
                }
            }
        }
    }
    int ans = 0;
    for (int t = 0; t < n; t++) {
        a[p][q] = t;
        bool ok = true;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                ok &= check(p, j, k);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ok &= check(i, j, q);
            }
        }
        if (ok) ++ans;
    }
    cout << ans << endl;
}