# Kombinatorik
## Idee

Einführung in Komplexitätsrechnung an einem Spiel ohne hidden state. Wie berechnet sich die Anzahl Kombinationen? Wie zählt man sie systematisch durch? Zustand (State) und Zustandsübergang (Transition / Move).
## 2x2x2 Rubik

{{:talit:pasted:20230220-154900.png?200}}
### Vorteile
  * Beschränkte Komplexität
  * Alle Cublets sind gleich (keine Unterscheidung Edge vs. Corner vs. Middle wie beim 3er Rubik)


### Komplexitätsrechnung
  * Wieviele Kombinationen gibt es?
    * Upper Bound: $7!\cdot3^7 = 11022480$ Kombinationen
      - Einen Stein betrachten wir als fix und orientieren uns dran.
      - Die 7 restlichen Steine können frei permutiert werden, ohne Zurücklegen, also $(8-1)!$ Kombinationen
      - jeder der 7 restlichen Steine kann in 3 verschiedenen Lagen sein, also $3^7$ Möglichkeiten für jede Kombination
    * Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation.

### Codierung
  * 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$
    * andere Ansätze (Bitfield...)
  * Objektorientierter Ansatz: 
    * Codierung ist interne Angelegenheit des Würfels

### Lösungsansätze
  * Brute-Force
    * Wie kann ich alle systematisch durchprobieren?
      * Suchbaum
      * Tiefensuche (DFS)
      * Breitensuche (BFS) (s.a. [[talit:algorithmen]])
      * Iteratives DFS mit inkrementell steigendem Tiefenhorizont.
      * Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf?)
    * Wie lange dauert es?


## 3er Rubik

  * Gute Quelle / JS Implementierung (für 3x3 Rubik): https://observablehq.com/@onionhoney/how-to-model-a-rubiks-cube

## Weiterführende Themen
  * Grenzen von Brute-Force
    * Transfer zu Passwort-Attacke: 8 vs. 12 Zeichen
    * Schach: Abschätzung der möglichen Zustände
  * Probleme mit unbekanntem Zustand (Markov-Probleme)