//AUTOR: PRZEMYSŁAW SAŁĘGA
//konfiguracja końcowa:
//1, 4, 7
//2, 5, 8
//3, 6

#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

struct element {
    char wartosc;
    int index_i;
    int index_j;
    element() {};
    element(char wartosc, int index_i, int index_j) {
        this->index_i = index_i;
        this->index_j = index_j;
        this->wartosc = wartosc;
    }
};

class puzzle {
    char tab[3][3];
public:
    void wypelnij_losowo();
    void wypelnij();
    void wypisz_tab();
    int total_manhattan_distance();
    bool ruch();
};

int puzzle::total_manhattan_distance() {
    int suma = 0;
    int j = 0;
    for (int i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (tab[i][j] == ' ') {
                continue;
            }
            int i_koncowe;
            int j_koncowe;
            if (tab[i][j] == '1') {
                i_koncowe = 0;
                j_koncowe = 0;
            }
            else if (tab[i][j] == '2') {
                i_koncowe = 1;
                j_koncowe = 0;
            }
            else if (tab[i][j] == '3') {
                i_koncowe = 2;
                j_koncowe = 0;
            }
            else if (tab[i][j] == '4') {
                i_koncowe = 0;
                j_koncowe = 1;
            }
            else if (tab[i][j] == '5') {
                i_koncowe = 1;
                j_koncowe = 1;
            }
            else if (tab[i][j] == '6') {
                i_koncowe = 2;
                j_koncowe = 1;
            }
            else if (tab[i][j] == '7') {
                i_koncowe = 0;
                j_koncowe = 2;
            }
            else if (tab[i][j] == '8') {
                i_koncowe = 1;
                j_koncowe = 2;
            }
            suma += abs(i_koncowe - i);
            suma += abs(j_koncowe - j);
        }
    }
    return suma;
}

void puzzle::wypelnij_losowo() {
    char wykorzystane[9];
    int l_wykorzystanych = 0;
    int j = 0;
    for (int i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            bool jeszcze_raz = false;
            do {
                jeszcze_raz = false;
                tab[i][j] = (rand() % 9) + 49;
                if (tab[i][j] == '9') {
                    tab[i][j] = ' ';
                }
                for (int k = 0; k < l_wykorzystanych; k++) {
                    if (wykorzystane[k] == tab[i][j]) {
                        jeszcze_raz = true;
                        break;
                    }
                }
                if (jeszcze_raz == false) {
                    wykorzystane[l_wykorzystanych] = tab[i][j];
                    l_wykorzystanych++;
                }
            } while (jeszcze_raz == true);
        }
    }
}

void puzzle::wypelnij() {
    int j;
    for (int i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            cout << "Podaj wartosc dla [" << i << "][" << j << "](Wpisz 9, aby ustawic wolne pole): ";
            cin >> tab[i][j];
            if (tab[i][j] == '9') {
                tab[i][j] = ' ';
            }
        }
    }
}

void puzzle::wypisz_tab() {
    int j = 0;
    for (int i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            cout << tab[i][j] << " ";
        }
        cout << endl;
    }
}

bool puzzle::ruch() {
    int i, j;               //indeksy pustego pola na planszy
    vector<element> lista;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (tab[i][j] == ' ') {
                break;
            }
        }
        if (i != 3 && j != 3) {
            if (tab[i][j] == ' ') {
                break;
            }
        }
    }
    if (j != 0) {
        element e(tab[i][j-1], i, j - 1);
        lista.push_back(e);
    }
    if (j != 2) {
        element e(tab[i][j+1], i, j + 1);
        lista.push_back(e);
    }
    if (i != 0) {
        element e(tab[i-1][j], i - 1, j);
        lista.push_back(e);
    }
    if (i != 2) {
        element e(tab[i+1][j], i + 1, j);
        lista.push_back(e);
    }
    int stara_suma = total_manhattan_distance();
    int i_tmp, j_tmp;
    int licznik = 0;
    vector<int> sumy;
    do {    //sprawdzanie sum odległości
        //zamiana na nowy element
        cout << endl << "Sprawdzenie " << licznik + 1 << ". sasiada." << endl;
        i_tmp = i;
        j_tmp = j;
        i = lista[licznik].index_i;
        j = lista[licznik].index_j;
        tab[i][j] = ' ';
        tab[i_tmp][j_tmp] = lista[licznik].wartosc;
        cout << "Tablica: " << endl;
        wypisz_tab();
        cout << "Suma odleglosci: ";
        cout << total_manhattan_distance() << endl;
        sumy.push_back(total_manhattan_distance()); //zapisanie nowej sumy
        //powrót do poprzedniego stanu
        tab[i][j] = lista[licznik].wartosc;
        tab[i_tmp][j_tmp] = ' ';
        i = i_tmp;
        j = j_tmp;
        licznik++;
    } while (licznik != lista.size());
    //sprawdzanie najmniejszej sumy odległości ze wszystkich możliwych
    int min_indeks = 0; //indeks najmniejszej sumy w wektorze
    int min = sumy[min_indeks]; //najmniejsza suma
    int k;
    for (k = 1; k < sumy.size(); k++) {
        if (sumy[k] < min) {
            min = sumy[k];
            min_indeks = k;
        }
    }
    //zamiana z "sąsiadem", który da najmniejszą sumę odległości
    if (min <= total_manhattan_distance()) {
        cout << "Zamiana z " << min_indeks + 1 << ". sasiadem." << endl << endl;
        i_tmp = i;
        j_tmp = j;
        i = lista[min_indeks].index_i;
        j = lista[min_indeks].index_j;
        tab[i][j] = ' ';
        tab[i_tmp][j_tmp] = lista[min_indeks].wartosc;
        cout << "Tablica: " << endl;
        wypisz_tab();
        cout << "Suma odleglosci: ";
        cout << total_manhattan_distance() << endl;
        if (total_manhattan_distance() == 0) {
            cout << "Koniec!" << endl;
            return false;
        }
        return true;
    }
    cout << "Blokada w minimum lokalnym." << endl;
    return false;
}

int main() {
    srand((unsigned int)time(NULL));
    int kolejna_proba = 1;
    do {
        puzzle p;
        int wybor;
        cout << "[1] Wypelnij losowo" << endl;
        cout << "[2] Wypelnij z klawiatury" << endl;
        cout << "[3] O programie" << endl;
        cout << "[0] Wyjdz." << endl;
        cin >> wybor;
        switch (wybor) {
        case 1:
            p.wypelnij_losowo();
            break;
        case 2:
            p.wypelnij();
            break;
        case 3:
            cout << "Autor programu: Przemyslaw Salega." << endl;
            system("PAUSE");
            system("cls");
            continue;
        case 0:
            system("PAUSE");
            return 0;
        }
        cout << "Tablica: " << endl;
        p.wypisz_tab();
        cout << "Suma odleglosci: ";
        cout << p.total_manhattan_distance() << endl;
        bool czy_kontynuowac = true;
        do {
            czy_kontynuowac = p.ruch();
        } while (czy_kontynuowac == true);
        cout << "Jeszcze raz? [1] Tak, [Dow. liczba] Nie: ";
        cin >> kolejna_proba;
        system("cls");
    } while (kolejna_proba == 1);
    system("PAUSE");
}