8년 전의 폴리오미노 타일링 알고리즘: 휴리스틱을 사용한 백트래킹 검색

이 글에서는 폴리오미노 타일링 문제를 해결하기 위한 알고리즘을 설명합니다. 핵심 아이디어는 기하학적 문제를 그래프 이론 문제로 변환하고 휴리스틱을 사용하는 백트래킹 검색 알고리즘을 사용하는 것입니다. 먼저 알고리즘은 전처리 단계에서 가능한 모든 배치를 계산하고 모든 가능성을 나타내는 이분 그래프를 생성합니다. 그런 다음 백트래킹 검색 알고리즘은 조건을 만족하는 배치의 부분 집합을 찾고, 제약이 있는 그리드 포인트 우선 순위 지정 및 그리드 분할과 같은 휴리스틱으로 최적화됩니다. 이 알고리즘은 임의의 그리드 모양과 폴리오미노 집합을 처리하는 데 뛰어난 일반성과 견고성을 보여줍니다. 저자는 또한 알고리즘의 한계와 향후 개선 사항에 대해 논의하며, 문제를 SAT 문제로 변환하여 해결하는 방법 등을 제시합니다.