[C] il giro del cavallo

[ndakota]

Ciao ragazzi, sto facendo gli esercizi che mi propone il libro sul C dei fratelli deitel. Mi sto imbattendo nel problema del giro del cavallo, che consiste nello scoprire se un cavallo riesce a muoversi per tutta una scacchiera senza mai passare sulle stesse caselle. Inizialmente l'esercizio chiede un implementazione senza "euristica dell'accessibilità" cioè senza dare un minimo di logica alle mosse del cavallo ma facendolo muovere nella prima posizione valida. Bene, una volta finita questa prima implementazione il programma mi segnalava che il mio cavallo era passato su 42 caselle su 64. Ottimista stavo iniziando a pensare a come implementarlo con l'"euristica dell'accessibilità" quando mi è venuta l'idea di stampare la scacchiera e da qui ho notato un problema, infatti calcolando gli 1 sulla scacchiera noto che son 32 non 42 come la variabile count mi dice. Non riesco proprio a trovare l'errore, qualcuno mi aiuta?

#include<stdio.h>
#include<stdlib.h>
#define DIM 8

int move(int, int);
void showBoard(void);

int board[DIM][DIM] = { 0 };
int horizontal[DIM] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[DIM] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int main()
{
    int currentRow = 4, currentColumn = 3, moveNumber, count = 0;

    do
    {
        moveNumber = move(currentRow, currentColumn);

        if(moveNumber != -1)
        {
            currentRow += vertical[ moveNumber ];
            currentColumn += horizontal[ moveNumber ];
            board[ currentRow ][ currentColumn ] = 1;
            count++;
        }

    } while(moveNumber != -1);

    printf("%d\n", count);
    showBoard();

    return 0;
}

int move(int currentRow, int currentColumn)
{
    int moveNumber;

    for(moveNumber = 0; moveNumber < DIM; ++moveNumber)
    {
        currentRow += vertical[ moveNumber ];
        currentColumn += horizontal[ moveNumber ];

        if(currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7 && board[ currentRow ][ currentColumn ] == 0)
            return moveNumber;
    }

    return -1;
}

void showBoard(void)
{
    int i, j;

    for(i = 0; i < DIM; ++i)
    {
        for(j = 0; j < DIM; ++j)
            printf("%d\t", board[ i ][ j ]);

        printf("\n");
    }
}

[DanieleC88]

Perché calcoli più volte caselle già visitate. Prova così:

        if (moveNumber != -1)
        {
            currentRow += vertical[ moveNumber ];
            currentColumn += horizontal[ moveNumber ];

            /* Se non abbiamo ancora visitato la casella */
            if (board[ currentRow ][ currentColumn ] != 1)
            {
                        board[ currentRow ][ currentColumn ] = 1;
                        count++;
            }
        }

[ndakota]

scusa eh ma mica faccio già il controllo nella funzione move?? nell'if c'è un board[currentRow][currentColumn] == 0

[DanieleC88]

Non farmi domande sugli scacchi, ma in move() tu modifichi i valori di currentRow e currentColumn ad ogni ciclo, alla fine invece restituisci l'offset da aggiungere alle posizioni iniziali, mentre tu hai controllato l'offset relativo all'ultimo spostamento...

Magari prova così:

    for (moveNumber = 0; moveNumber < DIM; ++moveNumber)
    {
        int tempRow = currentRow + vertical[ moveNumber ];
        int tempColumn = currentColumn + horizontal[ moveNumber ];

        if (IN_BOUNDS(tempRow) && IN_BOUNDS(tempColumn) && (board[ tempRow ][ tempColumn ] == 0))
        {
            return moveNumber;
        }
    }

dove IN_BOUNDS() è:

#define IN_BOUNDS(x) ((x) >= 0 && (x) < DIM)

Non so se era la logica che volevi, ma secondo me è lì l'errore, e infatti lo spostamento mi restituisce valori diversi, per un totale di 27 spostamenti (senza l'if che ti dicevo prima).

[ndakota]

oddio quel define mi fa rabbrividire
la mia logica è:
passo alla funzione la posizione del cavallo e itero sulle posizioni possibili. alla prima valida ritorno quella mossa e effettuo davvero lo spostamento(nel main)..

[Oceans11]

Originariamente inviato da DanieleC88

Perché calcoli più volte caselle già visitate.

ndakota non mi sembri convinto, forse non vi siete capiti ma devo dire che ha perfettamente ragione! in pratica in move tu vorresti provare tutte le mosse fino a trovarne un valida a partire dalla posizione in cui move è chiamato, invece nel ciclo for modifichi continuamente quel valore nel fare i tentativi! Quindi basta "resettare" al valore iniziale currentRow e currentColumn all'inizio di ogni iterazione

con il C sto a zero ma così dovrebbe andare:

