“Ever had to detangle a ball of wool?” (“Mußten sie jemals ein Wollknäuel entwirren?”) wird man bei “Detangle” gefragt. Für die wahrscheinlichere Zielgruppe der Mathe-Nerds wäre wohl “Mußten Sie jemals den Boyer-Myrvold-Algorithmus anwenden?” die passendere Frage.

Worum geht es bei dem Spiel?
Man bekommt einen Graphen vorgesetzt
detangle1
und soll seine Knoten solange verschieben bis alle Überkreuzungen verschwinden:
detangle2
So sah es vor dem letzten Schritt aus:
detangle3
und so vor dem vorletzten:
detangle4

Was steckt mathematisch dahinter? Es geht darum, einen Graphen ohne Überkreuzungen in die Ebene einzubetten. Graphen, die sich kreuzungsfrei in die Ebene einbetten lassen, heißen planare Graphen. Nach dem Satz von Kuratowski Ist ein Graph genau dann planar, wenn er keine Unterteilungen von K5 oder K3,3 als Teilgraphen enthält. Für die Graphen, die man bei “Detangle” vorgesetzt bekommt, ist das natürlich immer der Fall.
In dem Spiel geht es nicht nur um irgendwelche überkreuzungsfreien Einbettungen des Graphen in die Ebene, zusätzlich sollen auch noch alle Kanten Geradenstücke sein. Auch das wird aber von der Graphentheorie abgedeckt, nämlich vom Satz von Fary: jeder planare Graph läßt sich überkreuzungsfrei so in die Ebene einbetten, dass die Kanten Geradenstücke sind.
Das sind natürlich nur Existenzsätze, die einem bei der Lösung des Problems nicht weiterhelfen. Aber auch für dieses Problem gibt es Algorithmen, die effektivsten sind wohl der Boyer-Myrvold-Algorithmus und der Fraysseix-Ossona-Rosenstiehl-Algorithmus.

Die App gibt es hier für 0,99 $.

Kommentare (4)

  1. #1 Wolfgang Barth
    1. Dezember 2013

    Da gibts viele Apps, die das gleiche machen. Kostenfrei z.B. ist “untangle unlimited” oder “untangle me free” und viele viele andere, wenn man nach “untangle” sucht.

  2. #2 hugo
    1. Dezember 2013

    Was ähnliches in Flash fürs Web: https://planarity.net/ und für unixoide Desktops: https://web.mit.edu/xiphmont/Public/gPlanarity.html

  3. #3 wereatheist
    2. Dezember 2013

    @hugo: Super Tipp, danke. Gleich gPlanarity installiert und ausprobiert 🙂

  4. #4 Carsten Kemper
    2. Dezember 2013

    Ich empfehle “Simon Tatham’s Portable Puzzle Collection” für so ziemlich jedes Gerät.
    Untangle ist dort eines von vielen “kleinen” Spielen.
    Link: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/