题解 P7087 【[NWRRC2013]Intellectual Property】

· · 题解

对于两个 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 函数，可以随自己的喜好实现。