Text erkannt:
Programmbeschreibung:
In dieser Hausaufgabe soll ein Sudoku-Löser entwickelt werden. Das Programm liest ein vorgegebenes Sudoku aus einer Datei ein und versucht, es mittels eines einfachen Ausschlußverfahrens zu lösen.
- Hauptprogramm main (main. c/f90)
Das von Ihnen zu entwickelnde Hauptprogramm stellt den Rahmen des Programms dar. Hier werden die Unterprogramme aufgerufen und die grundsätzlichen Lösungsschleifen implementiert:
- Das Programm gibt beim Start eine Begrüfungsmeldung an den Benutzer aus.
- Die Funktion einlesen liest das Sudoku aus der Datei audoku. dat in die 9x9-Matrix spielfeld ein (erster Index: Zeile, zweiter Index: Spalte). Der Rückgabewert soll in der Variablen belegt gespeichert werden. Er besagt, wieviele Ziffern gegeben, d.h. ungleich null sind.
- Hat das Einlesen geklappt, d.h. es wurde mindestens ein vorgegebener Wert gefunden, geht es weiter, ansonsten wird das Programm mit einer Fehlermeldung beendet.
- Zunächst wird dem Benutzer mitgeteilt, wieviele Ziffern vorgegeben sind und das Sudoku mit dem Unterprogramm anzeigen ausgegeben.
- Die Hauptschleife des Algorithmus' wird wiederholt, bis alle Felder gefüllt sind oder in einem Hauptschleifendurchlauf keine einzige Ziffer neu positioniert werden konnte. Im Rumpf prüft der Algorithmus für jede Zeile und dann für jede Ziffer von eins bis neun ob diese Ziffer in dieser Zeile eindeutig positioniert werden kann:
* Die Anzahl der Hauptschleifendurchläufe soll mitgezählt werden.
* Ist die gesuchte Ziffer nicht in der Zeile vorhanden, wird die Funktion pruefen aufgerufen.
* Konnte diese die Ziffer eindeutig positionieren, gibt sie die Spaltennummer ( 1 bis 9 ) zurück, anderenfalls eine Null.
* Bei erfolgreicher Zuordnung wird die Ziffer im spielfeld platziert und anzeigen aufgerufen. Dabei werden die Koordinaten der ermittelten Ziffer als Parameter übergeben, damit die neu gefundene Ziffer rot eingefärbt werden kann.
- Nachdem die Hauptschleife verlassen wurde, wird gemeldet, ob das Sudoku gelöst werden konnte oder nicht und im Erfolgsfalle die Anzahl der Hauptschleifendurchläufe ausgegeben.
- Funktion pruefen (pruefen. c/f90)
Hier wird der Kern des Ausschlufverfahrens implementiert. Dazu wird das Feld ausschluss benutzt, dessen 9 Elemente für die einzelnen Spalten der aktuell betrachteten Zeile stehen. Im Endeffekt wird jede Spalte, die die aktuell betrachtete Ziffer noch enthalten könnte mit einer Null markiert, jede ausgeschlossene Spalte mit einer 1. Ist nach Ablauf der Prüfung nur noch eine Spalte übrig, wird die Spaltennummer ( 1 bis 9) zurückgegeben, ansonsten eine Null:
- Der Algorithmus prüft für jedes Element der gegebenen Zeile, ob dort bereits eine Ziffer steht. In diesem Falle wird im entsprechenden Element des ausschluss-Feldes eine 1 eingetragen.
Anderenfalls wird...
* zunächst eine Null im entsprechenden Element des ausschluss-Feldes eingetragen und
* alle Zeilen dieser Spalte daraufhin geprüft, ob dort die gesuchte Ziffer vorhanden ist. In diesem Falle wird die Spalte ausgeschlossen, d.h. eine 1 in das entsprechende Element des ausschluss-Feldes eingetragen. (Spaltenausschluß)
* Anschließend müssen die Start- und Endpunkte von Zeile und Spalte des 3x3-Blockes berechnet werden, der das aktuelle Element enthält. Dieses kann mittels ganzzahliger Division erfolgen, z.B. xatart \( =3 *( \) (zeile-1)/3)+1.
* Dann wird für jedes Element dieses 3x3-Blockes geprüft, ob es die gesuchte Ziffer enthält. Auch dann erfolgt ein Vermerk im ausschluss-Feld. (Blockausschluf)
- Nach Ablauf aller Prüfungen wird die Anzahl der Nullen im ausschluss-Feld gezählt.
- Ist sie exakt 1, so konnte die Ziffer eindeutig positioniert werden. In diesem Falle wird die entsprechende Spalte ( 1 bis 9 ) zurückgegeben, anderenfalls eine Null.
2
Ich soll zu dieser Aufgabe 2 Struktogramme erstellen. Jedoch habe ich Probleme damit. Würde mich freuen wenn einer mir ein Struktogramm zu Pruefen machen könnte.
