Problem mit " 8 Damen Problem "

durst99 · 31.03.11, 07:15

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 :

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

}

wmosebach · 01.04.11, 12:09

Da du das Array nicht richtig initialisiert und später nach den Werten der Felder fragst, könnte es gut sein, dass dir das Programm da im Dreieck springt. Änder das doch mal und schau was es dann macht.

Kleine Anmerkung bei der Rückgabe in der Funktion "conflictFeld"

Weitere Anmerkung in der main

Eine Bitte für den Programmierstil: Vermische keine englischen und deutschen Begriffe in Variablen oder Funktionsnamen. Lass es einheitlich

Zitat:

Zitat von durst99

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

        //du schreibst >=, dieser Fall wird nicht eintreten, daher wird das Array nicht initialisiert
        //richtig wäre <=
        //aber wieso 50 Zeilen und Spalten? Willst du nicht eher ein max. 8x8 Feld?
	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);
                                
                                // oder wird normalerweise als || geschrieben
  				if((groesse>MAX)|(groesse<1))		
   					{
   					printf("Falsche Eingabe, erneut eingeben\n\n");
                                //diese zuweisung ist überflüssig
    				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);
		
		
		}
		
	}
        // willst du hier nicht zurückgeben ob es einen konflikt gab?
        // --> return status
        // des weiteren solltest du vll status 1 und 0 tauschen, oder die while-schleife in der main ändern
	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_))
	{
		//du brichst alles ab, wenn es einen Konflikt gibt?
                //überlegt dir noch mal ob du die funktion conflictFeld in der while haben willst
		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");
	}
	

}