自动搬运

查看原文

来自洛谷，原作者为

	Starlight237 [Drawer/auth]EgcqEzGZV+k435xMKiYIpABsjWY0ln/huv6DW7QW9Qw=

搬运于2025-08-24 22:26:32，当前版本为作者最后更新于2021-10-29 14:44:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于两个 $9\times9$ 数独谜题（不管是否有解）$A,B$，定义 $A$ 和 $B$ 等价当且仅当 $A$ 可以通过下列操作进行若干次变换后成为 $B$。

• 选择两个数字 $x,y$，将所有 $x$ 变成 $y$，所有 $y$ 变成 $x$。
• 在 $(1,2,3),(4,5,6),(7,8,9)$ 三个三元组中，选择两个，作为整体交换以它为下标的行。
• 选择在同一个三元组中的两个数 $x,y$，交换谜题的第 $x$ 行和第 $y$ 行。
• 在 $(1,2,3),(4,5,6),(7,8,9)$ 三个三元组中，选择两个，作为整体交换以它为下标的列。
• 选择在同一个三元组中的两个数 $x,y$，交换谜题的第 $x$ 列和第 $y$ 列。
• 把 $A$ 转置。

现在给定 $n(n\le20)$ 个数独谜题，判断它们两两是否等价。若等价，还需要输出一种变换的方法。D x y 表示将两个数字交换，R a b 表示整体交换三元组 $(3a-2,3a-1,3a),(3b-2,3b-1,3b)$ 对应的行，r a b 表示交换两个行，同理有 C a b 和 c a b 作为列操作。F 表示取转置。

下面考虑如何比较两个数独 $A,B$，首先不考虑具体的数字，交换行的操作一共有 1296 种，交换列的操作也一共有 1296 种。$A$ 同时做行变换和列变换等价于 $A$ 只做行变换，$B$ 只做列变换，因此可以把 $A$ 做行变换的结果用 Hash 表存起来即可，然后枚举对 $B$ 的列变换，看 $B'$ 是否在 Hash 表中出现过。类似 BSGS 算法的思想。

转置操作最多会进行一次，枚举是否转置即可。

由于任意两个数字可以交换，我们只需要设计一种对数值不敏感的 Hash，比如 $H(s_1,...,s_9)=H_0(s_1)+...+H_0(s_n)$，或者异或等，其中 $s_i$ 表示数字 $i$ 在数独上出现的位置集合，可以用一个 unsigned int128 压缩起来。若比较的时候发现两个 Hash 值不相等，那一定（在当前变换方法下）不等价，否则暴力比较两个 $\{s_i\}$ 集合。具体实现可以用 std::map，std::unordered_map 等 STL 结构。$H_0$ 是一个单值 Hash 函数，可以随自己的喜好实现。