Problem mit " 8 Damen Problem "

[saabzero]

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

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

}

[Wutz]

conflictFeld liefert immer

return 1;

[saabzero]

Oh das ist noch falsch drinnen.

Soll natürlich " return status " heißen.

Hatte den 1er nur zur Fehlersuche mal drinnen.
Habs jetzt editiert.

Das Programm bleibt immer bei " kein Konflikt " in einer Endlos Schleife hängen und ich weiß nicht recht warum.

[Wutz]

Am Ende der ersten while Schleife fehlt noch

++spalte_;

o.ä.

[DirkB]

Du vergleichst auch immer mit <= groesse_
Wenn groesse_ = 8 ist hast du aber 9 Elemente.
Wenn groesse_ = 50 greifst du irgendwann auf z.B. schachbrett_[0][50]; zu. Dieses Element existiert aber nicht.

[Wutz]

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

sieht auch irgendwie ungesund aus.
Das wird auch prinzipiellso nichts. Du musst spalten/zeilen-weise zurücksetzen und nicht feldweise.
Es gibt genau 92 Lösungen für ein Standard-8x8 Schachbrett.