rohamis
Bekanntes Mitglied
Hallo zusammen,
ich muss in C einen Algorithmus schreiben, der ein beliebiges Sudoku mit der Backtracking Methode (rekursiv) löst.
Allerdings habe ich schon 3 Funktionen vorgelegt bekommen, die ich auch benutzen soll(!!!).
Ich weiss genau was Backtracking ist, ich weiss auch wie das in Sudoku funktioniert, aber ich komme nicht so ganz dahinter, wie ich das in C realisieren soll.
Mein Problem besteht nämlich darin, woher das Programm wiessen kann, zu welchen Feld es zurück gehen soll. Ich habe in einem Array die Felder markiert, die auch bearbeitet wurden sind, aber ich weiss nicht wie ich es dem Kompiler "sagen" soll, dass er da nochmals überprüfen soll, welche Zahl als nächstes Möglich ist.
Die Funktionen die ich habe sind: (b = Sudoku Brett)
1) suche_freie_stelle(i,j,b)
2) ist_belegt (ob Feld frei ist oder nicht)
3) ist_erlaubt (on in das leere Feld die Zahl rein kommen kann oder nicht).
Damit soll ich halt den Algorithmus schreiben.
Hier das, was ich bis jetzt gemacht habe. Ihr werdet auch schnell erkennen, dass ich es bis dahin nur soweit geschaft habe, dass er das Soduko soweit löst, bis der ein Feld sieht wo es keine Zahl rein passt. Dann ist schluss
Das soll auch nicht heissen, dass es bisher richtig ist was ich habe. Wenn jemand mir sagen würde "mache es anders" dann habe ich auch kein Problem mit. Wichtig ist, ich muss diese 3 Funktionen benutzen in dem Algo.
ich muss in C einen Algorithmus schreiben, der ein beliebiges Sudoku mit der Backtracking Methode (rekursiv) löst.
Allerdings habe ich schon 3 Funktionen vorgelegt bekommen, die ich auch benutzen soll(!!!).
Ich weiss genau was Backtracking ist, ich weiss auch wie das in Sudoku funktioniert, aber ich komme nicht so ganz dahinter, wie ich das in C realisieren soll.
Mein Problem besteht nämlich darin, woher das Programm wiessen kann, zu welchen Feld es zurück gehen soll. Ich habe in einem Array die Felder markiert, die auch bearbeitet wurden sind, aber ich weiss nicht wie ich es dem Kompiler "sagen" soll, dass er da nochmals überprüfen soll, welche Zahl als nächstes Möglich ist.
Die Funktionen die ich habe sind: (b = Sudoku Brett)
1) suche_freie_stelle(i,j,b)
2) ist_belegt (ob Feld frei ist oder nicht)
3) ist_erlaubt (on in das leere Feld die Zahl rein kommen kann oder nicht).
Damit soll ich halt den Algorithmus schreiben.
Hier das, was ich bis jetzt gemacht habe. Ihr werdet auch schnell erkennen, dass ich es bis dahin nur soweit geschaft habe, dass er das Soduko soweit löst, bis der ein Feld sieht wo es keine Zahl rein passt. Dann ist schluss
Das soll auch nicht heissen, dass es bisher richtig ist was ich habe. Wenn jemand mir sagen würde "mache es anders" dann habe ich auch kein Problem mit. Wichtig ist, ich muss diese 3 Funktionen benutzen in dem Algo.
Code:
int loese_sudoku(int i, int j, int b[BS][BS] )
{
int zahl_erlaubt = 0;
char markiert[BS][BS];
int m,n;
for(m=0;m<BS;m++)
for(n=0;n<BS;n++)
markiert[m][n] = 'f';
suche_naechste_freie_stelle(&i,&j,b); /* mit zeigern, damit die änderungen auch hier sichtbar sind */
if(i>=BS)
{
printf("Sudoku ist fertig!\n");
return 1;
}
else
{
int z = 1;
while(z<=10)
{
if(z==10)
{
if(markiert[i][j-1] == 'f'); /* HIER WEISS ICH NICHT WAS ICH MACHEN SOLL */
/* WIE ICH ZURÜCK GEHEN SOLL BZW. WIE ER WISSEN WOLL */
/* ZU WELCHEM FELD ER WIEDER ZURÜCK GEHEN MUSS!!! */
}
else
{
if(ist_erlaubt(z,i,j,b))
{
b[i][j] = z;
zahl_erlaubt = 1;
markiert[i][j] = 'm';
loese_sudoku(i,j,b);
}
}
z++;
}
}
}
Zuletzt bearbeitet: