UI zadanie 2

#include<stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#include <time.h>

int pocetKrokov = 0;


/*naplnenie tabulky heuristickou funkciou, ktorej hodnoty predstavuju pocet pohybov konom ktoré sa daju urobit z daneho policka*/
void napln(int **heuristika, int velkost)
{
    int i, j;
    for (i = 0; i < velkost; i++)
    {
        for (j = 0; j < velkost; j++)
        {
            if (i == 0 || j == 0 || i == velkost - 1 || j == velkost - 1)
            {
                heuristika[i][j] = 4;
            }
            else
            {
                if (i == 1 || j == 1 || i == velkost - 2 || j == velkost - 2)
                {
                    heuristika[i][j] = 6;
                }
                else
                {
                    heuristika[i][j] = 8;
                }
            }

        }
    }
    heuristika[0][0] = 2;
    heuristika[0][velkost - 1] = 2;
    heuristika[velkost - 1][0] = 2;
    heuristika[velkost - 1][velkost - 1] = 2;

    heuristika[0][1] = 3;
    heuristika[1][0] = 3;
    heuristika[0][velkost - 2] = 3;
    heuristika[1][velkost - 1] = 3;
    heuristika[velkost - 2][0] = 3;
    heuristika[velkost - 1][1] = 3;
    heuristika[velkost - 1][velkost - 2] = 3;
    heuristika[velkost - 2][velkost - 1] = 3;

    heuristika[1][1] = 4;
    heuristika[velkost - 2][1] = 4;
    heuristika[1][velkost - 2] = 4;
    heuristika[velkost - 2][velkost - 2] = 4;
}
int eulerovKon(int x, int y, int movei, int **riesenie, int xPosun[8], int yPosun[8], int **heuristika,int velkost);

/*funkcia ktora vrati ci je pohyb dovoleny, alebo nie (ci nepojde mimo sachovnice, alebo ci nepojde na policko na ktorom uz bol)*/
bool safe(int x, int y, int **riesenie,int velkost)
{
    return (x >= 0 && x < velkost && y >= 0 && y < velkost && riesenie[x][y] == -1);
}


