A Loop Compression Algorithm for Slitherlink Puzzle

행과 열이 m × n인 k개 셀 보드 판에 주어진 단서 숫자 개수 c개(c < k)의 주위에 단서 숫자 만큼의 선을 그어 하나의 루프를 형성하는 퍼즐을 슬리더링크 퍼즐(SLP)이라 한다. SLP는 지수시간이 필요한 NP-완전 문제로 다항시간의 정확한 해를 찾는 방법이 알려져 있지 않다. 본 논문은 O(c) 수행 복잡도로 정확한 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 초기치로 최외곽 점들을 연결한 최대 크기의 사각형 루프를 형성하였다. 루프에 인접한 단서 셀들에 대해 이 주위에 해당 숫자의 선이 그어지도록 루프를 내부로 점진적으로 압축하는 방법을 적용하였다. 제안된 알고리즘을 18개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 빠르고 정확하게 풀 수 있음을 보였다.