8 Damen Problem läuft nicht

[durst99]

Hallo

Habe ein Problem mit meinem Programm, welches das " 8 Damen Problem " lösen soll.

Der Algorithmus ist relativ einfach mit Backtracking gemacht, leider funktioniert das Programm nicht wirklich.

Wäre echt super wenn mal jemand drüber schauen könnte.

Hier ist der Code :

#include <stdio.h>

#define MAX 50



int schachbrett_[MAX][MAX];    //globale Variablen

int zeile_, spalte_,groesse_;



//INITIALISIERUNG

void initProgram ()

{

int i,j;	//Laufvariablen Arrayinitialisierung


	for(i=0;i>=MAX;i++)		//Initialisierung Array

	{

		for(j=0;j>=MAX;j++)

		{

			schachbrett_[i][j]=0;

		}

	}


	//restliche Initialisierung


	zeile_=0;

	spalte_=0;

	groesse_=0;

}




//EINGABEFUNKTION GROESSE SCHACHBRETT

int eingabeGroesse ()

{

	int eingabe = 1;

	int groesse;


	printf("\n\nErklaerung: Das Programm erstellt ein Schachbrett mit der von Ihnen eingegebenen Groesse (max. 50) und probiert in jede Spalte eine Dame zu setzen, mit der Bedingung das sich die Damen nicht schlagen koennen\n\n\n\n");



	while(eingabe) 					

  		{

			printf("Geben sie die Groesse des Schachbrettes an (zwischen 1 und 50):");

  			scanf("%i", &groesse);


  				if((groesse>MAX)|(groesse<1))		

   					{

   					printf("Falsche Eingabe, erneut eingeben\n\n");

    				eingabe=1;

   					}


				else

   					{

   					eingabe=0;

   					}


  		}


	return groesse;

}



//FUNKTION ZUM SETZEN EINES WERTES IM ARRAY

void setzeDame(int zeile, int spalte)

{

	schachbrett_[zeile][spalte]=1;	

	ausgabeStdio(groesse_);

	printf("\n\n\n");

	getchar();

}



//FUNKTION ZUM BESTIMMEN DER POSITION EINER DAME IN EINER SPALTE

int posiDame(int spalte)

{

	int i;	//Laufvariable

	int posi;


		for(i=0; i<=groesse_; i++)

		{

			if(schachbrett_[i][spalte]==1)

			{

			posi=i;

			}

			else

			{

			printf("keine Position gefunden");

			}

		}

	return posi;


}


//FUNKTION ZUM LÖSCHEN EINER DAME


void removeDame (int spalte, int zeile)

{

	schachbrett_[zeile][spalte]=0;

}


//FUNKTION ZUM ERMITTELN EINES KONFLIKTES BEIM SETZEN EINER DAME


int conflictFeld (int spalte, int zeile)

{

	int i; //Laufvariable

	int status; //Statusvar. wenn 1 konflikt wenn 0 Dame kann gesetzt werden

	int zahl = 0;


	for (i=0; i<=groesse_; i++)

	{


		if((schachbrett_[zeile][i]==1)&&(i!=spalte)) //Zeile	

		{

		status=1;

		}

		else if(((spalte-i)>=0)&&((zeile-i)>=0)&&(schachbrett_[zeile-i][spalte-i]==1))//Diagonale links hinauf

		{

		status=1;

		}

		else if(((spalte-i)>=0)&&((zeile+i)<=groesse_)&&(schachbrett_[zeile+i][spalte-i]==1))//Diagonale links hinunter

		{

		status=1;

		}

		else if(((spalte+i)<=groesse_)&&((zeile-i)>=0)&&(schachbrett_[zeile-i][spalte+i]==1))//Diagonale rechts hinauf

		{

		status=1;

		}

		else if(((spalte+i)<=groesse_)&&((zeile+i)<=groesse_)&&(schachbrett_[zeile+i][spalte+i]==1))//Diagonale rechts hinunter

		{

		status=1;

		}

		else

		{

		zahl=zahl+1;

		status=0;

		printf("kein konflikt %i\n", zahl);



		}


	}

	return 1;

}




//FUNKTION ZUR AUSGABE IM STDIO

int ausgabeStdio(int seitenlaenge)

{

	int i,j;		//Laufvariablen


	for (i=0;i<=(seitenlaenge-1);i++)		//Durchlauf Spalte

	{

		printf("\n");						//Neue Zeile


		for (j=0;j<=(seitenlaenge-1);j++)	//Durchlauf Zeile

		{

		printf("|%4i|",schachbrett_[i][j]);

		}

	}


}





//HAUPTPROGRAMM

int main()


{



	initProgram();							//Initialisierung

	groesse_=eingabeGroesse();				//Eingabe Groesse


	zeile_=0;								//Startposition

	spalte_=0;




	//Algorithmus


	while ((spalte_>=0)&&(spalte_<=groesse_))

	{


		while ((zeile_<groesse_) && conflictFeld(zeile_,spalte_))

		{

			zeile_=zeile_+1;



			if(zeile_<groesse_)

			{

			setzeDame(zeile_,spalte_);

			spalte_=spalte_+1;

			zeile_=0;

			}


			else

			{

			spalte_=spalte_-1;

			zeile_=posiDame(spalte_);

			removeDame(zeile_,spalte_);

			zeile_=zeile_+1;

			}

		}

	}


	if(spalte_>=groesse_)

	{

	printf("Es gibt eine Loesung\n\n\n");

	ausgabeStdio(groesse_);

	}

	else

	{

	printf("Es gibt keine Loesung");

	}



}

