BFS

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
using namespace std;
 
enum class Action {L, R, U, D};
 
class State {
    vector<vector<int>> v {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
    int zx = 2, zy = 2;
 
public:
    State() {}
    State(const vector<vector<int>>& v0) {
        assert(v0.size() == 3);
        assert(v0[0].size() == 3);
        assert(v0[1].size() == 3);
        assert(v0[2].size() == 3);
        v = v0;
        zx = -1;
        zy = -1;
        for(int y=0; y<3; ++y)
            for(int x=0; x<3; ++x)
                if(v[y][x]==0)
                {
                    zx = x;
                    zy = y;
                }
        assert(zx>=0); assert(zy>=0);
    }
    bool operator<(const State& s) const {
        return v<s.v;
    }
    bool operator==(const State& s) const {
        return v==s.v;
    }
    vector<Action> actions() const {
        vector<Action> res;
        if(zx>0) res.push_back(Action::L);
        if(zx<2) res.push_back(Action::R);
        if(zy>0) res.push_back(Action::U);
        if(zy<2) res.push_back(Action::D);
        return res;
    }
    void apply(const Action& a) {
        if(a==Action::L)
        {
            assert(zx>0);
            swap(v[zy][zx], v[zy][zx-1]);
            --zx;
        }
        else if(a==Action::R)
        {
            assert(zx<2);
            swap(v[zy][zx], v[zy][zx+1]);
            ++zx;
        }
        else if(a==Action::U)
        {
            assert(zy>0);
            swap(v[zy][zx], v[zy-1][zx]);
            --zy;
        }
        else if(a==Action::D)
        {
            assert(zy<2);
            swap(v[zy][zx], v[zy+1][zx]);
            ++zy;
        }
        else
        {
            assert(0);
        }
    }
    void apply_random() {
        vector<Action> a = actions();
        apply(a[rand() % a.size()]);
    }
    void print() const {
        cout << v[0][0] << " " << v[0][1] << " " << v[0][2] << endl;
        cout << v[1][0] << " " << v[1][1] << " " << v[1][2] << endl;
        cout << v[2][0] << " " << v[2][1] << " " << v[2][2] << endl;
        cout << "(" << zx << "," << zy << ")" << endl;
    }
};
 
class Problem {
    State initial_s;
 
public:
    Problem(const State& is) {
        initial_s = is;
    }
    State initial_state() const {
        return initial_s;
    }
    bool is_goal(const State& s) const {
        return s==State();
    }
    vector<Action> actions(const State& s) const {
        return s.actions();
    }
    State result(const State& s, const Action& a) const {
        State res(s);
        res.apply(a);
        return res;
    }
    int action_cost(const State& s, const Action& a, const State& sprim) const {
        return 1;
    }
};
 
class Node {
public:
    State state;
    int path_cost;
    Node(const State& s, int path_c) {
        state = s;
        path_cost = path_c;
    }
};
 
vector<Node> expand(const Problem& problem, const Node& node)
{
    vector<Node> res;
    // TODO
    return res;
}
 
Node BFS(const Problem& problem) {
    // TODO
    return Node(State(), -1);
}
 
int main()
{
    vector<vector<int>> v(3, vector<int>(3));
    cin >> v[0][0] >> v[0][1] >> v[0][2];
    cin >> v[1][0] >> v[1][1] >> v[1][2];
    cin >> v[2][0] >> v[2][1] >> v[2][2];
    State is(v);
    Problem problem(is);
 
    Node node = BFS(problem);
    cout << node.path_cost << endl;
}

Do przetestowania:

        State({{1, 2, 3}, {4, 5, 0}, {7, 8, 6}}) -> 1
        State({{1, 3, 0}, {4, 2, 5}, {7, 8, 6}}) -> 4
        State({{4, 1, 2}, {7, 5, 3}, {8, 0, 6}}) -> 7
        State({{8, 7, 6}, {5, 4, 3}, {2, 1, 0}}) -> 30
        State({{2, 1, 3}, {4, 5, 6}, {7, 8, 0}}) -> -1