De plusieurs heures à 360 ms : sur-ingénierie d’une solution de puzzle

L’auteur tente de résoudre un casse-tête de Sudoku dans le but de trouver la solution qui produit le plus grand PGCD possible parmi les neuf nombres à neuf chiffres formés par les lignes. Les tentatives initiales utilisant le solveur Z3 n’ont pas réussi à trouver de solution en quelques heures. L’auteur a ensuite employé plusieurs stratégies d’optimisation : une analyse mathématique pour réduire l’espace de recherche, un algorithme BFS et des améliorations itératives de la fonction `is_good`, passant de HashSet à bitset et enfin utilisant SIMD pour le calcul vectoriel. Le multithreading et la synchronisation raffinée des threads ont réduit le temps de résolution de plusieurs heures à 360 ms, obtenant une accélération de plus de 1600x. Bien qu’une réponse codée en dur se soit avérée la plus rapide, l’article montre comment même des problèmes arithmétiques apparemment simples offrent des gains de performance significatifs grâce à une optimisation algorithmique méticuleuse.