Toads and Frogs

• Konfiguration ist Zeichenkette über Alphabet Σ = {T, F,o} (Kröte, Frosch, Leer),

  Züge: Spieler L: To→oT, TFo→oFT,

  Spieler R (frog): oF→Fo,oTF→FTo

• Ü: Graph aller Konfigurationen für Start ToF, To^kF, ...

• allgemeine Analyse ist NP-vollständig,

  T. Thanatipanonda, D. Zeilberger 2007/8: https://arxiv.org/abs/0710.4951, https://arxiv.org/abs/0804.0640