#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stdexcept>
#include <stdlib.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream& os, const T_container& v) { os << '{'; string sep; for (const T& x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif


//ACTION = 0 -> UP; 1-> DOWN; 2 - > LEFT 3-> RIGHT

int getInversion(vector<int> arr)
{
    int inv_count = 0;
    for (int i = 0; i < arr.size() - 1; ++i)
    {
        for (int j = i + 1; j < arr.size(); ++j)
        {
            inv_count += ((arr[i] > arr[j]) ? 1 : 0);
        }
    }
    return inv_count;
}

bool isSolvable(vector<vector<int>> curState, int N)
{
    int empty_row = -1;
    vector<int> arr;
    for (int i = 0 ; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (curState[i][j])
                arr.push_back(curState[i][j]);
            else empty_row = i;
        }
    }
    int inversions = getInversion(arr);
    if (N % 2 == 0 && (empty_row % 2 == !(inversions % 2)))
        return true;
    if (N % 2 == 1 && inversions % 2 == 0)
        return true;
    return false;
}

vector<vector<int>> readData(string filePath, int &N)
{
    vector<vector<int>> givenState;
    cout << "Care este calea fisierului de intrare: ";
    cin >> filePath;
    ifstream fin;
    fin.open(filePath, ios::in);
    if (!fin)
    {
        cerr << "Eroare la deschiderea fisierului " << filePath;
        exit(EXIT_FAILURE);
    }
    fin >> N;
    int i, j, x;
    for (i = 0 ; i < N; ++i)
    {
        vector<int> currentRow;
        for (j = 0; j < N; ++j)
        {
            fin >> x;
            currentRow.push_back(x);
        }
        givenState.push_back(currentRow);
    }
    fin.close();
    return givenState;
}

void printData(vector<vector<int>> curState, string outputFilePath)
{
    int N = curState.size();
    ofstream fout(outputFilePath, ios::out | ios::app);
    for (int i = 0 ; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            fout << curState[i][j] << " ";
        }
        fout << endl;
    }
    fout << endl;
    fout.close();
}

void getEmptyPosition(vector<vector<int>> curState, int N, int &xPoz, int &yPoz)
{
    for (int i = 0; i < N ; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (curState[i][j] == 0)
            {
                xPoz = i, yPoz = j;
                return;
            }
        }
    }
}

bool canMoveUp(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz]  == curState[0][i])
            return false;
    }
    return true;
}


bool canMoveDown(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz]  == curState[N - 1][i])
            return false;
    }
    return true;
}


bool canMoveLeft(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz]  == curState[i][0])
            return false;
    }
    return true;
}


bool canMoveRight(vector<vector<int>> curState, int N, int xPoz, int yPoz)
{
    for (int i = 0; i < N; ++i)
    {
        if (curState[xPoz][yPoz]  == curState[i][N - 1])
            return false;
    }
    return true;
}

void expandState(vector<vector<int>> curState, int N, vector<vector<int>> &child1, vector<vector<int>> &child2, vector<vector<int>> &child3, vector<vector<int>> &child4)
{
    //child1 - up child2 - down child3 - left child4 - right
    int xPoz, yPoz;
    getEmptyPosition(curState, N, xPoz, yPoz);
    if (canMoveUp(curState, N, xPoz, yPoz))
    {
        child1 = curState;
        swap(child1[xPoz - 1][yPoz], child1[xPoz][yPoz]);

    }
    if (canMoveDown(curState, N, xPoz, yPoz))
    {
        child2 = curState;
        swap(child2[xPoz + 1][yPoz], child2[xPoz][yPoz]);
    }
    if (canMoveLeft(curState, N, xPoz, yPoz))
    {
        child3 = curState;
        swap(child3[xPoz][yPoz - 1], child3[xPoz][yPoz]);
    }
    if (canMoveRight(curState, N, xPoz, yPoz))
    {
        child4 = curState;
        swap(child4[xPoz][yPoz + 1], child4[xPoz][yPoz]);
    }
}


void getChilds(vector<vector<int>> curState, int N, int &level, vector<pair<vector<vector<int>>, int>> &test, string outputFilePath)
{
    level++;
    vector<vector<int>> child1, child2, child3, child4;
    expandState(curState, N, child1, child2, child3, child4);
    dbg(child1, child2, child3, child4);
    if (!child1.empty())
    {
        printData(child1, outputFilePath);
        test.push_back(make_pair(child1, level));
    }
    if (!child2.empty())
    {
        printData(child2, outputFilePath);
        test.push_back(make_pair(child2, level));
    }
    if (!child3.empty())
    {
        printData(child3, outputFilePath);
        test.push_back(make_pair(child3, level));
    }
    if (!child4.empty())
    {
        printData(child4, outputFilePath);
        test.push_back(make_pair(child4, level));
    }
    dbg(level);
    for (auto itr = test.begin(); itr != test.end(); ++itr) {
        cout << *itr << "\n";
    }
}


bool checkForDuplicates(vector<pair<vector<vector<int>>, int>> Tree)
{
    for (auto itr = Tree.begin(); itr < Tree.end(); ++itr)
    {
        for (auto itr2 = itr + 1; itr2 < Tree.end(); ++itr2)
        {
            if ((itr->first) == (itr2->first))
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int N;
    vector<vector<int>> curState;
    string inputFilePath, outputFilePath;
    curState = readData(inputFilePath, N);
    dbg(curState);
    if (isSolvable(curState, N))
    {
        cout << "\nCare este calea fisierului de iesire: ";
        cin >> outputFilePath;
        printData(curState, outputFilePath);
        int level = 0;
        vector<pair<vector<vector<int>>, int>> Tree;
        Tree.push_back(make_pair(curState, level));
        dbg(Tree);
        getChilds(curState, N, level, Tree, outputFilePath);
        if (checkForDuplicates(Tree) == false)
        {
            cout << "Au fost gasite duplicate";
        }
        else cout << "Nu exista duplicate";
        return 0;
    }
    else
    {
        cerr << "Puzzle-ul introdus nu este rezolvabil!";
        exit(EXIT_FAILURE);
    }
}