[C++]Program-konik szachowy C++-problem z algorytmem

0

Witam,
Mam takie problem mam na zaliczenie labkow napisac kilka programow i z jednym z nich mam problem mianowicie takim:
Napisac program znajdujacy droge skoczka szachowego na szachownicy (skoczek musi znalezc sie na wszystkich polach bedac na ka dym polu tylko jeden raz).
Dane wejsciowe: rozmiar szachownicy oraz poczatkowa pozycja skoczka.

Oto mój kod, który naskrobałem:

 
#include <iostream>
#include <iomanip>
 
using namespace std;
 
// Prototypy funkcji
void InicjacjaTablicy(int **board, int xRozmiar, int yRozmiar);
void WyswietlTablice(int **board, int xRozmiar, int yRozmiar);
bool KonikSzachowy(int **board, int xx, int yy, int xRozmiar, int yRozmiar, int moveNum);
bool MoveIsValid(int **board, int xx, int yy, int xRozmiar, int yRozmiar);
 
int main()
{
    int xRozmiar, yRozmiar, xx, yy;
    int **board;
 
    // Pętla dopoki uzytkownik nie wprowadzi rozmiarów szachownicy
    do
    {
        cout << "Wprowadz wymiary tablicy(oddzielajac spacja):";
        cin >> xRozmiar >> yRozmiar;
    } while ((xRozmiar < 1) || (yRozmiar < 1));
 
    do
    {
        cout << "Wprowadz punkt startowy x wieksze od 1-poziomo:";
        cin >> xx;
    } while ((xx > xRozmiar) || (xx < 1));
 
    do
    {
        cout << "Wprowadz punkt startowy y wieksze od 1-pionowo:";
        cin >> yy;
    } while ((yy > yRozmiar) || (yy < 1));
 

    cout << "Wymiary tablicy:" << xRozmiar << "X" << yRozmiar << endl;
    cout << "Punkty startowe: X:" << xx << "/Y:" << yy << endl;
 
   
    xx--;
    yy--;
 
    cout << "---------------------------------------------------" << endl << endl;
 
    board = new int *[xRozmiar];
    int **temp = board;
 
    for (int a = 0; a < xRozmiar; a++)
    {
        *temp = new int[yRozmiar];
        (temp)++;
    }
 
    
    InicjacjaTablicy(board, xRozmiar, yRozmiar);
    WyswietlTablice(board, xRozmiar, yRozmiar);
 

    cout << endl << "---------------------------------------------------" << endl;
    cout << "Uruchamianie Konik Szachowy..." << endl;
 
    if (KonikSzachowy(board, xx, yy, xRozmiar, yRozmiar, 1))
    {
        cout << "Rozwiazanie znaleziono: " << endl << endl;
        WyswietlTablice(board, xRozmiar, yRozmiar);
    }
    else
    {
        cout << "Nie znaleziono rozwiazania." << endl << endl;
        WyswietlTablice(board,xRozmiar,yRozmiar);
    }
 
    // Free up memory allocated for board.
    for(int i = 0; i < xRozmiar; i++)
    {
        delete [] (*board);
        (board)++;
    }
 
    cout << "Nacisnij klawisz aby kontynuowac...";
    cin.ignore(1000,'\n');
    cin.get();
 
    return 0;
}
 
// Funkcja inicjująca tablice 

void InicjacjaTablicy(int **board, int xRozmiar, int yRozmiar)
{
    int x, y;
 
    for (x = 0; x < xRozmiar; x++)
    {
        for (y = 0; y < yRozmiar; y++)
        {
            board[x][y] = 0;
        }
    }
}
 
