====== Methoden (Funktionen in Klassen) ======

===== Tic Tac Toe =====
Diese Aufgabe entspricht [[lehrkraefte:blc:informatik:ffprg1-2020:funktionen#tic-tac-toe_schoen_ausgeben|dieser Aufgabe]] im Kapitel Funktionen.

  * Schreiben Sie eine Klasse ''TicTacToe'' mit einem Konstruktor, der ein leeres 3x3-Feld anlegt:
<code python>
class TicTacToe:
    def __init__(self):     # Konstruktor, wird beim Anlegen einer neuen Instanz aufgerufen.
        # Ein 3x3 Feld initialisieren
        self.feld = []  # TODO
        
t = TicTacToe()   # Neue Instanz
print(t)          # Noch nicht spannend...
</code>        
  * 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 |   
---+---+---
 O | O | X 
---+---+---
 O | X | X 
</code>
Damit kann das Feld einfach mit 
<code python>
print(t)
</code>
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(self, x,y)'': Liefert ''True'', wenn das entsprechende Feld existiert und noch leer ist.
  * ''place(self, x,y,player)'': Platziert ein 'O' oder 'X', je nach Wert von ''player'' (1 oder 2).
  * ''winner(self, )'': Liefert 0, wenn niemand gewonnen hat, oder 1 oder 2, wenn der entsprechende Spieler gewonnen hat.
  * ''full(self, )'': Liefert ''True'', wenn das Feld voll ist.
  * ''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).