Andreyiy

NU stiu nu stiu eu dastea :))

wmutex

Ok, am gasit o pozitie cu 16 campuri atacate:

Cb6, Cd8, Na7, Na8, Tb7, Tc8, Db8, Rc7

Evident, mai sunt inca 8 variante echivalente, care se pot obtine din oglindiri ale pozitiei.

wmutex

Ok, in continuare e codul -- scris in C standard, in mai multe parti -- pentru rezolvarea problemei.

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_initializeaza_atac(struct tabla *a);
void sah_afiseaza(struct tabla *t);
int  sah_calculeaza_nr_atacuri(struct tabla *t, struct tabla *atac);

/* Urmatoarele functii calculeaza numarul de atacuri posibile pentru
* piesa indicata de linia si coloana respectiva. Functiile returneaza -1
* in caz de eroare. Campurile atacate sunt marcate cu '1' in tabelul
* atac (restul fiind marcate cu spatiu, ca de obicei)
*/
int sah_calcul_nr_atacuri_nebun (int linie, int coloana, struct tabla *tbl, struct tabla *atac);
int sah_calcul_nr_atacuri_cal (int linie, int coloana, struct tabla *tbl, struct tabla *atac);
int sah_calcul_nr_atacuri_turn (int linie, int coloana, struct tabla *tbl, struct tabla *atac);
int sah_calcul_nr_atacuri_dama (int linie, int coloana, struct tabla *tbl, struct tabla *atac);
int sah_calcul_nr_atacuri_rege (int linie, int coloana, struct tabla *tbl,  struct tabla *atac);

wmutex

int main(void)
{

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

    n = 1;
    srand(time(NULL));

    for(; n!=64; ) {
        sah_initializeaza(&t2);
        n_2 = sah_calculeaza_nr_atacuri(&t2, &a);

        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_atacuri(&t2, &a);
                            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 atacuri: %d\n", n);
            sah_afiseaza(&t);
            /*
            printf("Pozitii atacate:\n");
            sah_afiseaza(&a);
            */
        }
    }

    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];
    }
}

wmutex

void sah_initializeaza_atac (struct tabla *a)
{
    int linie, coloana;


    if(a==NULL) {
        return;
    }

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

wmutex

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");
}

wmutex

int  sah_calculeaza_nr_atacuri(struct tabla *t, struct tabla *atac)
{
    int linie, coloana;
    int nr_atacuri = 0;

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

    sah_initializeaza_atac(atac);

    for(linie=0; linie<NR_LINII; ++linie) {
        for(coloana=0; coloana<NR_COLOANE; ++coloana) {
            switch(t->tabla[coloana][linie]) {
            case 'N':
                sah_calcul_nr_atacuri_nebun(linie, coloana, t, atac);
                break;
            case 'C':
                sah_calcul_nr_atacuri_cal(linie, coloana, t, atac);
                break;
            case 'T':
                sah_calcul_nr_atacuri_turn(linie, coloana, t, atac);
                break;
            case 'D':
                sah_calcul_nr_atacuri_dama(linie, coloana, t, atac);
                break;
            case 'R':
                sah_calcul_nr_atacuri_rege(linie, coloana, t, atac);
                break;
            }
        }
    }

    for(linie=0; linie<NR_LINII; ++linie) {
        for(coloana=0; coloana<NR_COLOANE; ++coloana) {
            nr_atacuri += (atac->tabla[coloana][linie]=='1'?1:0);
        }
    }
    return nr_atacuri;
}

wmutex

int sah_calcul_nr_atacuri_nebun (int linie, int coloana, struct tabla *tbl, struct tabla *atac)
{
    int l, c;
    int nr_atacuri = 0;

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

    for(l=linie+1, c=coloana+1; (l<NR_LINII) && (c<NR_COLOANE); ++l, ++c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie+1, c=coloana-1; (l<NR_LINII) && (c>=0); ++l, --c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie-1, c=coloana+1; (l>=0) && (c<NR_COLOANE); --l, ++c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie-1, c=coloana-1; (l>=0) && (c>=0); --l, --c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }

    return nr_atacuri;
}

wmutex

int sah_calcul_nr_atacuri_cal (int linie, int coloana, struct tabla *tbl, struct tabla *atac)
{
    int l, c;
    int nr_atacuri = 0;

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

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

    return nr_atacuri;
}

wmutex

int sah_calcul_nr_atacuri_turn (int linie, int coloana, struct tabla *tbl, struct tabla *atac)
{
    int l, c;
    int nr_atacuri = 0;

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

    for(l=linie, c=coloana+1; c<NR_COLOANE; ++c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie, c=coloana-1; c>=0; --c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie+1, c=coloana; l<NR_LINII; ++l) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie-1, c=coloana; l>=0; --l) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }

    return nr_atacuri;
}

wmutex

int sah_calcul_nr_atacuri_dama (int linie, int coloana, struct tabla *tbl, struct tabla *atac)
{
    int l, c;
    int nr_atacuri = 0;

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

    for(l=linie+1, c=coloana+1; (l<NR_LINII) && (c<NR_COLOANE); ++l, ++c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie+1, c=coloana-1; (l<NR_LINII) && (c>=0); ++l, --c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie-1, c=coloana+1; (l>=0) && (c<NR_COLOANE); --l, ++c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie-1, c=coloana-1; (l>=0) && (c>=0); --l, --c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }

    for(l=linie, c=coloana+1; c<NR_COLOANE; ++c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie, c=coloana-1; c>=0; --c) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie+1, c=coloana; l<NR_LINII; ++l) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }
    for(l=linie-1, c=coloana; l>=0; --l) {
        ++nr_atacuri;
        atac->tabla[c][l] = '1';
        if(tbl->tabla[c][l] != ' ') {
            break;
        }
    }

    return nr_atacuri;
}

wmutex

int sah_calcul_nr_atacuri_rege (int linie, int coloana, struct tabla *tbl,  struct tabla *atac)
{
    int l, c;
    int nr_atacuri = 0;

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

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


    return nr_atacuri;
}