/*vytvorenie a naplnenie tabuliek potrebných na prehladanie sachovnice + zavolanie funkcie*/
bool priprava(int zaciatok_x, int zaciatok_y,int velkost)
{
    int **riesenie, **heuristika, x, y,i,j;
    heuristika = (int**)malloc(sizeof(int*)*velkost);
    riesenie = (int**)malloc(sizeof(int*)*velkost);
    for (i = 0; i < velkost; i++)
    {
        heuristika[i] = (int*)malloc(sizeof(int)*velkost);
        riesenie[i] = (int*)malloc(sizeof(int)*velkost);
        for (j = 0; j < velkost; j++)
        {
            riesenie[i][j] = -1;
        }
    }
    napln(heuristika, velkost);


    int xPosun[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; //posuny na sachovnici v smere x, nasiel som na internete ze tato postupnost krokov vedie v priemere k najrychlejsiemu rieseniu
    int yPosun[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };


    riesenie[zaciatok_x][zaciatok_y] = 0; //zapisanie prvej pozicie do tabulky riesenia


    if (eulerovKon(zaciatok_x, zaciatok_y, 1, riesenie, xPosun, yPosun, heuristika,velkost) == false) //volanie rekurzivnej funkcie na riesenie problemu eulerovho kona
    {
        if (pocetKrokov < 2000000){
            printf("Solution does not exist\n");
            return false;
        }
        else
        {
            printf("program prekrocil maximalne mnozstvo krokov(2 000 000)\n"); //obmedzenie poctu krokov na 2 000 000
            pocetKrokov = 0;
            return false;
        }
    }
    else

    /*vypis riesenia*/
    for (i = 0; i < velkost; i++)
    {
        for (j = 0; j < velkost; j++)
            printf(" %2d ", riesenie[i][j]);
        printf("\n");
    }
    printf("\n");

    return true;
}
/*rekurzivna funkcia riesiaca problem eulerovho kona*/
int eulerovKon(int x, int y, int movei, int **riesenie, int xPosun[8], int yPosun[8], int **heuristika,int velkost) {
    int k, i, j, pom, next_x, next_y, poradie[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    if (movei == velkost * velkost) //velkost hlbky ktoru chceme dosiahnut
        return true;

    /*bubble sort na zoradenie heuristiky*/
    for (i = 0; i < 8; i++) {
        for (j = 0; j < 7; j++) {
            if (safe(x + xPosun[poradie[j]], y + yPosun[poradie[j]], riesenie,velkost) &&
                safe(x + xPosun[poradie[j + 1]], y + yPosun[poradie[j + 1]], riesenie,velkost)) {
                if (heuristika[x + xPosun[poradie[j]]][y + yPosun[poradie[j]]] >
                    heuristika[x + xPosun[poradie[j + 1]]][y + yPosun[poradie[j + 1]]]) {

                    pom = poradie[j];
                    poradie[j] = poradie[j + 1];
                    poradie[j + 1] = pom;
                }
            }
            else {
                if (!safe(x + xPosun[poradie[j]], y + yPosun[poradie[j]], riesenie,velkost) &&
                    safe(x + xPosun[poradie[j + 1]], y + yPosun[poradie[j + 1]], riesenie,velkost)) {
                    pom = poradie[j];
                    poradie[j] = poradie[j + 1];
                    poradie[j + 1] = pom;
                }
            }
        }
    }
    /*zanáranie do krokov od tych s najmensim cislom heurisiky az po tie s najvacsim*/
    for (k = 0; k < 8; k++) {
        next_x = x + xPosun[poradie[k]];
        next_y = y + yPosun[poradie[k]];
        if (safe(next_x, next_y, riesenie,velkost)) {
            for (i = 0; i < 8; i++) {                       //odčítanie jednotky od okolitych pozicii v heuristike. kedze vybereme poziciu, tak z ostatnych z ktorych sa na nu dalo stupit vieme stupit o jeden menej
                if (safe(x + xPosun[i], y + yPosun[i], riesenie,velkost)) {
                    heuristika[x + xPosun[i]][y + yPosun[i]] -= 1;
                }
            }
            if (pocetKrokov<2000000)                    //obmedzenie na pocet krokov kolko moze funkcia vykonat
                {
                    pocetKrokov++;
                }
            else
            {
                return false;
            }
            riesenie[next_x][next_y] = movei;
            if (eulerovKon(next_x, next_y, movei + 1, riesenie, xPosun, yPosun, heuristika, velkost) == true){ //ked sa da riesit dalej, tak sa vnor o jednu hlbku dalej
                return true;
            }
            else {          //ked sa neda postupovat dalej, tak do tabulky s riesenim zapis -1 ako pozicia na ktorej kon nebol a vyber dalsi krok
                riesenie[next_x][next_y] = -1;
                for (i = 0; i < 8; i++) {
                    if (safe(x + xPosun[i], y + yPosun[i], riesenie,velkost)) {
                        heuristika[x + xPosun[i]][y + yPosun[i]] += 1;              //pripocitanie k heuristike, kedze sa vraciame z bodov na ktorych sme stali
                    }
                }
            }
        }
    }

    return false;
}

int main()
{
    int  i,velkost,x,y;

    printf("Zadajte veLkost strany Sachovnice:\n");
    scanf("%d", &velkost);
    srand(time(NULL));
    for ( i = 0; i < 10; i++)
    {

        x = rand() % velkost;
        y = rand() % velkost;
        printf("Riesenie:%d\n",i+1);
        printf("Pozicia X:%d Y:%d\n", x,y);
        priprava(y, x, velkost);
    }
    system("PAUSE");
    return 0;
}