Von Stunden zu 360 ms: Über-Engineering einer Puzzle-Lösung

Der Autor versucht, ein Sudoku-Puzzle zu lösen, mit dem Ziel, die Lösung zu finden, die den größtmöglichen GGT unter den neun neunstelligen Zahlen erzeugt, die durch die Zeilen gebildet werden. Anfängliche Versuche mit dem Z3-Solver konnten innerhalb von Stunden keine Lösung finden. Der Autor setzte dann mehrere Optimierungsstrategien ein: mathematische Analyse zur Reduzierung des Suchraums, einen BFS-Algorithmus und iterative Verbesserungen der Funktion `is_good`, wobei er von HashSet zu Bitset wechselte und schließlich SIMD für vektorisierte Berechnungen verwendete. Multithreading und verfeinerte Thread-Synchronisierung reduzierten die Lösungsdauer von Stunden auf 360 ms und erzielten eine Beschleunigung um mehr als das 1600-fache. Obwohl sich eine hartcodierte Antwort als die schnellste erwies, zeigt der Artikel, dass selbst scheinbar einfache arithmetische Probleme durch sorgfältige algorithmische Optimierung erhebliche Performance-Verbesserungen bieten.