Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg1-2020:funktionen-mit-klassen [2021/04/07 09:19]
Ivo Blöchliger [Tic Tac Toe]
+++ lehrkraefte:blc:informatik:ffprg1-2020:funktionen-mit-klassen [2021/04/09 16:07] (current)
Ivo Blöchliger
@@ Line 14: / Line 14: @@
 print(t)          # Noch nicht spannend...
 </code>
-  * Fügen Sie eine Methode ''__str__(self)'' hinzu, die einen String zurückgibt, die das aktuelle Spielfeld darstellt. Z.B. wenn ''feld=<nowiki>[[0,1,1], [2,1,2], [0,2,2]]</nowiki>'' dann soll die Ausgabe wie folgt sein:
+  * Fügen Sie eine Methode ''<nowiki>__str__</nowiki>(self)'' hinzu, die einen String zurückgibt, die das aktuelle Spielfeld darstellt. Z.B. wenn ''feld=<nowiki>[[0,1,1], [2,1,2], [0,2,2]]</nowiki>'' dann soll die Ausgabe wie folgt sein:
 <code  txt>
    | X |
@@ Line 26: / Line 26: @@
 print(t)
 </code>
-ausgegeben werden. Die Methode ''__str__'' wird automatisch aufgerufen, falls diese existiert. //Genau genommen, wird sonst die ''__str__'' Methode der Grund-Klasse ''object'' aufgerufen, von der alle Klassen erben.//
+ausgegeben werden. Die Methode ''<nowiki>__str__</nowiki>'' wird automatisch aufgerufen, falls diese existiert. //Genau genommen, wird sonst die ''<nowiki>__str__</nowiki>'' Methode der Grund-Klasse ''object'' aufgerufen, von der alle Klassen erben.//
 Bauen Sie die Klasse mit folgenden Methoden aus:
-  * ''isEmpty(x,y)'': Liefert ''True'', wenn das entsprechende Feld existiert und noch leer ist.
+  * ''isEmpty(self, x,y)'': Liefert ''True'', wenn das entsprechende Feld existiert und noch leer ist.
-  * ''place(x,y,player)'': Platziert ein 'O' oder 'X', je nach Wert von ''player'' (1 oder 2).
+  * ''place(self, x,y,player)'': Platziert ein 'O' oder 'X', je nach Wert von ''player'' (1 oder 2).
-  * ''winner()'': Liefert 0, wenn niemand gewonnen hat, oder 1 oder 2, wenn der entsprechende Spieler gewonnen hat.
+  * ''winner(self, )'': Liefert 0, wenn niemand gewonnen hat, oder 1 oder 2, wenn der entsprechende Spieler gewonnen hat.
-  * ''full()'': Liefert ''True'', wenn das Feld voll ist.
+  * ''full(self, )'': Liefert ''True'', wenn das Feld voll ist.
-  * ''reset()'': löscht das Spielfeld
+  * ''reset(self, )'': löscht das Spielfeld
+===== Sudoku =====
+Schreiben Sie eine Klasse ''Sudoku'' mit einem Konstruktur ''__init__(self,sudoku)'', der als Eingabe einen String erwartet, wie in der
+[[lehrkraefte:blc:informatik:ffprg1-2020:funktionen#sudoku_parsen|Originalaufgabe]] beschrieben.
+Die Klasse soll zwei Attribute haben: eine 9x9-Liste ''self.feld'', der aktuelle Zusand des Felds darstellt und eine 9x9-Liste ''self.given'', mit Einträgen ''True'' oder ''False'', je nachdem, ob der entsprechende Eintrag bereits im Rätsel vorgegeben ist.
+Fügen Sie der Klasse eine Methode ''<nowiki>__str__</nowiki>(self)'' hinzu, die einen String wie in der [[lehrkraefte:blc:informatik:ffprg1-2020:funktionen#sudoku_schoen_ausgeben|Originalaufgabe]] zurückgibt. Damit sollte folgendes Programm (nach der Klassendefinition) dann lauffähig sein:
+<code python>
+s = Sudoku("200080300\n060070084\n030500209\n000105408\n\n000000000\n402706000\n301007040\n720040060\n004010003")
+print(s)
+</code>
+Bauen Sie die Klasse mit folgenden Methoden aus:
+  * ''allowed(self, x,y, w)'' liefert ''True'', wenn der Wert ''w'' an der Stelle ''x'', ''y'' eingetragen werden kann, d.h. in der selben Spalte, Kolonne und Unterquadrat der ''w'' noch nicht vorkommt.
+==== Solver ====
+Eine mögliche Strategie zum Lösen eines Sudokus geht wie folgt:
+  * Man setzt die Position $p$ auf das erste noch freie Feld.
+  * Wiederholen
+    * Bestimme die nächste mögliche Zahl im Feld $p$, die grösser ist, als die Zahl, die schon da steht (die kleinste, wenn das Feld leer war).
+      * Wenn es diese gibt, schreibe die Zahl ins Feld und rücke $p$ auf das nächste freie Feld vor. Sind alle Felder voll ist das Sudoku gelöst. Ende.
+      * Sonst lösche das Feld und gehe zurück auf das letzte Feld, das nicht vorgegeben ist. Wenn nicht weiter zurückgegangen werden kann, ist das Sudoku unlösbar. Ende
+Diese Strategie ist ausreichend, um einfache Sudokus zu lösen. Die Strategie kann noch viel effizienter gemacht werden, wenn die Reihenfolge der Feld dynamisch angepasst wird, d.h. es werden erst jene Felder abgearbeitet, die am wenigsten mögliche Zahlen haben. Entweder merkt man sich die Reihenfolge oder man programmiert das rekursiv (und merkt sich die Reihenfolge so in den lokalen Variablen der Funktionsaufrufen).