wmutex

Nu stiu care e numarul maxim, dar se poate calcula o limita superioara a numarului maxim de mutari posibile. In cele ce urmeaza n(X) este numarul maxim de mutari posibile pentru o piesa de calitatea X pe tabla goala:

n(T) = 14
n(C) = 8
n(N) = 13
n(R) = 8
n(D) = 27

Desigur ca numarul cautat, n_max, este mai mice decat suma corespunzatoare:

n < 2*n(T) + 2*n(N) + 2*n(C) + n(R) + n(D) = 105

Asta se intampla fiindca piesele interactioneaza intre ele (piese care-si limiteaza -- eventual reciproc -- campurile accesibile).

Ok, nu-mi inchipui cum se poate calcula direct formula pozitiilor pieselor, dar cred ca se poate folosi urmatorul algoritm de aproximare succesiva a pozitiei optime:

1. Se distribuie aleatoriu piesele pe tabla.
2. Se calculeaza numarul de mutari posibile n_max_1 pentru configuratia data.
3. Fiecare piesa este mutata altundeva pe tabla si se recalculeaza numarul de mutari posibile n_max_2
4. Daca exista o piesa mutata pentru care n_max_2 > n_max_1 atnuci se pastreaza noua configuratie si se sare la pasul 2.
5. Daca nu exista nici o piesa mutata pentru care n_max_2 > n_max_1 atunci algoritmul se termina, si numarul maxim este n_max_1

Problema cu algoritmul e ca (dupa mintea mea) se "infunda" in situatii in care optimul local (care nu e optim global) nu poate fi depasit decat prin mutarea concomitenta a 2 piese, sau a 3 piese etc. Enumerarea tuturor pozitiilor posibile e cam... imposibila :D asa ca singura sansa e speranta ca distributia aleatoare a pieselor acopera suficiente cazuri. :-)

wmutex

Ok, am gasit pozitie cu 100 de mutari posibile:

1. Rd2, Db3, Ta5, Tc7, Nd4, Ne4, Cd6, Cf4

Programul inca mai cauta pozitia pentru 101 mutari posibile, desi nu prea cred c-o sa iasa... :D

wmutex

Ok, e oficial: programul meu nu e destul de destept sa gaseasca pozitii cu mai mult de 100 de mutari posibile. Cele 8 pozitii gasite decurg prin oglindiri verticale si/sau orizontale ale celor 2 pozitii esentiale:

1. Rd2, Db3, Ta5, Tc7, Nd4, Ne4, Cd6, Cf4
2. Rd2, Db3, Tg5, Tc7, Nd4, Ne4, Cd6, Cf4

Ramane provocarea pentru humans de-a gasi solutii mai bune. :D

wmutex

Pentru cine doreste, o sa postez in continuare (in mai multe parti) codul pe care l-am folosit -- scris in C standard.

wmutex

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

#define NR_LINII 8
#define NR_COLOANE 8
#define NR_CAMPURI (NR_LINII*NR_COLOANE)

struct tabla {
    /*
     * Piesele sunt codificate prin caractere: N=nebun, C=cal,
     * T=turn, D=dama, R=rege, spatiu=camp liber
     *
     * tabla[0][0] corespunde campului a1, tabla[7][7] corespunde
     * campului h8.
     */
    char tabla[NR_COLOANE][NR_LINII];
};


void sah_initializeaza (struct tabla *t);
void sah_afiseaza(struct tabla *t);
int  sah_calculeaza_nr_mutari(struct tabla *t);

/*
*Urmatoarele functii calculeaza numarul de mutari posibile pentru
* piesa indicata de linia si coloana respectiva. Functiile returneaza -1
* in caz de eroare.
*/
int sah_calcul_nr_mutari_nebun (int linie, int coloana, struct tabla *t);
int sah_calcul_nr_mutari_cal (int linie, int coloana, struct tabla *tbl);
int sah_calcul_nr_mutari_dama (int linie, int coloana, struct tabla *tbl);
int sah_calcul_nr_mutari_rege (int linie, int coloana, struct tabla *tbl);

wmutex

