Kombinatorik

Gute Quelle / JS Implementierung (für 3×3 Rubik): https://observablehq.com/@onionhoney/how-to-model-a-rubiks-cube
Komplexitätsrechnung an einem einfachen Beispiel einführen (z.B. 2x2x2 Rubik)
- Wieviele Kombinationen gibt es?
  - Upper Bound: $7!\cdot7^3 = 1728720$ Kombinationen
    1. Einen Stein betrachten wir als fix und orientieren uns dran.
    2. Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, also $(8-1)!$ Kombinationen
    3. jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $7^3$ Möglichkeiten für jede Kombination
  - Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation.
Wie lässt sich ein Würfel darstellen / codieren?
- Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right)
- Koordinatennetz mit planarer Sicht
- String oder Array mit Länge $6*4 = 24$
Brute-Force-Ansätze
- Wie kann ich alle systematisch durchprobieren?
  - Suchbaum
  - Tiefensuche (DFS)
  - Breitensuche (BFS) (s.a. Graphenalgorithmen)
  - Iteratives DFS mit inkrementell steigendem Tiefenhorizont.
  - Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf?)
- Wie lange dauert es?
Grenzen von Brute-Force
- Transfer zu Passwort-Attacke: 8 vs. 12 Zeichen
- 3x3x3-Rubik
- Schach
Probleme mit unbekanntem Zustand (Markov-Probleme)

Dies ist eine alte Version des Dokuments!