Puzzle Loop Solver

考虑对边进行 BFS 来模拟手动求解的推导过程。

具体来说，对于每一条边，有三个状态：$-1$（不确定是否选），$0$（确定不选），$1$（确定选）。如果一条边被确定为 $0$ 或 $1$，尝试向外扩展。

不妨考虑确定的边是横向的，纵向同理。如果确定为 $0$，分别考虑：

• 左侧/右侧点：
  • 如果只剩下一条未确定边，且剩余边均确定为 $0$：将这条未确定边确定为 $0$；
  • 如果只剩下一条未确定边，且剩余边恰有一条确定为 $1$：将这条未确定边确定为 $1$。
  • 如果没有未确定边，且恰有一条确定为 $1$：返回无解。
• 上/下方格：
  • 如果剩余未确定边全确定为 $0/1$ 恰好满足要求：将它们全部确定为 $0/1$。
  • 如果剩余未确定边全确定为 $0$ 仍过大或全确定为 $1$ 仍过小：返回无解。

如果确定为 $1$：

• 左侧/右侧点：
  • 如果有多于三条确定为 $1$：返回无解。
  • 如果恰有两条确定为 $1$：将其他未确定边确定为 $0$。
  • 如果只剩下一条未确定边，且剩余边恰有一条确定为 $1$：将这条未确定边确定为 $1$。
  • 如果没有未确定边，且恰有一条确定为 $1$：返回无解。
• 上/下方格同理。

特别的，在过程中维护一个并查集，如果发现合并成环，立刻判断局面是否是解。如果是，结束；如果不是，返回无解。

如果 BFS 结束没有出现无解，则枚举所有边连通块。如果有一个连通块度数和是奇数，返回无解。

然后在外面套一个 DFS，每次枚举所有未确定边，将其钦定为一个状态，如果出现无解，则必然是另一个状态。我们称该过程为一次增广。在一次 DFS 中不断增广直到无法增广，然后考虑所有边钦定为某一个状态后能够确定多少条边，先选择确定边数多的，钦定它，然后递归 DFS。

这样，求解除每月谜题以外的谜题都可以在不递归 DFS 的情况下得解，用时通常小于 1 秒。大部分每月谜题也可以在 1 分钟内得解。但是会有少部分题需要很长时间。

为了进一步优化，我们观察到直接 BFS 并不能够利用到所有能够通过 BFS 获取到的信息。例如：

• 考虑钦定一条边 $e_1$ 的状态为 $k_1$。
• 此时我们额外确定了两条边 $e_2,e_3$ 的状态分别为 $k_2,k_3$。
• 进而利用这两条边，我们确定 $e_4$ 的状态为 $k_4$。
• 我们有命题 $e_1=k_1\Rightarrow e_4=k_4$。显然，应该有逆否命题 $e_4=\lnot k_4\Rightarrow e_1=\lnot k_1$。
• 但是，如果确定 $e_4=\lnot k_4$ 并不能确定 $e_2$ 和 $e_3$，就无法通过直接 BFS 得到该逆否命题。

因此我们手动将这个逆否命题加进去。具体来说：

• 对每一条边取每一个状态 $(e,k)$ 维护一个邻接表。
• 在 BFS 的时候不仅遍历相邻的点/方格进行扩展，同时遍历这个邻接表进行扩展。
• 在 DFS 的时候，如果无法直接通过 BFS 发现矛盾，则对于每一条未知边 $e$，枚举其状态 $k=0/1$，然后从它开始 BFS，将搜到的所有边加入 $(e,k)$ 的邻接表中。如果在所有边的 BFS 都结束之后没有邻接表发生变化，则按照之前的原则递归 DFS；否则继续尝试寻找矛盾。

这样相比之前的做法可以达到一定程度上的优化。这里使用了之前出现过的，并且 solver 的 DFS 次数比较多的每月谜题进行测试：

• 2023.9 的每月谜题：原 solver 在 $50,000$ 次 DFS 内没有出解；新 solver 在 $137$ 次 DFS 后出解，耗时 $44.3$ 秒。
• 2023.1 的每月谜题：原 solver 在 $3,286$ 次 DFS 后出解，耗时 $282.2$ 秒；新 solver 在 $55$ 次 DFS 后出解，耗时 $17.7$ 秒。
• 2023.7 的每月谜题：原 solver 在 $1,306$ 次 DFS 后出解，耗时 $55.1$ 秒；新 solver 在 $25$ 次 DFS 后出解，耗时 $10.5$ 秒。

其他数据基本没有区别，均可在 1 分钟内出解。

为避免侵权，不提供测试数据。代码经过了重构和修改，可以 在 GitHub 上 查看。目前仅支持在 Windows 下运行。