USACO 3.2 Magic Squares

Typical solution for ‘minimum’ or ‘maximum’ problems:

• Greedy
• Dynamic Programming
• BFS

For this problem, it is not obvious about overlapping sub-problems so BFS is an obvious solution.
The tricky parts are:

• How to encode the transforms (the A, B, and C).
• How to test if a state has been explored.
• How to perform backtracking once we have hit desired states.

I think this problem is very good on testing implementation skills, as the algorithm itself is not very complicated.

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>
#include <queue>

using namespace std;

vector<vector<int>> tx = {
    {8,7,6,5,4,3,2,1}, // A
    {4,1,2,3,6,7,8,5}, // B
    {1,7,2,4,5,3,6,8}, // C
};

struct state {
    vector<int> val;
    state() {
        val = vector<int>(8, 0);
        std::iota(val.begin(), val.end(), 1);
    }
};

queue<state> q;
const int MAX_STATES = 40500;
vector<bool> visited(MAX_STATES, false);
// Stores state_hash:(previous state hash : transform index)
vector<vector<int>> trace(MAX_STATES, vector<int>(2, -1));
// Stores state_hash:transform index
vector<int> transforms(MAX_STATES, 0);
vector<int> factorial = {1, 1, 2, 6, 24, 120, 720, 5040};
// Expected state (read from input.).
vector<int> target(8, 0);

int steps;

int hashing(vector<int> state) {
    int sum = 1, t = 0;
    for (int i = 0; i < 7; ++i) {
        t = 0;
        for (int j = i + 1; j < 8; ++j) {
            if(state[j] < state[i]) ++t;
        }
        sum += t * factorial[7 - i];
    }
    return sum;
}

void bfs() {
    int hash = 0;
    trace[1][1] = 0;
    visited[1] = true;
    q.emplace(state());

    while(!q.empty()) {
        auto cur = q.front();q.pop();
        hash = hashing(cur.val);
        if(cur.val == target)
            break;
        for (int i = 0; i < 3; ++i) {
            state next;
            for (int j = 0; j < 8; ++j) {
                next.val[j] = cur.val[tx[i][j] - 1];
            }
            int next_state_hash = hashing(next.val);
            if (visited[next_state_hash]) continue;
            q.push(next);
            visited[next_state_hash] = true;
            trace[next_state_hash][0] = hash;
            trace[next_state_hash][1] = i;
        }
    }

    while (trace[hash][0] != -1) {
        transforms[steps]= trace[hash][1];
        hash = trace[hash][0];
        ++steps;
    }
}

void output(ofstream &fout) {
    cout << steps << endl;
    fout << steps << endl;
    for(int i = steps - 1; i >= 0; --i) {
        char c = transforms[i] + 'A';
        cout << c; fout << c;
    }

    fout << endl; cout << endl;
}

int main() {
    ifstream fin("msquare.in");
    ofstream fout("msquare.out");
    for (int i = 0; i < 8; ++i) {
        fin >> target[i];
    }
    bfs();
    output(fout);
}