3. springerproblem

springerproblem

  • S

    hallo, muss zur zeit das springerproblem in c++ implementieren.
    leider komm ich mit der rekursion noch nicht ganz klar. 😕
    wär nett wenn sich jemand mal den code ansehen könnte und mir vielleicht eine denkhilfe geben könnte.

    danke im voraus

    gruß sigint

    #include <iostream>
    #include <iomanip>

    using namespace std;

    void springer(int, int, int);

    bool spielbrett [5][5];
    int weg [5][5];
    int zug = 25;
    int x;
    int y;

    void main()
    {

    for(int i = 0; i<5; i++)
    {
    for(int j = 0; j<5;j++)
    {
    spielbrett[i][j] = true;
    }
    }

    for(int i = 0; i<5;i++)
    {
    for(int j = 0; j<5;j++)
    {
    cout << spielbrett[i][j] << " ";
    }
    cout << endl;
    }

    cout << "\t THE KNIGHT'S TOUR \n\n";
    do
    { cout << "Please choose the X startpoint for the knight: \t";
    cin >> x;
    } while(x<0||x>4);

    do
    { cout << "Please choose the Y startpoint for the knight: \t";
    cin >> y;
    } while (y<0||y>4);

    cout << "\nThe way of the knight will be shown\n";

    springer(zug,x,y);
    char u;
    cin >> u;
    }

    void springer(int zug, int x, int y)
    {

    for(int i = 0; i<5;i++)
    {
    for(int j = 0; j<5;j++)
    {
    cout << spielbrett[i][j] << " ";
    }
    cout << endl;
    }

    cout << endl;

    if(zug>0)
    {
    if((x-2)>=0 && (y-1)>=0 && spielbrett[x-2][y-1])
    { spielbrett[x][y] = false;
    springer(zug-1,x-2,y-1);}

    else if ((x+2)<=4 && (y-1)>=0 && spielbrett[x+2][y-1])
    { spielbrett[x][y] = false;
    springer(zug-1,x+2,y-1);}

    else if ((x+1)<=4 && (y-2)>=0 && spielbrett[x+1][y-2])
    { spielbrett[x][y] = false;
    springer(zug-1,x+1,y-2);}

    else if ((x-1)>=0 && (y-2)>=0 && spielbrett[x-1][y-2])
    { spielbrett[x][y] = false;
    springer(zug-1,x-1,y-2);}

    else if ((x-2)>=0 && (y+1)<=4 && spielbrett[x-2][y+1])
    { spielbrett[x][y] = false;
    springer(zug-1,x-2,y+1);}

    else if ((x+2)<=4 && (y+1)<=4 && spielbrett[x+2][y+1])
    { spielbrett[x][y] = false;
    springer(zug-1,x+2,y+1);}

    else if ((x-1)>=0 && (y+2)<=4 && spielbrett[x-1][y+2])
    { spielbrett[x][y] = false;
    springer(zug-1,x-1,y+2);}

    else if ((x+1)<=4 && (y+2)<=4 && spielbrett[x+1][y+2])
    { spielbrett[x][y] = false;
    springer(zug-1,x+1,y+2);}
    }
    else
    cout << "Eine Lösung wurde gefunden";

    }

    0
  • C

    Erstens: sfds

    Zweitens: Wo genau liegt dein Problem? Compilerfehler? Falsche Ausgaben? Gar keine Ausgaben?

    Drittens: Dir ist hoffentlich klar, daß du auf einem 5*5 Feld nur 24 Schritte gehen kannst, bis du jedes Feld einmal besetzt hast.

    0
  • S

    ok, danke so siehts besser aus. 🙂

    #include <iostream>
#include <iomanip>

using namespace std;

void springer(int, int, int);

bool spielbrett [5][5];
int weg [5][5];
int zug = 25;
int x;
int y;

void main()
{

	for(int i = 0; i<5; i++)
	{
		for(int j = 0; j<5;j++)
		{
			spielbrett[i][j] = true;
		}
	}

	for(int i = 0; i<5;i++)
	{
		for(int j = 0; j<5;j++)
		{
			cout << spielbrett[i][j] << " ";
		}
		cout << endl;
	}

	cout << "\t THE KNIGHT'S TOUR \n\n";
	do
	{ cout << "Please choose the X startpoint for the knight: \t";
	  cin >> x;
	} while(x<0||x>4);

	do
	{ cout << "Please choose the Y startpoint for the knight: \t";
	  cin >> y;
	} while (y<0||y>4);

	cout << "\nThe way of the knight will be shown\n";

	springer(zug,x,y);
	char u;
	cin >> u;
}

void springer(int zug, int x, int y)
{

	for(int i = 0; i<5;i++)
	{
		for(int j = 0; j<5;j++)
		{
			cout << spielbrett[i][j] << " ";
		}
		cout << endl;
	}

	cout << endl;

	if(zug>0)
	{
	if((x-2)>=0 && (y-1)>=0 && spielbrett[x-2][y-1])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x-2,y-1);}

	else if ((x+2)<=4 && (y-1)>=0 && spielbrett[x+2][y-1])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x+2,y-1);}

	else if ((x+1)<=4 && (y-2)>=0 && spielbrett[x+1][y-2])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x+1,y-2);}

	else if ((x-1)>=0 && (y-2)>=0 && spielbrett[x-1][y-2])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x-1,y-2);}

	else if ((x-2)>=0 && (y+1)<=4 && spielbrett[x-2][y+1])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x-2,y+1);}

	else if ((x+2)<=4 && (y+1)<=4 && spielbrett[x+2][y+1])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x+2,y+1);}

	else if ((x-1)>=0 && (y+2)<=4 && spielbrett[x-1][y+2])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x-1,y+2);}

	else if ((x+1)<=4 && (y+2)<=4 && spielbrett[x+1][y+2])
	{ spielbrett[x][y] = false;	
	  springer(zug-1,x+1,y+2);}
	}
	else
	cout << "Eine Lösung wurde gefunden";

}

    mein problem liegt in der rekursion. er springt bis zu einem gewissen punkt, bei welchem er nicht mehr weiterkommt. über backtracking sollte ich zum vorletzten aufruf zurückkehren und einen alternativen sprung machen. funktioniert aber nich so ganz. bei der ausgabe zeigt er mir, bis zu welchem sprung er geht und dann nicht mehr weiterkommt. logischerweise verläuft er sich dann und bringt mir einen stackoverflow.

    0
  • C

    Eventuell solltest du beim zurückspringen auch wieder die Änderungen umkehren, die du auf dem Vorwärtswegs ausgeführt aus (insbesondere die Feldelemente zurücksetzen auf true). Und außerdem solltest du mal überprüfen, ob du noch im Inneren des Spielfeldes bist.

    0
Anmelden zum Antworten