int main(void)
{

    struct tabla t1, t2, t;  /* table de sah */
    int n_1, n_2, n;  /* numarul de mutari posibile */
    int camp1, camp2;  /* Contor de campuri */
    int c1, l1, c2, l2;  /* coloane/linii pentru pozitii de piese */
    char piesa;  /* Piesa */

    printf("Pentru a iesi din program apasati CTRL+C\\n\\n");
    n = -1;
    srand(time(NULL));

    for(; n!=105; ) {
        sah_initializeaza(&t2);
        n_2 = sah_calculeaza_nr_mutari(&t2);

        do {
            t1  = t2;
            n_1 = n_2;

            /* Caut piese care pot fi mutate pe tabla. */
            for(camp1=0; camp1<NR_CAMPURI; ++camp1) {
                c1 = camp1 % NR_COLOANE;
                l1 = camp1 / NR_COLOANE;
    
                switch(t1.tabla[c1][l1]) {
                /* Campuri goale si piese negre */
                case ' ':
                    continue;

                case 'T':
                case 'C':
                case 'N':
                case 'D':
                case 'R':
                    /* Memorez piesa pe care o mut */
                    piesa = t1.tabla[c1][l1];

                    /* Generez incercari */
                    for(camp2=0; camp2<NR_CAMPURI; ++camp2) {
                        c2 = camp2 % NR_COLOANE;
                        l2 = camp2 / NR_COLOANE;

                        if(t1.tabla[c2][l2] == ' ') {
                            /* Mutare piesa */
                            t2 = t1;
                            t2.tabla[c2][l2] = piesa;
                            t2.tabla[c1][l1] = ' ';

                            n_2 = sah_calculeaza_nr_mutari(&t2);
                            if(n_2 > n_1) {
                                goto iteratia_urmatoare;
                            }
                        }
                    }
                    break;

                default:
                    printf("Eroare: piesa neidentificata.\\n");
                    return -1;
                }
            }
        iteratia_urmatoare:
            ;
        } while(n_2>n_1);

        if(n_1>n) {
            t = t1;
            n = n_1;
            printf("Numar maxim de mutari: %d\\n", n);
            sah_afiseaza(&t);
        }
    }

    return 0;

}

wmutex

void sah_initializeaza (struct tabla *t)
{
    int camp, linie, coloana;
    char piese[] = "TTNNCCDR";
    int index;

    if(t == NULL) {
        return;
    }

    for(linie=0; linie<NR_LINII; ++linie) {
        for(coloana=0; coloana<NR_COLOANE; ++coloana) {
            t->tabla[coloana][linie] = ' ';
        }
    }

    /* "Plantez" piese la intamplare (generatorul de numere aleatoare a fost "insamantat" deja) */
    for(index=0; piese[index]!='\0'; ++index) {
        do{
            camp = rand() % NR_CAMPURI;
            coloana = camp % NR_COLOANE;
            linie = camp / NR_COLOANE;
        } while (t->tabla[coloana][linie] != ' ');

        t->tabla[coloana][linie] = piese[index];
    }
}

void sah_afiseaza (struct tabla *t)
{
    int linie, coloana;
    char piesa;

    if(t == NULL) {
        return;
    }

    for(linie=0; linie<NR_LINII; ++linie) {
        for(coloana=0; coloana<NR_COLOANE; ++coloana) {
            piesa = t->tabla[coloana][linie];
            if(piesa !=' ') {
                printf(" %c%c%d", piesa, 'a'+coloana, 1+linie);
            }
        }
    }
    printf("\\n");
}

int  sah_calculeaza_nr_mutari(struct tabla *t)
{
    int linie, coloana;
    int nr_mutari = 0;

    if(t == NULL) {
        return -1;
    }

    for(linie=0; linie<NR_LINII; ++linie) {
        for(coloana=0; coloana<NR_COLOANE; ++coloana) {
            switch(t->tabla[coloana][linie]) {
            case 'N':
                nr_mutari += sah_calcul_nr_mutari_nebun(linie, coloana, t);
                break;
            case 'C':
                nr_mutari += sah_calcul_nr_mutari_cal(linie, coloana, t);
                break;
            case 'T':
                nr_mutari += sah_calcul_nr_mutari_turn(linie, coloana, t);
                break;
            case 'D':
                nr_mutari += sah_calcul_nr_mutari_dama(linie, coloana, t);
                break;
            case 'R':
                nr_mutari += sah_calcul_nr_mutari_rege(linie, coloana, t);
                break;
            }
        }
    }

    return nr_mutari;
}

wmutex

