C/C++ Forum :: Rekursive Funktion mit 2d array als parameter (Sudoku-Backtracking)

sadmarvin Mitglied 12:50:40 01.09.2010 Titel:

Hi,

ich habe gerade angefangen C zu lernen. Aber bei diesem ganzen Zeiger Kram steig ich noch nicht wirklich durch.

ich habe in Python ein Programm zum lösen von Sudokus per Backtracking und versuche nun dies in C zu programmieren.

die rekursive Funktion zum lösen sieht in python so aus:
http://pastebin.com/bS7nhyqR

in C habe ich es so versucht:
http://pastebin.com/7E4dSsHU
(die Funktion allowed habe ich nicht mit gepostet)

aber das funktioniert nicht richtig.
Es wird das leere Sudoku ausgegeben, aber dann scheint das Programm irgendwie in einer Endlosschleife zu stecken.

Wenn ich in der Funktio die Abfrage

Code:
if (solve(feld) != NULL)

Code:
if (solve(feld) != NULL)

Code:
if (solve(feld) != NULL)

in

Code:
if (solve(feld) == NULL)

Code:
if (solve(feld) == NULL)

Code:
if (solve(feld) == NULL)

ändere, läuft das Prog. bis es die erste Zelle findet, für die keine Zahl gültig ist. Also es wird das leere Sudoku ausgegeben, und dann das Sudoku mit den bis zum abbruch gefundenen Zahlen.

Irgendwie scheint die Rekursion nicht so ganz zu funktionieren.
Wie gesagt, bin ich mit Zeigern, Rekursion und so noch sehr unsicher.

Wo liegt denn der Fehler. Muss ich dass Array evtl. anders an die Funktionen übergeben?

Wutz Mitglied 14:50:39 01.09.2010 Titel:

Du läufst u.a. von 1..10, sollte das nicht 1..9 sein?
Am Ende der Funktion fehlt ein return, hier sollte wohl irgendwas für !=NULL stehen? Vielleicht solltest du einfach den return-Typ von void* auf int ändern, ist einfacher für diesen Fall.

sadmarvin Mitglied 15:49:35 01.09.2010 Titel:

ups ja muss natürlich n<10 sein und nicht n<=10

aber mit return-typ int und einem "return 1" am Ende funktioniert es auch nicht.
http://pastebin.com/p9RxVJ6W

wenn ich das "return 1" eine Klammer weiter nach innen packe, geht es bis zur ersten Zeile. also:

Code:
1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Code:
1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Code:
1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Bei noch einer Klammer weiter nach innen, nur die erste Zahl. Das ist ja auch zu erwarten. Aber wenn das return 1 am ende steht startet das Programm und die Funktion "hängt irgendwo fest".

sadmarvin Mitglied 21:33:47 01.09.2010 Titel:

also ich habe jetzt im netz was gefunden was funktioniert, aber dazu hab ich noch mal eine frage:

http://pastebin.com/jQytjzRf

Die Funktion fängt oben links an und arbeitet dann spalte für spalte ab.

wenn ich jetzt in den Zeilen 14 bis 19 n und m vertausche, müsste sie ja auch oben links anfangen, aber dann zeilenweise weitermachen. Genau das funktioniert aber nicht. Dann verhält sie sich genauso wie meine erste. (die geht ja auch zeilenweise vor)

Weiss jemand woran das liegt, das es nicht funktioniert wenn man m und n vertauscht?

EDIT:
hmm, seltsam, ich habe die erste funktion grad nochmal eingegeben und die geht jetzt auf einmal. War vielleicht irgendwo nen tippfehler oder so?!

Aber das mit dem n und m vertauschen verstehe ich nicht.