3. Problem bei Rekursion zur Sudokulösung

Problem bei Rekursion zur Sudokulösung

  • ?

    Hallo!
    Ich arbeite zurzeit an einem Programm, welches mir ein fertig gelöstes in sich stimmiges Sudoku erstellen soll. Ich habe mir gedacht, dies rekursiv zu lösen, aber so wirklich endgültig verstanden, scheine ich die Rekursion noch nicht zu haben. Mein Programm ist zwar lauffähig, aber es spuckt mir nur unfertige Sudokus aus.

    Hier der Quelltext der rekursiven Funktion:

    int sudofill(int zahl,int x,int y)
{
if(sudotest(zahl,x,y))sudo[x][y]=zahl;
else {return 0;}
bool keineNullen=true;
	for(int i=0;i<9;i++)
	for(int j=0;j<9;j++)
	if(sudo[i][j]==0)keineNullen=false;
if(keineNullen)return 1;
x=(rand()%9)+1;
y=(rand()%9)+1;
for(int i=1;i<10;i++)
	{
	int erg=sudofill(i,x,y);
	if(erg==1)return 1;
	//if(i==9)i=1;
	}

}

    Ich hoffe jemand kann mir helfen, mein Problem zu erkennen.
    sudotest(zahl,x,y) gibt wahr zurück, wenn die zahl an der angegebenden Koordinate eintragbar ist.

    lg Tino Raspari

    0
  • X

    ok langsam:

    if(sudo[i][j]==0)keineNullen=false;

    hast du erst alle felder wirklich mit mit der Zahl 0 initialisiert?

    x=(rand()%9)+1;
y=(rand()%9)+1;

    springst du hier in ein zufälliges Feld? und wenn, warum +1? ich dachte dein array fängt mit index 0 an?

    Wann rufst du sudofill überhaupt auf? zeig mal den gesamten code...scheint irgendwie ziemlich wirr zu sein.

    0
  • ?

    Moin^^
    Also das mit dem +1 bei der rand funktion hab ich schon wieder behoben...
    war nurn flüchtigkeitsfehler, sieht man ja an der Ausgabe^^
    hier also der gesammte Quelltext:

    #include<iostream>
#include<time.h>
#include<fstream>
using namespace std;
int sudo[9][9];

bool sudotest(int zahl,int x,int  y)
{
bool res=true;	// Ergebnissspeicher
int i,j;	// Zählvariablen

// Testen der Zeile / Spalte
for (i=0;i<9;i++)
    {
    if (sudo[i][y]==zahl) res = false;
    if (sudo[x][i]==zahl) res = false;
    }

// Testen des Blocks
int h1=x/3*3;
int h2=y/3*3;
for (i=0;i<3;i++)
    for (j=0;j<3;j++)
	if (sudo[h1+i][h2+j]==zahl) res = false;

return res;
}

void sudoterm()
{
for (int i=0;i<9;i++)
    for(int j=0;j<9;j++)
	sudo[i][j] = 0;
}

int sudofill(int zahl,int x,int y)
{
if(sudotest(zahl,x,y))sudo[x][y]=zahl;
else {return 0;}
bool keineNullen=true;
	for(int i=0;i<9;i++)
	for(int j=0;j<9;j++)
	if(sudo[i][j]==0)keineNullen=false;
if(keineNullen)return 1;
randxy:
x=(rand()%9);
y=(rand()%9);
if(sudo[x][y]!=0)goto randxy;
for(int i=1;i<10;i++)
	{
	int erg=sudofill(i,x,y);
	if(erg==1)return 1;
	//if(erg==3){sudo[x][y]=0;return 0;}
	}
return 0;
}

void sudocall()
{
for (int i=0;i<9;i++)
    {
    for (int j=0;j<9;j++) cout<<sudo[j][i]<<" ";
    cout<<endl;	
    }
}

int main()
{

srand( (unsigned)time( NULL ) );
ofstream OF;
OF.open("Sudokus.txt");
for(int i=0;i<50;i++)
{sudoterm();
hier2:
// srand( (unsigned)time( NULL ) );
int x=((rand())%9),y=((rand())%9);
int zahl=(rand())%9+1;

int a;
for(int zahl=1;zahl<=9;zahl++)
{a=sudofill(zahl,x,y);if(a)break;}
if(a)
{				
sudocall();
for(int j=0;j<9;j++)
	{
		for(int k=0;k<9;k++)
		{OF<<sudo[j][k]<<" ";}
	OF<<endl;
	}
OF<<endl;OF<<endl<<"-------------------------------------"<<i<<"---------------"<<endl;
cout<<(unsigned)time( NULL )<<endl;
}
else goto hier2;
}
OF.close();
return 0;
}

    Achso wegen der Sache mit den keineNullen. Das mach erst Sinn wenn man sich denkt das die Rekursion schon tiefer ist. damit testet er quasi ob er schon fertig ist und wenn ja returned er 1. das wird dann durchgegeben bis zum Schluss..

    lg Tino

    0
  • X

    so also erstens:

    wie dein Quellcode strukturiert ist, ist echt schlimm. Gewöhn dir ein bisschen einen schöneren Stil an.

    Weiter: Das hier ist deine Schleife

    for(int i=0;i<50;i++)
{sudoterm();
hier2:
// srand( (unsigned)time( NULL ) );
int x=((rand())%9),y=((rand())%9);
int zahl=(rand())%9+1;

int a;
for(int zahl=1;zahl<=9;zahl++)
{a=sudofill(zahl,x,y);if(a)break;}
if(a)
{               
sudocall();
for(int j=0;j<9;j++)
    {
        for(int k=0;k<9;k++)
        {OF<<sudo[j][k]<<" ";}
    OF<<endl;
    }
OF<<endl;OF<<endl<<"-------------------------------------"<<i<<"---------------"<<endl;
cout<<(unsigned)time( NULL )<<endl;
}
else goto hier2;
}

    gleich zu beginn setzt du bei jedem Schleifendurchlauf alle Felder auf 0, und zwar mit sudocall....ich hab's noch nicht genau durchgeschaut (es ist echt mühsam bei der struktur), aber ich glaub das ist blödsinn

    0
  • ?
     

    for(int zahl=1;zahl<=9;zahl++)
{a=sudofill(zahl,x,y);if(a)break;}

    an dieser Stelle wird Sudofill aufgerufen, welche sich rekursiv selbst aufruft.
    in dieser rekkursion überprüft er nun ob die angegebene zahl an angegebener stelle im sudoku so stehen könnte ohne gegen irgendwelche regeln zu verstoßen. wenn ja eintragen und neuen zufällig koordinate ran und wieder die zahlen von 1 bis 9 durchprobieren, wenns pass nächste und so weiter...

    lg Tino

    0
  • X

    wow ich versteh zwar deine erklärung aber dein code ist nur strange.
    Hast du ICQ oder was ähnliches um dir einige dinge zu erklären?

    Das wäre viel zu aufwendig hier.

    0
Anmelden zum Antworten