✔ 8-Damen-Problem

[Dorschty]

Das ich da mit einer rekursiven Funktion arbeiten muss hab ich jetzt bestimmt schon knapp 1000 mal beim googlen erfahren Das Problem ist nur, das ich keine Ahnung hab, wie ich das anstellen soll, da ich wie gesagt noch ein ziehmlicher Anfänger bin!

 

[zerix]

Schau dir das mal an. Ich denke das ist ein guter Anfang.

http://www.inf.hs-zigr.de/~wagenkn/TI/Komplexitaet/ReferateSS00/roitsch.pdf

MFG

zEriX

 

[mike4004]

Hallo

das Problem ist auch recht gut auf http://www.pronix.de/pronix-838.html beschrieben. Einfach mal hinschauen.

mfg mike4004

 

[Dorschty]

Hey,

nochmal kurz zu dem Problem...
also ich hab das Programm jetzt soweit meiner Meinung nach fertig.... allerdings ist jetzt noch irgendwie das Problem, das wenn er die zweite Dame gesetzt hat in der Zeile 2 Spalte c

1 | X |__|__|__|__|__|__|
2 |__|__|__|__|__|__|__|
3 |__|__|__|__|__|__|__|
4 |__|__|__|__|__|__|__|
5 |__|__|__|__|__|__|__|
6 |__|__|__|__|__|__|__|
7 |__|__|__|__|__|__|__|
8 |__|__|__|__|__|__|__|
a b c d e f g

und in das Programm in der nächsten Zeile überprüft erkennt er die Dame, die ich in der Zelle gesetzt hab nicht mehr!
Hier ist der Quelltext dazu:

#include "stdafx.h"
#include <stdio.h> 
#include <conio.h> 

#define DAME 'D'

int spalte=0,zeile=0,i=0;
char schachbrett[8][8];

int check()
{
        
        int my_zeile=zeile, my_spalte=spalte, my_spaltel=spalte, my_spalter=spalte;
        int kollision=0;

        for(i=0;i<zeile;i++)
        {
            my_zeile--;
            if(schachbrett[my_zeile][my_spalte]==DAME)
            {
                kollision++;
                return 1;
            }
               
            if(my_spaltel>=0&&my_spaltel<=7)
            {
                my_spaltel--;
                if(my_spaltel>=0){
                    if(schachbrett[my_zeile][my_spaltel]==DAME)
                    {
                        kollision++;
                        return 1;
                    }
                }
            }

            if(my_spalter<=7&&my_spalter>=0){
                my_spalter++;
                if(my_spalter<=7){
                    if(schachbrett[my_zeile][my_spalter]==DAME)
                    {
                        kollision++;
                        return 1;
                    }
                }
            }
        }
        
        if(kollision==0)
                return 0;
}


int _tmain(int argc, _TCHAR* argv[])
{
               
    int j=0,k=0, gesetzt=0; 

    for(j=0;j<8;j++)
        for(i=0;i<8;i++)
            schachbrett[j][i]=' ';
            

    
    while(gesetzt<8)
    {
        schachbrett[spalte][zeile]=DAME;
        int result=check();
        if(result==0){
            gesetzt++;
            zeile++;
            spalte=0;
        }
        else if(result==1)
        {
            schachbrett[spalte][zeile]=' ';
            if(spalte<=7)
                spalte++;
            else if(spalte>7){
                zeile--;
                spalte=0;
            }
            
        }

    }        
    
    printf("+- - - - - - - -+\n|");
    for(j=0;j<8;j++)
    {
        for(i=0;i<8;i++)
            printf("%c|",schachbrett[j][i]);
        if(j==7)
            printf("\n+- - - - - - - -+\n");
        else
            printf("\n+-|-|-|-|-|-|-|-+\n|");
    }
    _getch();

    return 0;
}

Sieht jemand meinen Fehler? Ich kann ihn einfach nicht finden!
Gruß
Dorschty

 

[Dorschty]

Hab den Fehler jetzt doch noch selbst gefunden.
Wen es interessiert, hier ist der Quellcode für die visuelle Ausgabe von einer Lösung!

#include "stdafx.h"
#include <stdio.h> 
#include <conio.h> 

#define DAME 'D'

int spalte=0,zeile=0,i=0;
char schachbrett[8][8];

int check(int my_zeile=zeile, int my_spalte=spalte, int my_spaltel=spalte, int my_spalter=spalte)
{
        for(i=0;i<zeile;i++)
        {
            my_zeile--;
            if(schachbrett[my_zeile][my_spalte]==DAME)
            {
                return 1;
            }
               
            if(my_spaltel>=0&&my_spaltel<=7)
            {
                my_spaltel--;
                if(my_spaltel>=0){
                    if(schachbrett[my_zeile][my_spaltel]==DAME)
                    {
                        return 1;
                    }   
                }
            }

            if(my_spalter<=7&&my_spalter>=0){
                my_spalter++;
                if(my_spalter<=7){
                    if(schachbrett[my_zeile][my_spalter]==DAME)
                    {
                        return 1;
                    }       
                }
            }
        }
        return 0;
}


int _tmain(int argc, _TCHAR* argv[])
{
               
    int j=0,k=0, gesetzt=0; 

    for(j=0;j<8;j++)
        for(i=0;i<8;i++)
            schachbrett[j][i]=' ';
            

    while(gesetzt<=8)
    {
        schachbrett[zeile][spalte]=DAME;
        int result=check();
        if(result==0){
            gesetzt++;
            zeile++;
            spalte=0;
    
        }
        else if(result==1)
        {
            schachbrett[zeile][spalte]=' ';
            if(spalte<=7)
                spalte++;
            if(spalte>7){
                zeile--;
                spalte=0;
                while(schachbrett[zeile][spalte]!=DAME)
                    spalte++;
                schachbrett[zeile][spalte]=' ';
                gesetzt--;
                if(spalte==7){
                    zeile--;
                    spalte=0;
                    while(schachbrett[zeile][spalte]!=DAME)
                        spalte++;
                    schachbrett[zeile][spalte]=' ';
                    spalte++;
                    gesetzt--;
                }
            
                else
                    spalte++;                   
            }
            
        }
    }
       
    printf("+- - - - - - - -+\n|");
    for(j=0;j<8;j++)
    {
        for(i=0;i<8;i++)
            printf("%c|",schachbrett[j][i]);
        if(j==7)
            printf("\n+- - - - - - - -+\n");
        else
            printf("\n+-|-|-|-|-|-|-|-+\n|");
    }

    _getch();

    return 0;
}

Gruß
Dorschty