数時間から360ミリ秒へ：パズル解法のオーバーエンジニアリング

著者は、行で形成された9つの9桁の数の中で、可能な限り最大の最大公約数を得ることを目的とした数独パズルに挑戦しました。Z3ソルバーを使った初期の試みは、数時間経っても解が見つかりませんでした。そこで著者は、いくつかの最適化戦略を採用しました。探索空間を狭めるための数学的分析、BFSアルゴリズム、そして`is_good`関数の反復的な改良（HashSetからbitsetへの移行、そしてベクトル化計算のためのSIMDの活用）です。マルチスレッド化と洗練されたスレッド同期により、解法時間は数時間から360ミリ秒に短縮され、1600倍以上の高速化を実現しました。ハードコードされた解答が最も速い方法であることが判明しましたが、この記事は、一見単純な算術問題でも、綿密なアルゴリズム最適化によって大幅な性能向上が得られることを示しています。