9. Dezember 2016 08:23:56 CET
[blockquote]Fabian Märkert sagte:
Haha xD und ich war schon stolz, als ich die Laufzeit in Java auf eine halbe Stunde runter hauen konnte :P
Der Knackpunkt war doch, die schon bereits gehabten Puzzlemöglichkeiten aus zu sortieren oder? >.<[/blockquote]
Sehe ich genauso! Hatte Anfangs auch das Problem mit der langen Laufzeit (programmiere auch in Java), hab das aber wie folgt gelöst:
Die Liste, welche die gehabten Puzzlemöglichkeiten darstellt, wird je nach Tiefe der Breitensuche gigantisch. Daher muss man hier eine Hashtabelle verwenden, damit das Durchsuchen der gehabten Puzzlemöglichkeiten quasi "blitzschnell" funktioniert (Liegt an der Komplexität von Hashtabellen)
Zum Vergleich: Mit ArrayList habe ich nach 40 min keine Lösung für das 3. Beispiel gefunden und daher abgebrochen. Alleine durch den Einsatz von HashSet schafft selbst mein PC das in weniger als 20 Sekunden