Kommt wohl darauf an, wie man die Aufgabe interpretiert.
Euler würde bedeuten, dass man jede Kante zwischen zwei benachbarten Feldern einmal ablaufen muss.
Dabei würde man zwangsläufig Knoten mehrfach besuchen, und das ist beim vorliegenden Problem nicht erlaubt.
Hamiltonwege sind ja nicht maximal, z.b. TSP entspricht dem kuerzesten Hamiltonkreis.
Die Minimalität bezieht sich dort auf die Kantengewichte entlang des gesuchten Pfades, nicht auf die Anzahl der besuchten Knoten (die ist fest).
Ich plädiere auch für "alles durchprobieren".
In einem Zustand merkt man sich, wo man gerade ist und welche Felder bereits besucht wurden (2D-Bitmap); evtl. zum Beschleunigen noch die verbleibende Anzahl noch zu besuchender Felder.
Der Startzustand ist klar: man befindet sich auf der Startposition und hat noch kein Feld besucht außer eben das Startfeld.
Den Startzustand legt man in eine Warteschlange.
Ein globaler Zähler zählt die Anzahl bisher gefundener maximaler Wege.
Aus der Warteschlange nimmt man sich nun immer den ersten Zustand heraus. Befindet man sich in diesem Zustand auf dem Zielfeld, so wird geprüft, ob auch alle anderen Felder besucht wurden. Wenn ja, ist das ein gültiger maximaler Weg, und man kann den globalen Zähler erhöhen.
Der Zustand wird aus der Warteschlange gelöscht, und es werden alle möglichen Nachfolgezustände erzeugt und wieder in die Warteschlange eingefügt (nur wenn die aktuelle Position nicht das Zielfeld ist, denn sonst kann hieraus kein gültiger maximaler Weg mehr entstehen, denn das Zielfeld muss als letztes erreicht werden).
Wenn die Warteschlange leer ist, hört man auf, und der Zähler sollte nun die korrekte Antwort enthalten.
Vielleicht kann man durch bidirektionale Suche (Vor- und Rückwärtssuche) noch einiges an Performance rausholen.