슬리더링크 퍼즐에 관한 루프 압축 알고리즘
초록
행과 열이 m × n인 k개 셀 보드 판에 주어진 단서 숫자 개수 c개(c < k)의 주위에 단서 숫자 만큼의 선을 그어 하나의 루프를 형성하는 퍼즐을 슬리더링크 퍼즐(SLP)이라 한다. SLP는 지수시간이 필요한 NP-완전 문제로 다항시간의 정확한 해를 찾는 방법이 알려져 있지 않다. 본 논문은 O(c) 수행 복잡도로 정확한 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 초기치로 최외곽 점들을 연결한 최대 크기의 사각형 루프를 형성하였다. 루프에 인접한 단서 셀들에 대해 이 주위에 해당 숫자의 선이 그어지도록 루프를 내부로 점진적으로 압축하는 방법을 적용하였다. 제안된 알고리즘을 18개 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 퍼즐을 빠르고 정확하게 풀 수 있음을 보였다.
Abstract
A puzzle that forms a loop by drawing as many lines as the number of clues as c(c < k) around a given number of cues on a board of k cells with rows and columns m × n is called a Slitherlink Puzzle (SLP). SLP is an NP-complete problem that requires exponential time, and it is not known how to find the exact solution of polynomial time. This paper proposed an algorithm to obtain an accurate solution with the complexity of performing O(c). The proposed algorithm formed a maximum-sized rectangular loop connecting the outermost dots at the initial value. For clue cells adjacent to the loop, a method of gradually compressing the loop inward so that a line of the corresponding number is drawn around it was applied. Applying the proposed algorithm to 18 benchmarking experimental data showed that puzzles can be solved in polynomial time for all problems.
Keywords:
slitherlink puzzle, loop, compression, unique line, empty lineⅠ. 서 론
슬리더링크(Slitherlink)는 일본의 퍼즐회사 니코리(Nikoli)에서 개발한 퍼즐로, 점들(Dots)로 이루어진 주어진 격자에서 단서(실마리, c) 숫자 주위에 해당 숫자의 선을 행 또는 열로 그어 하나의 루프를 형성하는 퍼즐이다[1][2]. SLP 규칙은 매우 간단한 반면에, 정확한 해를 다항시간으로 구하는 방법은 알려져 있지 않은 NP-완전(NP-complete)으로 분류된 난제이다[3]-[6]. 지금까지 알려진 방법은 독립된 단서 숫자들 전체와 단서들이 모여 있는 일부 경우에 한해 단서 숫자들 주위에 선을 긋는 규칙들을 제시하였을 뿐이며, 모든 경우 수를 고려하지는 못하고 있다[2]. 이러한 규칙들을 적용할 경우 가장 큰 문제점은 하나의 루프를 형성하기가 너무 어렵다는 점이다. 따라서 본 논문에서는 최외곽의 루프를 형성하고, 이 루프를 파괴하지 않으면서 단서들(c) 각각에 대해 선의 수 l이 l > c인 경우 초과하는 선을 삭제하며, l < c인 부족인 경우 추가 선을 그으면서 루프를 내부로 압축하여 최종적으로 모든 단서들이 c = l를 갖는 하나의 루프를 형성하는 방법을 제안한다.
본 논문은 SLP의 정확한 해를 O(c)의 선형시간으로 찾는 규칙을 가진 알고리즘을 제안한다. 2장에서는 SLP 사례 데이터를 통해 개념을 고찰해 본다. 3장에서는 SLP를 O(c)의 선형시간으로 풀 수 있는 루프 압축 알고리즘을 제안한다. 4장에서는 벤치마킹 실험 데이터를 대상으로 제안된 알고리즘의 적합성을 검증한다.
Ⅱ. 관련 연구와 연구 배경
슬리더링크 퍼즐의 규칙은 다음과 같다[1].
(규칙 1) 행 또는 열의 선으로 인접한 점들을 연결하여 하나의 루프(폐회로)를 형성한다.
(규칙 2) 셀에 주어진 단서(실마리) 숫자 [1,4]는 주위에 해당 숫자의 선이 그어짐을 의미하며, 공란 셀은 임의의 선을 그을 수 있다. 단, ‘0’는 주위에 선이 없음을 의미한다.
(규칙 3) 루프는 자체적으로 절대로 엇갈릴(교차할) 수 없고 갈라질 수도 없다. 즉, 단일 루프를 형성해야만 한다.
그림 1의 SLP-1[2] 예제 문제를 대상으로 슬리더링크 퍼즐을 고찰해 보자. 좌측은 주어진 문제이며, 우측은 해(정답)이다. 우측 정답은 위의 3가지 규칙을 모두 만족함을 알 수 있다.
Slitherlink puzzle of SLP-1
슬리더링크 퍼즐은 m × n 셀(또는 단서)을 가진 보드 판에 실마리(단서) 숫자가 c개(c < m × n) 들어 있으며, 각 단서 숫자 주위의 4개 점 들을 대상으로 해당 숫자만큼의 선을 그어야만 하며, 최종적으로 얻은 선들은 하나의 루프(폐회로)를 형성해야만 한다. 여기서는 편의상 점들을 표기하지 않고 사각형으로 표기하였다. 즉, 격자의 교차 지점을 점으로 생각하면 된다. 셀에 주어진 단서들은 blank, 0,1,2,3,4의 숫자를 가질 수 있으며, blank(공란)은 주위에 선을 [0,4] 범위에서 임의로 그을 수 있음을, ‘0’은 주위에 선이 없어야 함을, [1,4]는 주위에 선의 개수가 단서 수만큼 그어야 함을 의미한다.
이와 같은 규칙을 준수하면서 하나의 루프를 형성한 것이 우측의 정답임을 알 수 있다. 이러한 퍼즐을 풀기 위해 지금까지 알려진 일부 방법들은 그림 2에 제시되어 있다[2]. 그러나 실제로는 다양한 단서들이 결합된 형태를 취하고 있어 이 방법들만을 적용하는데 한계가 있어 단지 쉽게 풀기 위한 참조하는 수준에 불과하다.
Known solution methods
기존에 알려진 일부 규칙들을 적용하여 전수탐색 법(Brute-force)이나 분기한정법(Branch-and-bound)을 적용한다면 mn에 대해 O(mn!) 수행 복잡도가 요구된다.
3장에서는 이러한 알려진 규칙들을 적용하지 않고도 O(c)의 선형시간으로 정확한 해를 구하는 알고리즘을 제시한다.
Ⅲ. 루프 압축 알고리즘
슬리더링크 퍼즐의 최종 목표는 단일 루프를 형성하는 것이다. 이 목표를 충족하기 위해 사전에 최외곽의 점들을 대상으로 행과 열의 사각형 루프를 형성한다. 다음으로 최외곽 셀(1행과 m행, 1열과 n열)부터 그림 3의 단서 선 긋기 방법을 적용하면서 루프를 내부로 압축시킨다.
Line drawing of clue for SLP-1
제안된 알고리즘을 루프 압축 알고리즘(LCA, Loop Compression Algorithm)이라 하며, 그림 4와 같이 수행된다.
Loop compression algorithm
제안된 LCA를 그림 1의 SLP-1에 적용한 결과는 그림 5에 제시하였다.
LCA for SLP-1
사전에 6 × 6 셀 최외곽 점들을 잇는 최대 크기의 사각형 루프를 작도한다. 첫 번째로 ‘0’에 인접한 셀에 ‘x’를 표기(Empty line)하여 경계선을 긋지 못하도록 하고 루프를 단서 숫자 근방까지 내부로 압축시킨다. 두 번째로 인접한 2개 단서들을 거치는 선으로 내부로 루프를 압축한다. 이 때 동일한 숫자의 단서들 간에는 겹칠 수 없으므로 겹치는 셀에는‘x’를 표기한다. 루프를 내부로 압축하는 방법은 여러 갈래의 선택지가 있는 단서와 유일한 방향의 선(Unique line)을 갖는 단서가 존재할 경우 유일 선 단서를 우선하여 루프를 압축하는 방법을 적용하였다. 각 과정에서 선 개수를 충족한 단서의 잉여 셀에는 ‘x’를 표기한다. 또한 선을 그을 수 있는 유일한 선이 존재하는 단서를 우선하여 이 부분으로 루프의 선을 긋는다. 이와 같은 방법으로 루프를 점진적으로 압축하여 내부의 모든 단서들의 선 개수를 충족하는 최종적인 루프로 압축시켜 퍼즐을 O(c)의 선형시간으로 풀 수 있다. 제안된 알고리즘의 가장 큰 특징은 슬리더 링크의 최종 목표인 단일 루프를 초기에 m × n 크기의 최외곽 점들 크기로 설정한 후, 내부 단서들 주변으로 루프를 압축하는 과정에서 절단(단락)시키지 않는다는 점에서 항상 해를 보장할 수 있다고 할 수 있다.
Ⅳ. 알고리즘 적용성 평가
본 장에서는 그림 6의 실험 데이터들을 대상으로 제안된 LCA를 적용하여 본다.
Experimental data
그림 6의 실험 데이터들을 대상으로 제안된 LCA를 적용한 결과는 그림 7에 제시하였다.
LCA for experimental data
본 논문에서 거론된 18개 유형의 실험 데이터에 대해 LCA는 퍼즐을 O(c)의 선형시간으로 빠르고 정확하게 푸는데 성공하였다. 이 과정에서 실패 사례 규칙을 추가로 발견하지는 못하였다. 또한 분기한정법(백트래킹)이나 메타휴리스틱 기법을 적용한 사례가 없어 이들 방법과의 정량적 성능비교가 불가하여 이 부분은 생략한다.
슬리더 링크 퍼즐은 스도쿠나 지뢰찾기 등과 같이 앱으로 출시되지 않고 있으며, 연구가 거의 없어 다양한 유형의 밴치마킹 데이터를 얻는데 어려움이 있어, 본 논문에서는 그림 6의 18개 데이터를 밴치마킹 데이터로 한정시켰다. 추후 보다 많은 유형의 문제들이 제시되고 제안된 알고리즘의 단점이 부각된다면 본 알고리즘을 보완시킬 예정이다.
Ⅴ. 결 론
본 논문에서는 NP-완전으로 지수시간이 소요되는 메타휴리스틱 기법 또는 전수탐색 법(Brute force) 이외에는 퍼즐을 풀 수 없는 슬리더링크 퍼즐을 다항시간으로 풀 수 있는 규칙을 제안하였다.
제안된 방법은 초기치로 최외곽 점들을 잇는 최대 크기의 사각형 루프를 형성하였다. 루프에 인접한 단서 숫자들 만큼의 선이 주위에 존재하도록 루프를 점진적으로 내부로 압축시키는 방법을 적용하였다.
제안된 알고리즘을 18개 유형의 벤치마킹 데이터들에 적용한 결과 O(c)의 선형시간 복잡도로 단순하면서도 효율적으로 퍼즐을 푸는데 성공하였다.
References
- Nikoli, "Slitherlink", https://www.nikoli.co.jp/en/puzzles/slitherlink/, . [accessed: Nov. 10, 2025]
- Wikipedia, "Slitherlink", https://en.wikipedia.org/wiki/Slitherlink, . [accessed: Nov. 10, 2025]
- T. Yato, "On the NP-completeness of the Slither Link Puzzle", IPSJ SIG Notes, Vol. AL-74, pp. 25-32, Jan. 2000.
-
J. Kölker, "Selected Slither Link Variants are NP-complete", Journal of Information Processing, Vol. 20, No. 3, pp. 709-712, Jul. 2012.
[https://doi.org/10.2197/ipsjjip.20.709]
-
H. Tang, "A Framework for Loop and Path Puzzle Satisfiability NP-Hardness Results", arXiv:2202.02046, , pp. 1-40, Feb. 2022.
[https://doi.org/10.48550/arXiv.2202.02046]
- Y. Takauki, "Complexity and Completeness of Finding Another Solution and its Application to Puzzles", IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, Vol. E86-A, No. 5, pp. 1052-1060, May 2003.
- Maybe Puzzles, "Slither Link", https://maybepuzzles.com/types/slither-link/, . [accessed: Nov. 10, 2025]
- D. Pleacher, "Slither Link #3 – Answers", https://www.pleacher.com/mp/puzzles/miscpuz/slit3ans.html, . [accessed: Nov. 10, 2025]
- T. Snydermar, "Dr. Sudoku Prescribes: Slitherlink", http://wired.com/magazine/2013/03/dr-sudoku-slitherlink, . [accessed: Nov. 10, 2025]
- Puzzle Madness, "Daily Medium Slitherlink Puzzle", https://puzzlemadness.co.uk/slitherlink/medium, . Sep. 2023.
- Motris, "Friday Puzzle #135 - Loop the Loops (DD Part 8)", http://motris.livejournal.com/161428.html, . [accessed: Nov. 10, 2025]
- Any Puzzle Media, "Slitherlink Logic Puzzles", https://www.anypuzzle.com/Slitherlink, . [accessed: Nov. 10, 2025]
- D. Pleacher, "Slither Link #5", https://www.pleacher.com/mp/puzzles/miscpuz2/slit5ans.html, . [accessed: Nov. 10, 2025]
- djmv01, "Answer of Slither Link Question 1(10x10)", http://microrrelato.net/djmv01/, . [accessed: Nov. 10, 2025]
- Bandrewk, "Creating an Interactive Grid for a Puzzle Game", Oct. 2012. https://gamedev.stackexchange.com/questions/38106/creating-an-interactive-grid-for-a-puzzle-game, .
- Bing, "Slitherlink", slitherlink - Bing images. [accessed: Nov. 10, 2025]
- Geocaching, "Slitherlink", https://www.geocaching.com/geocache/GC27M4Q, . [accessed: Nov. 10, 2025]
- Cross+A, "Slitherlink", http://www.cross-plus-a.com/pl/variation.htm, . [accessed: Nov. 10, 2025]
- L'allenamente, "Rompicapo", https://brainstrainers.blogspot.com/2011/04/rompicapo.html, . [accessed: Nov. 10, 2025]
- L. Appelbe, "How to Generate Slither Link puzzles: A Tasty Treat for Algorithm nerds", Oct. 2020. https://liamappelbe.medium.com/how-to-generate-slither-link-puzzles-6c65510b2ba1, .
- Leonardrhine, "Slitherlink Puzzle", https://www.reddit.com/r/puzzles/comments/ozfyao/slitherlink_puzzle/, . [accessed: Nov. 10, 2025]
- Conceptispuzzles, "Slitherlink: Loop the Snake (iPhone, iPad, Android)", https://www.conceptispuzzles.com/ko/index.aspx?uri=mobile/100007, . [accessed: Nov. 10, 2025]
1987년 2월 : 한국항공대학교 항공전자공학과(학사)
1997년 8월 : 경상대학교 컴퓨터과학과(석사)
2001년 2월 : 경상대학교 컴퓨터과학과(박사)
2003년 3월 : 강원도립대학 컴퓨터응용과 전임강사
2004년 3월~ 2007년 2월 : 국립 원주대학 여성교양과 조교수
2007년 3월 ~ 2015년 3월 : 강릉원주대학교 멀티미디어공학과 부교수
2015년 4월 ~ 2026년 2월 : 강릉원주대학교 멀티미디어공학과 정교수
2026년 3월 ~ 현재 : 강원대학교 AI콘텐츠공학과 정교수
관심분야 : 소프트웨어 프로젝트 관리, 소프트웨어 개발 방법론, 소프트웨어 분석과 설계 방법론, 소프트웨어 신뢰성, 인공지능, 빅데이터 분석, NP-완전 문제 최적화 알고리즘, 퍼즐