Problem mit " 8 Damen Problem "
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");
}
}
|