[Klotzkopp]

Du erwartest hoffentlich nicht, dass sich jemand hinsetzt und in über 200 Zeilen Code nach einem Fehler sucht, über den absolut nichts bekannt ist außer dieser tollen Fehlerbeschreibung:

leider funktioniert das Programm nicht wirklich.

Benutz den Debugger, prüf die Variablenwerte, grenz den Fehler ein, beschreib das erwartete und das beobachtete Verhalten.

[durst99]

Sry für die ungenau Beschreibung.

Hatte in der Früh nicht viel Zeit den Code zu posten.

Es geht darum, dass mir das Programm hier :

else

		{

		status=0;

		printf("kein konflikt %i\n", zahl);



		}

In einer Endlosschleife hängen bleibt.

Es geht bei der Funktion "conflictFeld" um die Überprüfung, ob sich in den Diagonalen, bzw. in der selben Zeile schon eine Dame befindet.

Ist dort eine soll "status" den Wert 1 liefern , ist dort keine soll es 0 liefern.

So wäre zumindest meine Überlegung gewesen.

[Klotzkopp]

Deine conflictFeld-Funktion gibt sowieso immer 1 zurück, egal welchen Wert status hat.

[durst99]

soll "return status " heißen.

Hatte den 1er noch von der Fehlersuch drinnen.

[Klotzkopp]

Jetzt gibt conflictFeld immer 0 zurück, damit wird die Bedingung deiner inneren Schleife nie wahr, sie wird also nie ausgeführt.

Ansonsten passiert in der äußeren Schleife nichts -> Endlosschleife.

[durst99]

Aber warum ?

Meine Conflict Bedingungen müssten doch eigendlich passen.

[Klotzkopp]

while ((zeile_<groesse_) && conflictFeld(zeile_,spalte_))

Wenn conflictFeld 0 zurückgibt, ist diese Schleifenbedingung false, und damit wird diese Schleife nicht betreten. Und da nur in dieser Schleife eine Dame gesetzt wird, wird keine Dame gesetzt, wenn conflictFeld 0 zurückgibt. Aber wenn keine Dame gesetzt wird, wird conflictFeld weiterhin 0 zurückgeben.

Wie soll denn deiner Meinung nach jemals die erste Dame gesetzt werden?

[durst99]

Gut das sehe ich ein ja.

Aber was ist dann in der for schleife oben falsch, dass immer status 0 returned wird ?

for (i=0; i<=groesse_; i++)

	{


		if((schachbrett_[zeile][i]==1)&&(i!=spalte)) //Zeile	

		{

		status=1;

		}

		else if(((spalte-i)>=0)&&((zeile-i)>=0)&&(schachbrett_[zeile-i][spalte-i]==1))//Diagonale links hinauf

		{

		status=1;

		}

		else if(((spalte-i)>=0)&&((zeile+i)<=groesse_)&&(schachbrett_[zeile+i][spalte-i]==1))//Diagonale links hinunter

		{

		status=1;

		}

		else if(((spalte+i)<=groesse_)&&((zeile-i)>=0)&&(schachbrett_[zeile-i][spalte+i]==1))//Diagonale rechts hinauf

		{

		status=1;

		}

		else if(((spalte+i)<=groesse_)&&((zeile+i)<=groesse_)&&(schachbrett_[zeile+i][spalte+i]==1))//Diagonale rechts hinunter

		{

		status=1;

		}

		else

		{

		zahl=zahl+1;

		status=0;

		printf("kein konflikt %i\n", zahl);


		}


	}

	return status;

[Klotzkopp]

Aber was ist dann in der for schleife oben falsch, dass immer status 0 returned wird ?

Du suchst den Fehler an der falschen Stelle.

Solange keine einzige Dame auf dem Schachbrett steht, ist es völlig richtig, dass die Funktion 0 zurückgibt.

Falsch ist, wie du in der main-Funktion auf den Rückgabewert 0 reagierst.

Bearbeitet 1. April 2011 von Klotzkopp

[durst99]

Funktioniert leider immer noch nicht.

Verstehe nicht wirklich was in der main falsch ist.

[Klotzkopp]

Funktioniert leider immer noch nicht.

Wenn du nichts geändert hast, ist das nicht weiter verwunderlich.

Wenn doch, solltest du schon sagen, was

Verstehe nicht wirklich was in der main falsch ist.

Geh es doch einfach mal von Hand durch:

1. schachbrett_ enthält überall 0, zeile_ und spalte_ sind auch 0
   
2. while ((spalte_>=0)&&(spalte_<=groesse_)) ---> true, äußere Schleife betreten
   
3. while ((zeile_<groesse_) && conflictFeld(zeile_,spalte_)) ---> false (weil conflictFeld auf einem leeren Schachbrett 0 zurückgibt), innere Schleife nicht betreten
   
4. Ende der äußeren Schleife, zurück zu 2
   

Mehr passiert nicht.