int move(int row, int column) {
    int moveNumber;

    for (moveNumber = 0; moveNumber < DIM; ++moveNumber) {
        int currentRow = row;
        int currentColumn = column;
        currentRow += vertical[ moveNumber ];
        currentColumn += horizontal[ moveNumber ];

        if (currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7 && board[ currentRow ][ currentColumn ] == 0)
            return moveNumber;
    }

    return -1;
}

Spero di essere stato di aiuto....e di non aver detto scemenze!



[EDIT] mi sono dimenticato di dire che count dovrebbe partire da 1 e non da zero, dato che tu devi segnare anche la posizione di partenza no?[/EDIT]

[ndakota]

scusa ma le passo per valore, nel main dovrebbero tornare ad avere il loro valore no??

[DanieleC88]

Originariamente inviato da ndakota

oddio quel define mi fa rabbrividire

E perché?

Originariamente inviato da ndakota

scusa ma le passo per valore, nel main dovrebbero tornare ad avere il loro valore no??

No, rileggi il mio ultimo post, ad ogni ciclo continui a spostare relativamente all'ultima posizione vista. Prova ad assegnare due variabili temporanee come ti ho scritto su (e come ti ha ripetuto Oceans11).

[ndakota]

Originariamente inviato da DanieleC88

Perché calcoli più volte caselle già visitate. Prova così:

        if (moveNumber != -1)
        {
            currentRow += vertical[ moveNumber ];
            currentColumn += horizontal[ moveNumber ];

            /* Se non abbiamo ancora visitato la casella */
            if (board[ currentRow ][ currentColumn ] != 1)
            {
                        board[ currentRow ][ currentColumn ] = 1;
                        count++;
            }
        }

hai ragione così funziona.. anche se ancora non ne capisco il motivo visto che quel controllo c'è già dentro la funzione

[DanieleC88]

No, io dicevo l'ultimo post che segnala l'errore dentro la move()... Tu in pratica ti sposti dalla posizione iniziale ad una nuova posizione: se questa non è accettabile, ti sposti da questa ad un'altra posizione ancora, e così via, finché non ne trovi una accettabile o non finisci le possibilità di movimento. In pratica, devi conservare le variabili al loro valoro iniziale, se le modifichi continuamente non rispecchi il vero movimento della pedina: prova a simulare con carta e penna quel ciclo e immaginare le posizioni occupate...

[Oceans11]

Il problema è che tu fai così:

parti dalla posizione p0 e cerchi la prossima libera. diciamo che la prossima libera è p2 e ci arrivi muovendoti con la mossa 1 orizzontale, -2 verticale (è la seconda nella tua disposizione)

tu però provi innanzitutto la prima mossa (2, -1) e finisci in p1 che mettiamo sia occupata e quindi non va bene.

Nell'iterazione successiva le tue coordinate assolute (currentRow e currentColumn) avranno il valore di p1 e non di p0, e da lì sballa tutto.

spero di essere stato più chiaro di prima, anche se ne dubito

[ndakota]

sono tonto ragazzi.. secondo me al main vengono ritornate solo posizioni valide.. tu mi dici il contrario.. non capisco

[Oceans11]

Originariamente inviato da ndakota

secondo me al main vengono ritornate solo posizioni valide

Non c'è dubbio! non ho detto il contrario...

però nei rispetti del tuo algoritmo non sono le prime posizioni valide, ma posizioni prese un pò a caso!

sicuro ogni volta che dal main richiami move() sia currentRow che currentColumn descrivono la posizione giusta. Il problema è che però nel ciclo for di move() sta posizione rimane quella giusta solo nel caso in cui è la prima mossa quella valida ([2,-1] a quanto hai dichiarato tu negli array)

[DanieleC88]

Fai una cosa: stampati le posizioni.

        if (IN_BOUNDS(tempRow) && IN_BOUNDS(tempColumn) && (board[ tempRow ][ tempColumn ] == 0))
        {
            printf(" -> Sono move(), ho trovato una posizione valida in [%d; %d].\n", tempColumn, tempRow);
            return moveNumber;
        }

        if (moveNumber != -1)
        {
            currentRow += vertical[ moveNumber ];
            currentColumn += horizontal[ moveNumber ];

            printf("Sono main(), mi sto spostando in [%d; %d].\n", currentColumn, currentRow);
            board[ currentRow ][ currentColumn ] = 1;
            count++;
        }

e vedrai che il funzionamento non è quello che ti aspetteresti...

[ndakota]

ragazzi finalmente ho capito.. non capivo proprio quello che volevate dirmi.. guardavo da tutt'altra parte..
ora l'ho fatto così, non è bellissimo però non volevo sbattermi e cambiarlo tutto.

#include<stdio.h>
#include<stdlib.h>
#define DIM 8

int move(int, int);
void showBoard(void);

