奇数码问题

形式化题目

给定一个奇数 $n$ 以及两个 $n \times n$ 的网格矩阵。网格中恰好包含一个 $0$ （代表空格）以及 $1 \sim n^2-1$ 的所有整数各一个。

每次操作可以将空格与上下左右相邻的一个数字交换位置。判断是否存在一系列操作，使得第一个网格变换为第二个网格。

正解

思路

直接在 $n \times n$ 网格上做广度优先搜索的状态空间规模为 $(n^2)! / 2$ ，当 $n \geqslant 3$ 时无法直接搜索，需要寻找局面变换过程中的不变量。

1. 展开为一维序列

将网格按行优先顺序（从左到右、从上到下）展开为一维数组，并忽略代表空格的数字 $0$ ，得到一个包含 $1 \sim n^2-1$ 这 $n^2-1$ 个数的置换序列。

我们考查空格移动对该序列逆序对数量的影响：

空格左右移动：
- 空格与同行的左右相邻元素交换。
- 在忽略 $0$ 的一维序列中，所有非 $0$ 数字的相对前后顺序完全没有发生改变。
- 因此，左右移动不改变一维序列的逆序对数量。
空格上下移动：
- 空格向上或向下移动一格，相当于空格在一维网格序列中向前或向后跨越了 $n$ 个位置。
- 除去空格自身，该操作等价于：某个非 $0$ 数字跨过了恰好 $n-1$ 个其他非 $0$ 数字。
- 设这 $n-1$ 个数字中，原本与该数字构成逆序对的有 $k$ 个，构成顺序对的有 $(n-1)-k$ 个。跨越后，原本的逆序变成顺序，原本的顺序变成逆序。
- 逆序对总数的变化量为：
  $\Delta = ((n - 1) - k) - k = (n - 1) - 2k$
- 模 $2$ 意义下：
  $\Delta \equiv n - 1 \pmod 2$
- 题目给定 $n$ 为奇数，因此 $n - 1$ 一定是偶数！
- 即 $\Delta \equiv 0 \pmod 2$ 。因此，上下移动同样不改变一维序列逆序对数量的奇偶性。

2. 结论与充要性

综上，无论空格如何移动，忽略 $0$ 后的一维序列的逆序对总数的奇偶性恒定不变。

代数置换群理论保证了其充分性：在 $n$ 为奇数的棋盘上，所有逆序对奇偶性相同的局面处于同一个连通分量中。因此：

两个局面互相可达 $\iff$ 两个局面忽略 $0$ 后的序列具有相同的逆序对奇偶性。

只需对两个局面分别求出忽略 $0$ 后序列的逆序对数，利用归并排序在 $O(n^2 \log n)$ 时间内完成统计并比对其奇偶性即可。

图示解析

下面以 $n=3$ 的网格为例，展示空格在上下移动时，非 $0$ 元素在一维序列中的跨越过程：

text

1
2
3
4
5
6
7网格状态 A：                  网格状态 B（0 下移，与 7 交换）：
1  2  3                       1  2  3
0  4  6   ====== 0 下移 =====> 7  4  6
7  5  8                       0  5  8

忽略 0 后的一维序列 A: [1, 2, 3, 4, 6, 7, 5, 8]
忽略 0 后的一维序列 B: [1, 2, 3, 7, 4, 6, 5, 8]

在忽略 $0$ 的一维序列中，数字 $7$ 跨过了前面的数字 $4$ 和 $6$ （共 $n-1=2$ 个数字），其他元素的相对顺序保持不变。由于跨过的元素个数 $n-1=2$ 为偶数，逆序对数量的奇偶性保持不变。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-18 10:00
# update_at: 2026-04-18 10:00

import sys


