수 시간에서 360밀리초로: 퍼즐 해법의 과도한 엔지니어링

저자는 행으로 구성된 9개의 9자리 숫자들 중 최대 공약수를 얻는 것을 목표로 수도쿠 퍼즐을 해결하려고 시도했습니다. Z3 솔버를 사용한 초기 시도는 수 시간이 지나도 해결책을 찾지 못했습니다. 그래서 저자는 몇 가지 최적화 전략을 사용했습니다. 검색 공간을 줄이기 위한 수학적 분석, BFS 알고리즘, 그리고 `is_good` 함수의 반복적인 개선(HashSet에서 bitset으로 전환, 그리고 벡터화 계산을 위한 SIMD 활용)입니다. 멀티스레딩과 세련된 스레드 동기화를 통해 해결 시간은 수 시간에서 360밀리초로 단축되었고, 1600배 이상의 속도 향상을 달성했습니다. 하드코딩된 답변이 가장 빠른 방법으로 판명되었지만, 이 글은 단순해 보이는 산술 문제라도 신중한 알고리즘 최적화를 통해 상당한 성능 향상을 얻을 수 있음을 보여줍니다.