int board[DIM][DIM] = { 0 };
int horizontal[DIM] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[DIM] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int main()
{
    int currentRow = 4, currentColumn = 3, moveNumber, count = 1;
    board[ currentRow ][ currentColumn ] = 1;

    do
    {
        moveNumber = move(currentRow, currentColumn);

        if(moveNumber != -1)
        {
            currentRow += vertical[ moveNumber ];
            currentColumn += horizontal[ moveNumber ];

            if (board[ currentRow ][ currentColumn ] != 1)
            {
                board[ currentRow ][ currentColumn ] = 1;
                count++;
            }
        }

    } while(moveNumber != -1);

    printf("%d\n", count);
    showBoard();

    return 0;
}

int move(int currentRow, int currentColumn)
{
    int moveNumber;

    for(moveNumber = 0; moveNumber < DIM; ++moveNumber)
    {
        currentRow += vertical[ moveNumber ];
        currentColumn += horizontal[ moveNumber ];

        if(currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7 && board[ currentRow ][ currentColumn ] == 0)
            return moveNumber;

        else
        {
            currentRow -= vertical[ moveNumber ];
            currentColumn -= horizontal[ moveNumber ];
        }
    }

    return -1;
}

void showBoard(void)
{
    int i, j;

    for(i = 0; i < DIM; ++i)
    {
        for(j = 0; j < DIM; ++j)
            printf("%d\t", board[ i ][ j ]);

        printf("\n");
    }
}

vi sembra gisuto? come risultati mi da 28 e 28 sia la stampa di count che gli 1 nella stampa della matrice..
un'altra cosa: ho fatto bene secondo voi ad usare la matrice ed i due array globali? so che non bisognerebbe usare varibili globali ma mi sembrava brutto in questo caso passare 5 variabili alla funzione per così poche righe di codice..

[DanieleC88]

Non era più facile mettere due nuove variabili invece che 4 controlli?

Per il resto, sì, va bene anche usare variabili globali per quello che stai facendo, non è "rischioso" ed è solo un esercizio, quindi vai tranquillo.

[Oceans11]

Originariamente inviato da ndakota

ragazzi finalmente ho capito

bene!

Originariamente inviato da DanieleC88

Non era più facile mettere due nuove variabili...

beh come dargli torto??? anch'io avrei (ed in effetti...ho) usato 2 variabili temporanee piuttosto che quel ramo else..."a che pro sottrarre quei valori se li hai appena sommati?"

Cmq penso sia fatto bene!quantomeno all'altezza di ciò che dovrebbe essere richiesto dall'esercizio. Suppongo che il capitolo che stai affrontando sia roba di array e/o cicli for, quindi per adesso almeno non puoi ne devi fare altro, giusto? (sto pensando a una qualche struttura dati creata ad hoc)

Per quanto riguarda le variabili globali...beh vengo dal java, ma a quanto vedo sono da evitare il più possibile in ogni linguaggio.

Originariamente inviato da ndakota

mi sembrava brutto in questo caso passare 5 variabili alla funzione per così poche righe di codice..

eh pure io la penso allo stesso modo...però per quel poco che ho visto è proprio una particolarità del c....per sbaglio mi è capitato l'occhio su qualche funzione di libreria di quelle con 134 parametri, un delirio!!!

[ndakota]

Originariamente inviato da Oceans11

Cmq penso sia fatto bene!quantomeno all'altezza di ciò che dovrebbe essere richiesto dall'esercizio. Suppongo che il capitolo che stai affrontando sia roba di array e/o cicli for, quindi per adesso almeno non puoi ne devi fare altro, giusto? (sto pensando a una qualche struttura dati creata ad hoc)

no infatti per adesso ho fatto tutta la parte di controllo e gli array. Nei prossimi capitoli mi pare ci siano: stringhe, puntatori, strutture dati, file. Sono cose che ho già fatto a scuola ma adesso le voglio riprendere da solo BENE.

eh pure io la penso allo stesso modo...però per quel poco che ho visto è proprio una particolarità del c....per sbaglio mi è capitato l'occhio su qualche funzione di libreria di quelle con 134 parametri, un delirio!!!

massi per un esercizietto del genere penso vada bene così. E poi non mi è mai capitato che mi servissero programmando OO, mi sembra una particolarità dei linguaggi procedurali.

risposte in neretto

[Oceans11]

Anch'io sono convinto che vada bene così. Oltretutto se devi studiarlo per bene, ora fossi in te mi concentrerei di più sulla parte relativa al capitolo "in corso" senza dimenticare quelli precedenti. Se cominci a saltare pezzi perchè bene o male già li conosci allora non approfondisci mai!

cmq prometto che un giorno o l'altro mi metto e studierò per bene il c anch'io!

[ndakota]

bah io ho sempre letto dei fratelli Deitel poi potrei sbagliarmi