NP-Complete 문제, 십자말 풀이 생성 알고리즘의 비밀
십자말 풀이 생성은 NP-Complete 문제로, 효율적인 알고리즘이 존재하지 않음.
저자는 Greedy 알고리즘의 한계를 극복하고, Lazy Evaluation, Constraint Propagation, Domain Splitting 기법을 활용하여 성능을 개선함.
커뮤니티에서는 알고리즘 최적화 과정과 실용적인 문제 해결 접근 방식에 대한 높은 관심을 보임.
Lazy Evaluation과 PossibleLines 구조
십자말 풀이 생성의 핵심은 PossibleLines라는 Lazy Data Structure를 활용하는 것이다. 구체적으로, 모든 가능한 단어 조합을 미리 계산하지 않고, 필요할 때마다 필터링하는 방식을 사용한다. 따라서 메모리 사용량을 줄이고, Constraint Propagation을 효율적으로 수행할 수 있다. 결과적으로, 복잡한 조합 문제를 효과적으로 해결한다.
Constraint Propagation과 Domain Splitting
알고리즘은 Constraint Propagation을 통해 각 행/열의 가능한 단어 집합을 좁혀나간다. 구체적으로, 한 단어가 결정되면 교차하는 다른 단어들에 제약 조건이 전파된다. 반면, Domain Splitting 기법을 통해 가능한 단어 집합을 이분 검색하여 탐색 공간을 줄인다. 결과적으로, 탐색 속도를 획기적으로 향상시킨다.
CharSet 최적화와 실전 적용
저자는 CharSet을 Bitmask로 구현하여 문자 집합 연산을 최적화했다. 구체적으로, 각 문자를 비트 단위로 표현하여 Intersection 연산을 빠르게 수행한다. 따라서 필터링 성능을 개선하고, 전체 알고리즘의 속도를 높였다. 결과적으로, 십자말 풀이 생성 시간을 단축하고, 실용적인 수준의 결과를 얻었다.
