geknac’t
Kürzeste Wege finden: Auflösung der Knobelaufgabe c’t-Racetrack
Ein virtuelles Autorennen ähnlich einem alten Papier-und-Bleistift-Spiel war eine Knobelaufgabe, mit der wir c’t-Leser vor längerer Zeit herausgefordert haben. Es hat sich gezeigt: Viele spannende Wege führen zur Lösung.
Die Aufgabe war auch von Hand lösbar, aber um zweifelsfrei das Optimum zu finden, musste doch der Computer ran: Ein virtueller Rennwagen steht auf dem Startpunkt des abgebildeten Parcours und soll in möglichst wenig Schritten zum Ziel gefahren werden.
Die Regeln orientieren sich an einem Spiel, das man mit einem Stift auf kariertem Papier spielen kann, sind aber ein bisschen abgewandelt. Alle Koordinaten sind ganzzahlig. In jedem Schritt wird zunächst der aktuelle Geschwindigkeitsvektor zur Position addiert und anschließend darf der c’t-Racer um einen Vektor der Länge höchstens 10 in eine beliebige Richtung beschleunigt werden.
Gesucht ist eine möglichst kurze Folge zulässiger Beschleunigungsvektoren, die den Wagen vom Start zum Ziel bringt und ihn dort zum Stillstand kommen lässt. Der Geschwindigkeitsvektor muss am Ende also (0, 0) betragen. Die Hindernisse sind der Einfachheit halber gerade Linien und dürfen nicht berührt werden.
Man braucht im Prinzip nur Millimeterpapier, um diese Aufgabe komplett von Hand anzugehen, aber das hat unseres Wissens kein c’t-Leser gemacht. Mehr als die Hälfte der Einsender haben das Problem aber im Prinzip von Hand gelöst und den Computer nur als Hilfsmittel zur Visualisierung benutzt.