Wir behandeln im Unterricht gerade das Thema Graphen und DFS und BFS. Als Aufgabe habe ich eine sehr theoretische Aufgabe bekommen. Nämlich die folgende:
Jeder Spielstand von Tic-Tac-Toe wird in einem Graphen dargestellt.
a) Wie viele Knoten auf Stufe 1 existieren (also alle Spielstände wenn Spieler X 1 Feld gesetzt)?
Hier hätte ich gesagt, dass es 9 Spielstände gibt. Das heisst in jedem Feld ein "X".
b) Wie viele Knoten auf Stufe 2?
Bei dieser Aufgabe, hätte ich gesagt, das wären hier nur 8 Spielstände pro oberen Spielstand. Das wäre ja dann: 9*8 = 72
c) Wie viele Spielstände die in einem Gewinn für X resultieren gibt es bei Stufe 8
Stimmt dann hier meine Rechnung: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 = 362'880 Spielstände. Stimmt hier meine Rechnung?
d) Wie viele wirklich unterschiedliche Spielstände gibt es auf Level 2? Mit einemm DAG (Directed acyclic graph) können viele Knoten eliminiert werden, da einige Knoten denselben Spielstand repräsentieren (z.B. man rotiert oder spiegelt das Feld)
Wie geht man hier vor? Ich weiss auf Level 1 gibt es zum Beispiel nur 3 verschiedene Spielstände.
