最近在补 XGP in Final Fantasy13-2时,Encounter a clock puzzle,感觉挺有意思,Like trying to solve it with a search algorithm.

问题描述

如下图所示,有一个时钟,contains a node,Each node has a numerical ID,Players can initially choose a node arbitrarily,选择后,The node is eliminated and the pointer points to the node's location,According to the numeric value of this node n Split into two pointers that rotate clockwise and counterclockwise respectively n unit length.After that each time the player can only select the node pointed to by the pointer,Nodes are eliminated after selecting them,The two pointers are merged to point to the location of the selected node and split and rotated as described above,Players need to eliminate all nodes to win.

注：Players cannot select nodes that have already been eliminated,If the two pointers after splitting and rotating are both located at the position of the node that has been eliminated,则判定游戏失败.

算法思路

This problem is easy to think of to use深度优先搜索来解决,Choose a node to start with,as the first choice 12 Node at the o'clock position,（以下为了方便,Arrange positions in the clock by nodes n node n）该结点值为 5,After selecting, rotate clockwise and counterclockwise respectively to reach the node 5 和 结点 7,This creates two branches（Equivalent to the left and right subtrees of a binary tree）,Select these two nodes respectively to continue the search,If the node reaches a node that has already been visited（That is, the node has been eliminated）,Then the search in that direction is terminated,并进行回溯,Delete this node on the path,and restore the access flag.

If the number of nodes on the path has been reached 12,That is, all nodes are successfully eliminated,Then the path is a solution path,Save that result and backtrack to continue searching,until all possibilities have been tried,算法结束.

完整代码

#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) {
     // All elements are successfully accessed
            res.emplace_back(path);
        }

        int p1 = (ind - sequences[ind] + n) % n; // Subscript after rotation counterclockwise
        int p2 = (ind + sequences[ind]) % n; // Subscript after clockwise rotation

        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) {
     // Pick a node as the starting node
            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;
    }
}

结果分析

Below are all the solution paths to the problem in the example graph,经验证,符合条件.