#include <cstring>
#include <iostream>

using namespace std;

struct rightWay {
    int A[3][3];
    rightWay *next;
    rightWay *prev;
};

struct allWays {
    int A[3][3];
    allWays *next;
};

const int position[4][2] = {
        {-1, 0},
        {0,  1},
        {1,  0},
        {0,  -1}
};

int findZeroPosition(int startPosition[3][3], int *zeroX, int *zeroY) {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (startPosition[i][j] == 0) {
                *zeroX = i;
                *zeroY = j;
                return 0;
            }
    return -1;
}

bool compareArrays(int A[3][3], int B[3][3]) {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (A[i][j] != B[i][j])
                return false;
    return true;
}

bool compareArrays(int **swapResult, allWays *headAllWays) {

    while (headAllWays != nullptr) {
        int flag = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                if (headAllWays->A[i][j] == swapResult[i][j])
                    flag++;
            }

        if (flag == 9)
            return true;
        headAllWays = headAllWays->next;
    }
    return false;
}

int **swap(int currentArray[3][3], int zeroX, int zeroY, int move) {

    int **array = new int *[3];
    for (int i = 0; i < 3; i++) {
        array[i] = new int[3];
    }
    memcpy(array, currentArray, 9 * sizeof(int));

    array[zeroX][zeroY] = currentArray[zeroX + position[move][0]][zeroY + position[move][1]];
    array[zeroX + position[move][0]][zeroY + position[move][1]] = 0;

    return array;
}

int main() {
    rightWay *headRightWay, *currentRightWay = new rightWay;
    allWays *headAllWays, *currentAllWays = new allWays;

    int startPosition[3][3] = {
            {5, 8, 3},
            {4, 0, 2},
            {7, 6, 1}
    };

    memcpy(currentRightWay->A, startPosition, 9 * sizeof(int));
    headRightWay = currentRightWay;

    memcpy(currentAllWays->A, startPosition, 9 * sizeof(int));
    headAllWays = currentAllWays;

    int endPosition[3][3] = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 0}
    };

    int zeroX, zeroY;
    findZeroPosition(startPosition, &zeroX, &zeroY);

    do {
        for (int i = 0; i < 4; i++) {
            if ((zeroX + position[i][0] >= 0) && (zeroX + position[i][0] <= 2) && (zeroY + position[i][1] >= 0) &&
                (zeroY + position[i][1] <= 2)) {
                int **swapResult = swap(currentAllWays->A, zeroX, zeroY, i);
                if (!compareArrays(swapResult, headAllWays)) {
                    cout << "ok!";
                    return 0;
                }
            }
        }

    } while (!compareArrays(currentRightWay->A, endPosition));

    return 0;
}