用DFS解决最终幻想13-2时钟谜题

最近在补 XGP 中的最终幻想13-2时，遇到一个时钟谜题，感觉挺有意思，就像尝试用搜索算法将其解决。

问题描述

如下图所示，有一个时钟，包含个结点，每个节点有一个数字标识，玩家最开始可以任意选择一个结点，选择后，该结点被消除且指针会指向该结点的位置，根据该节点的数字值 n 分裂为两根指针分别向顺时针方向和逆时针方向旋转 n 个的单位长度。此后每次玩家只能选择指针指向的结点，选择结点后结点被消除，两指针合并指向选择结点的位置并按上述描述进行分裂和旋转，玩家需要将所有节点消除才能胜利。

注：玩家无法选择已经被消除的结点，若分裂旋转后的两指针均位于已被消除的结点位置，则判定游戏失败。

算法思路

本问题很容易想到利用深度优先搜索来解决，选择一个结点作为开始，如第一次选择 12 点钟位置的结点，（以下为了方便，按结点在时钟中排布位置 n 称作结点 n）该结点值为 5，则选中后分别向顺时针和逆时针方向旋转到达结点 5 和 结点 7，这就产生了两个分支（相当于二叉树的左右子树），分别选择这两个结点继续搜索，若结点到达了一个已被访问过的结点（即该结点已被消除），则终止该方向上的搜索，并进行回溯，将路径上的该结点删除，并将访问标志复原。

若路径上的结点个数已经达到 12，即所有节点均被成功消除，则该路径为一个解路径，将该结果保存并回溯继续进行搜索，直到尝试了所有可能性，算法结束。

完整代码

#include<iostream>
#include<vector>
using namespace std;class Solution {
private:int n;vector<int> path; // 搜索路径vector<vector<int>> res; // 成功路径void dfs(vector<int>& sequences, vector<bool>& visited, int ind) {if (visited[ind]) { // 已访问过return;}path.emplace_back(ind);visited[ind] = true;if (path.size() == n) { // 成功访问所有元素res.emplace_back(path);}int p1 = (ind - sequences[ind] + n) % n; // 逆时针方向旋转后的下标int p2 = (ind + sequences[ind]) % n; // 顺时针方向旋转后的下标if (p1 == p2) {dfs(sequences, visited, p1);}else {dfs(sequences, visited, p1);dfs(sequences, visited, p2);}// 回溯path.pop_back();visited[ind] = false;}
public:vector<vector<int>> clockPuzzle(vector<int>& sequences) {n = sequences.size();vector<bool> visited;for (int i = 0; i < n; ++i) { // 选取一个结点作为开始结点visited.assign(n, false); // 重置visited数组 dfs(sequences, visited, i);}return res;}
};int main() {Solution S;vector<int> sequences = { 5,5,3,6,2,1,4,3,4,5,3,4 };auto res = S.clockPuzzle(sequences);for (const auto& re : res) {for (const auto& r : re) {cout << r << " ";}cout << endl << endl;}
}

结果分析

以下为示例图中问题的所有解路径，经验证，符合条件。