// Wystwietl tablice
void WyswietlTablice(int **board, int xRozmiar, int yRozmiar)
{
    int x, y;
 
    for (x = 0; x < xRozmiar; x++)
    {
        for (y = 0; y < yRozmiar; y++)
        {
            cout << setw(3) << board[x][y];
        }
        cout << endl;
    }
}
 
 bool MoveIsValid(int **board, int xx, int yy, int xRozmiar, int yRozmiar)
{
    if ((xx < 0) || (xx >= xRozmiar))
    {
        return false;
    }
 
    if ((yy < 0) || (yy >= yRozmiar))
    {
        return false;
    }
 
    if (board[xx][yy] != 0)
    {
        return false;
    }
 
    return true;
}
 
 
// Szkoczek Szachowy algorytm.
bool KonikSzachowy(int **board, int xx, int yy, int xRozmiar, int yRozmiar, int moveNum)
{
    if (!MoveIsValid(board, xx, yy, xRozmiar, yRozmiar))
    {
        return false;
    }
 
    board[xx][yy] = moveNum;
 
    if ((xRozmiar * yRozmiar) == moveNum)
    {
        return true;
    }
 
    cout << "KS: "<< yy << ", " << xx << ", " << moveNum << endl;
 
 
    if (!KonikSzachowy(board, (xx - 1), (yy - 2), xRozmiar, yRozmiar, (moveNum + 1)))
        if (!KonikSzachowy(board, (xx - 2), (yy - 1), xRozmiar, yRozmiar, (moveNum + 1)))
            if (!KonikSzachowy(board, (xx - 2), (yy + 1), xRozmiar, yRozmiar, (moveNum + 1)))
                if (!KonikSzachowy(board, (xx - 1), (yy + 2), xRozmiar, yRozmiar, (moveNum + 1)))
                    if (!KonikSzachowy(board, (xx + 1), (yy + 2), xRozmiar, yRozmiar, (moveNum + 1)))
                        if (!KonikSzachowy(board, (xx + 2), (yy + 1), xRozmiar, yRozmiar, (moveNum + 1)))
                            if (!KonikSzachowy(board, (xx + 2), (yy - 1), xRozmiar, yRozmiar, (moveNum + 1)))
                                if (!KonikSzachowy(board, (xx + 1), (yy - 2), xRozmiar, yRozmiar, (moveNum + 1)))
                                return false;
                                }
                                

SCREAN Z PROBLEMEM: http://img713.imageshack.us/img713/5862/obraztd.png

Opis problemu:
Problem polega na tym, że kolejność ruchow jest wykonywana poprawnie do 20 potem cos mi sie sypie i znowu wywala 18,19 itd..problem pojawia sie tez na innych wymirach tablicy, scieram sie nad tym od poand 3 godzin i nie mam pojecia jak to rozwiazac. Dla zobrazowania problemu screean powyzej. Prosze o pomoc...bo nie potrafie sobie z tym poradzic..

0

coś jest źle z tymi if-ami! Gdzie jest return true, z rekurencji? Na dodatek nie cofasz ruchu jeśli okazał się nietrafiony (prowadzący donikąd).

Zamiast męczyć się z taką ilością if-ów, może lepiej zrobić tak (przypuszczam, że to chciałeś osiągnąć):

bool KonikSzachowy(int **board, int xx, int yy, int xRozmiar, int yRozmiar, int moveNum)
{
    static const int IleMozliwychRuchow = 8;
    static struct Ruch {
         int dx,dy;
    } MozliweRuchy[IleMozliwychRuchow] = {
         {-2,-1}, {-2,1}, {2,-1}, {2,1},
         {-1,2}, {-1,-2}, {1,2}, {1,-2}
    };

    if (xx<0 || xx>=xRozmiar || yy<0 || yy>=yRozmiar) {
         return false;
    }
    if (board[xx][yy]!=0) {
         return false;
    }
    board[xx][yy] = ++moveNum; // wykonaj ruch
    if ((xRozmiar * yRozmiar) >= moveNum) {
        return true;
    }

    for(int i=0; i<IleMozliwychRuchow; ++i) {
        if (KonikSzachowy(board, xx+MozliweRuchy[i].dx, yy+MozliweRuchy[i].dy, xRozmiar, yRozmiar, moveNum)) {
            return true;
        }
    }
    board[xx][yy] = 0; // cofanie nieudanego ruchu
    return false;
}

Wątpię by było to wystarczająco sprawne rozwiązanie.

PS. Jeszcze jedno. Aż się prosi by opakować zmienne: board, xRozmiar, yRozmiar w jedną wspólną strukturę opisujące planszę. W końcu podczas rekurencji te wartości się nie zmieniają.

1 użytkowników online, w tym zalogowanych: 0, gości: 1