Wer hat gewonnen?

Ausgangslage: Der Zustand des Spielfeldes ist in einer Variable feld als 2-dimensionales Array gespeichert. Die Einträge sind Strings der Länge 1, entweder “ ”, “x” oder “o”.

Zu schreiben ist eine Funktion, die überprüft ob 3 (oder allgemeiner $n$) gleiche Einträge “x” oder “o” auf einer Linie sind, horizontal, vertikal oder diagonal.

Die Grösse vom Spielfeld ist w=len(feld) in $x$-Richtung und h=len(feld[0]) in $y$-Richtung (für width und height).

Für ein 3×3-Feld könnte man mit einem Haufen if-Abfragen das Feld überprüfen, z.B. wie folgt:

if feld[0][0]!=" " and feld[0][0]==feld[1][0] and feld[1][0]==feld[2][0]:
  return feld[0][0]  # Gewinner melden
...
...
return " "   # Niemand hat gewonnen

Sobald das Feld grösser als 3×3 ist (z.B. 7×6 für Vier gewinnt), ist das natürlich völlig unpraktikabel.

Die Grundidee ist die gleiche wie bei der Parameterdarstellung der Geraden in der Vektorgeometrie. Man definiert einen Startpunkt und einen Richtungsvektor, der die Verschiebung angibt.

D.h. Man startet z.B. im Punkt (0,2) und verschiebt dann schrittweise um den Vektor $\binom{1}{-1}$, um die Punkte (1,1) und (2,0) zu erhalten. Auf diesem Weg zählt man, wie viele Male man hintereinander den gleichen Eintrag findet. Achtung, der folgende Code ist ein Pseudo-Code, der aber an Python angelehnt ist:

punkt = startpunkt
anzahl = 0
was = " "
while (punkt noch im feld):
   inhalt = feld[punktx][punkty]  # Aktuellen Feldinhalt auslesen
     if inhalt==" ":  # Leeres Feld
        anzahl = 0
        was = " "
     else:
        if inhalt==was:  # Gleiches Feld!
           anzahl+=1     # Zähler erhöhen
           if anzahl==3  # Linie voll? Könnte auch eine grössere Zahl sein.
              return was  # Plus eventuell melden, wo 
        else:
           anzahl = 1
           was = inhalt
   punkt = punkt + richtung
   
   

Was jetzt noch fehlt, sind die Startpunkte für die Überprüfung und die Richtungsvektoren. Die Idee ist, die Startpunktskoordinaten in einer for-Schleife zu erzeugen.

Es muss nicht jedes Mal das ganze Feld überprüft werden. Es reicht, von der Position aus zu zählen, wo das Feld verändert wurde. Dazu muss in die vier Richtungen (d.h. horizontal, vertikal und 2 diagonal) vorwärts und rückwärts gezählt werden.

Dazu schreibt man am einfachsten eine for-Schleife über die möglichen Richtungen:

for dir in [[1,0],[1,1], [0,1], [-1,1]]:
  anzahl = In Richtung ''dir'' zählen
  anzahl += In Richtung ''-dir'' zählen
  anzahl +=1  # Die Position selbst zählen
  if anzahl==3:  # Oder was auch immer
     return True  # Sieg melden
return False  # Kein Sieg