int sah_calcul_nr_mutari_nebun (int linie, int coloana, struct tabla *t)
{
    int l, c;
    int nr_mutari = 0;

    if(t == NULL) {
        return -1;
    } else if(linie<0 || linie>=NR_LINII || coloana<0 || coloana>=NR_COLOANE) {
        return -2;
    } else if(t->tabla[coloana][linie]!='N') {
        return -3;
    }

    for(l=linie+1, c=coloana+1; (l<NR_LINII) && (c<NR_COLOANE); ++l, ++c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie+1, c=coloana-1; (l<NR_LINII) && (c>=0); ++l, --c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie-1, c=coloana+1; (l>=0) && (c<NR_COLOANE); --l, ++c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie-1, c=coloana-1; (l>=0) && (c>=0); --l, --c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }

    return nr_mutari;
}

wmutex

int sah_calcul_nr_mutari_cal (int linie, int coloana, struct tabla *t)
{
    int l, c;
    int nr_mutari = 0;

    if(t == NULL) {
        return -1;
    } else if(linie<0 || linie>=NR_LINII || coloana<0 || coloana>=NR_COLOANE) {
        return -2;
    } else if(t->tabla[coloana][linie]!='C') {
        return -3;
    }

    l = linie-1; c = coloana-2;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+1; c = coloana-2;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie-1; c = coloana+2;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+1; c = coloana+2;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie-2; c = coloana-1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+2; c = coloana-1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie-2; c = coloana+1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+2; c = coloana+1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }

    return nr_mutari;
}

wmutex

int sah_calcul_nr_mutari_turn (int linie, int coloana, struct tabla *t)
{
    int l, c;
    int nr_mutari = 0;

    if(t == NULL) {
        return -1;
    } else if(linie<0 || linie>=NR_LINII || coloana<0 || coloana>=NR_COLOANE) {
        return -2;
    } else if(t->tabla[coloana][linie]!='T') {
        return -3;
    }

    for(l=linie, c=coloana+1; c<NR_COLOANE; ++c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie, c=coloana-1; c>=0; --c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie+1, c=coloana; l<NR_LINII; ++l) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie-1, c=coloana; l>=0; --l) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }

    return nr_mutari;
}

wmutex

int sah_calcul_nr_mutari_dama (int linie, int coloana, struct tabla *t)
{
    int l, c;
    int nr_mutari = 0;

    if(t == NULL) {
        return -1;
    } else if(linie<0 || linie>=NR_LINII || coloana<0 || coloana>=NR_COLOANE) {
        return -2;
    } else if(t->tabla[coloana][linie]!='D') {
        return -3;
    }

    for(l=linie+1, c=coloana+1; (l<NR_LINII) && (c<NR_COLOANE); ++l, ++c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie+1, c=coloana-1; (l<NR_LINII) && (c>=0); ++l, --c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie-1, c=coloana+1; (l>=0) && (c<NR_COLOANE); --l, ++c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie-1, c=coloana-1; (l>=0) && (c>=0); --l, --c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }

    for(l=linie, c=coloana+1; c<NR_COLOANE; ++c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie, c=coloana-1; c>=0; --c) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie+1, c=coloana; l<NR_LINII; ++l) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }
    for(l=linie-1, c=coloana; l>=0; --l) {
        if(t->tabla[c][l] == ' ') {
            ++nr_mutari;
        } else {
            break;
        }
    }

    return nr_mutari;
}

wmutex

int sah_calcul_nr_mutari_rege (int linie, int coloana, struct tabla *t)
{
    int l, c;
    int nr_mutari = 0;

    if(t == NULL) {
        return -1;
    } else if(linie<0 || linie>=NR_LINII || coloana<0 || coloana>=NR_COLOANE) {
        return -2;
    } else if(t->tabla[coloana][linie]!='R') {
        return -3;
    }

    l = linie-1; c = coloana-1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie-1; c = coloana;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie-1; c = coloana+1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie; c = coloana-1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie; c = coloana;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie; c = coloana+1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+1; c = coloana-1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+1; c = coloana;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }
    l = linie+1; c = coloana+1;
    if(!(l<0 || l>=NR_LINII || c<0 || c>=NR_COLOANE || t->tabla[c][l]!=' ')) {
        ++nr_mutari;
    }


    return nr_mutari;
}