def count_inversions(arr: list[int]) -> int:
    """求一维数组的逆序对总数。利用归并排序在 O(M log M) 时间内统计。"""
    temp = [0] * len(arr)

    def merge_sort(left: int, right: int) -> int:
        if left >= right:
            return 0
        mid = (left + right) // 2
        inv = merge_sort(left, mid) + merge_sort(mid + 1, right)
        i, j, k = left, mid + 1, left
        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]
                i += 1
            else:
                temp[k] = arr[j]
                inv += mid - i + 1
                j += 1
            k += 1
        while i <= mid:
            temp[k] = arr[i]
            i += 1
            k += 1
        while j <= right:
            temp[k] = arr[j]
            j += 1
            k += 1
        arr[left : right + 1] = temp[left : right + 1]
        return inv

    return merge_sort(0, len(arr) - 1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    for n in data:
        total_cells = n * n
        # 读取两个局面并忽略空格 0
        seq1 = [v for _ in range(total_cells) if (v := next(data)) != 0]
        seq2 = [v for _ in range(total_cells) if (v := next(data)) != 0]

        inv1 = count_inversions(seq1)
        inv2 = count_inversions(seq2)

        is_reachable = (inv1 & 1) == (inv2 & 1)
        out.append("TAK" if is_reachable else "NIE")

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-18 10:40
 * update_at: 2026-10-06 14:05
 */
// 奇数码问题：n 为奇数时，两个局面可达 <=> 忽略空格 0 后的
// 两个一维序列逆序对个数奇偶性相同。用归并排序统计逆序对。

#include <cstdio>

typedef long long ll;

const int MAXN = 505;      // n < 500
const int MAXM = MAXN * MAXN;

ll a[MAXM];   // 第一个局面忽略 0 后的一维序列
ll b[MAXM];   // 第二个局面忽略 0 后的一维序列
ll tmp1[MAXM]; // 归并辅助数组（局面一）
ll tmp2[MAXM]; // 归并辅助数组（局面二）

// 归并排序统计 a[l..r] 的逆序对个数，过程中会排好序
ll merge_sort_count(ll *arr, ll *tmp, ll l, ll r) {
    if (l >= r)
        return 0;
    ll mid = (l + r) >> 1;
    // 逆序对 = 左半内部的 + 右半内部的 + 合并时跨越两半的
    ll inv = merge_sort_count(arr, tmp, l, mid) + merge_sort_count(arr, tmp, mid + 1, r);
    ll i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            tmp[k] = arr[i];
            i++;
        } else {
            // arr[j] 比左边剩下的 mid - i + 1 个数都小，各构成一个逆序对
            tmp[k] = arr[j];
            inv += mid - i + 1;
            j++;
        }
        k++;
    }
    while (i <= mid) {
        tmp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= r) {
        tmp[k] = arr[j];
        j++;
        k++;
    }
    for (ll p = l; p <= r; p++)
        arr[p] = tmp[p];
    return inv;
}

// 读入一个 n*n 局面（n 已在 main 中读出），把非 0 数字依次存入 arr，返回长度
ll read_board(ll *arr, int n) {
    ll len = 0;
    for (int i = 0; i < n * n; i++) {
        ll v;
        scanf("%lld", &v);
        if (v != 0) { // 忽略空格 0
            len++;
            arr[len] = v;
        }
    }
    return len;
}

int main() {
    int n;
    // 多组数据，读到文件末尾为止
    while (scanf("%d", &n) == 1) {
        ll len1 = read_board(a, n); // 第一个局面，忽略 0 后的长度
        ll len2 = read_board(b, n); // 第二个局面
        ll inv1 = merge_sort_count(a, tmp1, 1, len1);
        ll inv2 = merge_sort_count(b, tmp2, 1, len2);
        if ((inv1 & 1) == (inv2 & 1))
            printf("TAK\n");
        else
            printf("NIE\n");
    }
    return 0;
}

复杂度

时间复杂度：序列长度为 $M = n^2 - 1$ 。归并排序求解逆序对的时间复杂度为 $O(M \log M) = O(n^2 \log n)$ 。若有 $T$ 组数据，总时间复杂度为 $O(\sum n^2 \log n)$ ，足以在时限内通过。
空间复杂度：存储序列与归并辅助数组占用 $O(n^2)$ 空间，递归深度为 $O(\log n)$ ，总空间复杂度为 $O(n^2)$ 。

总结

奇数码问题的本质是通过“忽略空格看相对顺序”将二维网格变换转化为一维置换。因为棋盘边长 $n$ 为奇数，空格纵向跨越的非空数字个数 $n-1$ 为偶数，使得逆序对奇偶性成为无论如何移动都保持不变的“不变量”。利用归并排序高效统计逆序对即可在多项式时间内完成可达性判定。

目录

形式化题目

正解

思路

1. 展开为一维序列

2. 结论与充要性

图示解析

代码

复杂度

总结