Segment Rotation Optimization

When solving permutation puzzles that require rearranging contiguous segments within a fixed array, the branching factor can grow exponentially. For an array of length $n$, selecting a segment of length $i$ yields $n-i+1$ starting positions and $n-i$ insertion points. Accounting for symmetry (forward vs. backward movement equivalence), the effective branching factor per node is approximately $\sum_{i=1}^{n} \frac{(n-i)(n-i+1)}{2}$. For $n=15$, this totals 560 nodes per level. A brute-force search quickly exceeds memory and time limits beyond four depths. An Iterative Deepening A* (IDA*) approach efficiently narrows the search space by combining depth-first traversal with an admissible heuristic.

Heuristic Construction

The evaluation function must never overestimate the remaining moves required to reach the target state. In a sorted sequence, every adjacent pair $(a_i, a_{i+1})$ must satisfy $a_{i+1} = a_i + 1$. Transitions violate this condition. A single segment shift can disrupt at most three boundaries and repair up to three mismatches. Consequently, the minimum number of operations needed equals $\lceil \text{violations} / 3 \rceil$. This lower bound serves as the admissible heuristic $h(s)$. The search prunes any branch where $\text{current_depth} + h(s) > \text{max_depth}$.

#include <iostream>
#include <vector>
#include <algorithm>

constexpr int MAX_N = 20;
std::vector<int> sequence;
std::vector<std::vector<int>> snapshots;

int compute_lower_bound(const std::vector<int>& arr) {
    int misalignments = 0;
    for (size_t i = 0; i + 1 < arr.size(); ++i) {
        if (arr[i + 1] != arr[i] + 1) ++misalignments;
    }
    return (misalignments + 2) / 3; // Equivalent to ceil(misalignments / 3.0)
}

bool verify_state(const std::vector<int>& arr) {
    for (int i = 0; i < static_cast<int>(arr.size()); ++i) {
        if (arr[i] != i + 1) return false;
    }
    return true;
}

bool run_idastar(int current_level, int limit) {
    if (current_level + compute_lower_bound(sequence) > limit) return false;
    if (verify_state(sequence)) return true;

    const int n = sequence.size();
    snapshots.assign(limit + 1, std::vector<int>(n));

    for (int left = 0; left < n; ++left) {
        for (int right = left; right < n; ++right) {
            for (int insert_pos = right + 1; insert_pos < n; ++insert_pos) {
                // Save state before modification
                snapshots[current_level] = sequence;

                // Construct rotated array
                std::vector<int> temp(sequence.begin() + left, sequence.begin() + right + 1);
                std::vector<int> next_seq;
                
                for (int i = 0; i < left; ++i) next_seq.push_back(sequence[i]);
                for (int i = right + 1; i <= insert_pos; ++i) next_seq.push_back(sequence[i]);
                for (int x : temp) next_seq.push_back(x);
                for (int i = insert_pos + 1; i < n; ++i) next_seq.push_back(sequence[i]);

                sequence = next_seq;
                if (run_idastar(current_level + 1, limit)) return true;
                
                sequence = snapshots[current_level]; // Backtrack
            }
        }
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        int n;
        std::cin >> n;
        sequence.resize(n);
        for (int i = 0; i < n; ++i) std::cin >> sequence[i];

        int depth = 0;
        while (depth < 5 && !run_idastar(0, depth)) ++depth;
        
        if (depth >= 5) std::cout << "5 or more\n";
        else std::cout << depth << "\n";
    }
    return 0;
}

Intersecting Path Grid Puzzle

Puzzles involving cyclic shifts along predefined cross-shaped paths present a different combinatorial challenge. The board configuration maps to a linear array where eight distnict operations rotate specific index subsets. The objective is to equalize values across the central intersection region. Because the solution path length varies per test case, IDA* dynamically adjusts the search depth threshold until a valid configuration emerges.

Heuristic & Pruning Strategies

Within the eight central coordinates, track the frequency distribution of values ${1, 2, 3}$. Let $k$ represent the maximum frequency among these values. Since each cycle operation displaces exactly one element from the center and replaces it with another, the overlap count cannot increase by more than one per step. Thus, the admissible heuristic simplifies to $h(s) = 8 - k$.

To optimize traversal, cache the inverse mapping of each operation and skip reverting the immediately preceding move. Lexicographical ordering of the output sequence is guaranteed by enumerating operations in ascending index order during the depth-first expansion. This strcutural constraint ensures the first valid path found corresponds to the smallest dictionary-order result without requiring post-processing sorting.

#include <iostream>
#include <vector>
#include <algorithm>

constexpr int GRID_SIZE = 24;
std::vector<int> board(GRID_SIZE);

// Predefined rotation trajectories for each of the 8 paths
const std::vector<std::vector<int>> TRAJECTORIES = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};

// Central intersection indices
const std::vector<int> INTERSECTION = {6, 7, 8, 11, 12, 15, 16, 17};
// Bidirectional inverses to prune redundant backtracking
const std::vector<int> REVERSE_MAP = {5, 4, 7, 6, 1, 0, 3, 2};

std::vector<int> recorded_path;

int evaluate_state() {
    int frequencies[4] = {0};
    for (int idx : INTERSECTION) {
        frequencies[board[idx]]++;
    }
    int max_freq = 0;
    for (int val : frequencies) max_freq = std::max(max_freq, val);
    return 8 - max_freq;
}

bool verify_center() {
    int reference = board[INTERSECTION[0]];
    for (size_t i = 1; i < INTERSECTION.size(); ++i) {
        if (board[INTERSECTION[i]] != reference) return false;
    }
    return true;
}

void execute_shift(int path_idx) {
    const auto& trail = TRAJECTORIES[path_idx];
    int hold_value = board[trail[0]];
    for (int i = 0; i < 6; ++i) {
        board[trail[i]] = board[trail[i + 1]];
    }
    board[trail[6]] = hold_value;
}

bool search(int current_depth, int depth_limit, int prev_op) {
    if (current_depth + evaluate_state() > depth_limit) return false;
    if (verify_center()) return true;

    for (int op = 0; op < 8; ++op) {
        if (REVERSE_MAP[op] == prev_op) continue;
        
        execute_shift(op);
        recorded_path.push_back(op);
        
        if (search(current_depth + 1, depth_limit, op)) return true;
        
        // Undo shift for backtracking
        execute_shift(REVERSE_MAP[op]);
        recorded_path.pop_back();
    }
    return false;
}

int main() {
    while (std::cin >> board[0] && board[0]) {
        for (int i = 1; i < GRID_SIZE; ++i) std::cin >> board[i];

        int limit = 0;
        recorded_path.clear();
        while (!search(0, limit, -1)) {
            limit++;
        }

        if (limit == 0) std::cout << "No moves needed\n";
        else {
            for (int move : recorded_path) std::cout << static_cast<char>('A' + move);
            std::cout << "\n" << board[6] << "\n";
        }
    }
    return 0;
}