점 연결 퍼즐에 관한 내부 점 우선 연결 알고리즘

Ⅰ. 서 론

점 연결 퍼즐(DLP, Dots Link Puzzle)은 사각형, 오각형, 육각형, 원 등 다양한 형태의 다각형(Polygon) 게임 보드 내부에 색, 문자 또는 숫자로 서로 구별되는 n개 점들 쌍(pair, 2n)이 존재하는 퍼즐로 동일한 점들 쌍 간에 선(직선 또는 곡선)으로 연결하는 게임으로 연결선 간에 교차(Crossing)가 전혀 없도록 해야 하는 제약사항(규칙)을 준수해야 한다[1]. 이 문제는 색 연결(CL, Color Link)[2] 또는 숫자 연결(NL, Number Link)[3][4]이라고도 한다.

스도쿠(Sudoku)[5]를 비롯하여 대부분의 퍼즐들은 다항시간으로 퍼즐을 풀 수 있는 방법이 알려져 있지 않아 시행착오 법(Trial-and-error)으로 풀 수 밖에 없는 NP-완전(Non polynomial time-complete)으로 알려진 난제들이다[6]-[8]. DLP 또한 대부분의 퍼즐들과 마찬가지로 NP-완전 문제라 할 수 있다.

DLP에 관한 연구는 전무한 상태이며, 현재는 게임으로 인터넷 상으로만 출시된 상태이다[1][2][9]. 결국, DLP의 최적 해를 다항시간으로 풀 수 있는 방법은 시행착오 법 이외에는 현재까지 알려져 있지 않은 상태이다. DLP는 교차가 전혀 없도록 선을 연결하는 문제로 전자회로나 반도체 설계에 적용할 수 있다[10][11].

본 논문에서는 DLP의 최적 해를 O(n)의 선형시간 복잡도로 찾을 수 있는 알고리즘을 제안한다. 2장에서는 관련 연구를, 3장에서는 내부 점 우선 연결 법을 제안하고 사례 문제를 대상으로 적용하여 해를 구하여 본다. 4장에서는 다양한 벤치마킹 데이터들에 제안된 알고리즘을 적용하여 알고리즘의 적합성을 검증해 본다.

Ⅱ. 관련 연구와 문제점

DLP는 그림 1[9]과 같은 형태를 취하고 있다. 여기서는 다각형 게임 보드 판에 R, G, B의 3색 점들(n = 3)이 쌍으로 6개(2n = 6) 존재한다. 이들 중 n개 이상은 변(Side)에 내접하고 있으며, n개 이하는 내부(Interior)에 존재하는 형태이다.

Fig. 1.

DLP example(BT-21, CL-1)

여기서 DLP의 해가 존재하기 위해서는 반드시 1개 점 쌍은 반드시 변에 인접하여야만 한다. 그림 1의 BT-21(CL-1)에서 변에 인접한 점 쌍은 ‘G’이다.

만약 주어진 DLP가 그림 2와 같이 변에 인접한 점 쌍이 2개 이상이면 해가 존재하지 않는다. 왜냐하면, 변에 인접한 점 쌍 간에 직선을 먼저 연결하면 퍼즐 게임 보드 판을 두 영역으로 양분시켜 두 영역에 존재하는 점 쌍 간에는 교차없이 선을 연결할 수 없기 때문이다.

Fig. 2.

DLP example without solution

{G,B,R}, n = 3의 가능한 순열 수는 식 (1)에 의거 G-B-R, G-R-B, B-G-R, B-R-G, R-G-B, R-B-G의 n! = 6가지이다.

따라서 그림 1의 BT-21(CL-1)에 대해 시행착오 법의 전수탐색(Brute search, exhaustive search)으로 최적 해를 구하기 위해서는 G-B-R, G-R-B, B-G-R, B-R- G, R-G-B, R-B-G의 6가지 경우에 대해 선을 연결해 보아야 한다. 이를 수행한 결과는 그림 3에 제시되어 있다.

Fig. 3.

Number of possible cases of BT-21(CL-1)

DLP의 해를 구하기 위한 방법으로 기존에 알려진 전수 탐색 법은 O(n) 수행 복잡도를 n!회 수행하므로 수행 복잡도는 O(n!n)이다.

반면에 전수탐색 법의 n! 순열 경우 수 중에서 해가 존재하는 경우는 R-B-G와 B-R-G 순서로 선을 연결하는 2가지만 존재함을 알 수 있다.

즉, 변에 인접한 문자 쌍(G)은 마지막에 연결해야만 하며, R-B와 B-R의 2가지 경우가 모두 해가 존재하는 이유는 R과 B의 어느 한 점이나 두 점 모두 반드시 보드 판 내부에 존재한다는 점이다. 만약, 내부에 존재하는 점 쌍들의 직선이 교차하지 않으면 유일한 해가 존재하며, 교차 수(Crossing number)[10][11] 만큼의 다른 해가 존재하는 특징을 발견할 수 있다.

이와 같이 발견된 특징들에 기반하여 3장에서는 O(n) 수행 복잡도로 단 1회 만에 DLP의 해를 구하는 O(n)의 선형시간 복잡도 알고리즘을 제안한다.

Ⅲ. 내부 점 우선 연결 알고리즘

본 장에서는 그림 4와 같이 BT-21(CL-1)로부터 유도된 해 도출 법칙에 기반하여 그림 5의 O(n)의 선형시간 복잡도 내부 점 우선 연결 알고리즘(IDPCA, Internal Dot Priority Connection Algorithm)을 제안한다.

Fig. 4.

DLP's law of solution derivation

Fig. 5.

Internal dot priority connection algorithm(IDPCA)

IPPCA는 보드 판 변에 인접한 문자 쌍은 다른 문자의 쌍 간 선을 작도할 수 없도록(연결 통로 차단) 두 영역으로 양분하기 때문에 연결선 작도를 일단 유보(Holding)하고, 내부에 존재하는 문자 점들에 대해 직선을 그어 교차하면 교차를 없애기 위해 곡선으로 변경시킨다. 마지막으로 유보시킨 변에 인접한 쌍 문자 점 간 선을 기존에 확정된 선들과 교차하지 않도록 연결하여 해를 얻는 방법이다.

IDPCA를 BT-21(CL-1)에 적용한 결과는 그림 6에 제시되어 있다.

Fig. 6.

Apply IDPCA to BT-21(CL-1)

이 문제는 내부 점들인 R과 B 점 쌍의 두 직선이 교차하지 않는 관계로 내부 점들인 R과 B는 확정된 상태이다. 마지막으로 변에 인접한 G-G 간 선은 R-R과 B-B 선과 교차하지 않도록 연결하면 된다. 제안된 알고리즘은 내부 점들을 우선하여 파악하고 이들 쌍 선들이 교차하지 않도록 곡선으로 재 연결선을 긋고 변 인접 점 쌍 간 선을 기존에 확정된 선들과 교차하지 않도록 그으면 되는 가장 단순한 법칙을 적용하였음을 알 수 있다.

Ⅳ. 적용 및 결과 분석

본 장에서는 그림 7의 벤치마킹 데이터들을 대상으로 IDPCA의 적용성을 검증해 본다. 여기서 BT(Brain Test), IQT(IQ Test)는 [9]에서, DLP는 [2][12][13]에서 인용되었다.

Fig. 7.

Benchmarking data

그림 7의 벤치마킹 데이터들에 IDPCA를 적용한 결과는 그림 8에 제시하였다. 여기서는 가능한 모든 경우의 해를 제시하였으며, 실제 퍼즐을 풀 때는 이들 중 어느 하나의 해만 구하면 된다.

Fig. 8.

IDPCA for benchmarking data

그림 8에서 알 수 있듯이 IDPCA를 적용하면 어떠한 난이도의 DLP라 할지라도 내부 점 들 간에 교차가 발생하지 않도록 선을 연결하고 마지막으로 변에 인접한 점 쌍의 선을 교차가 발생하지 않도록 연결하면 항상 해를 얻을 수 있음을 알 수 있다. 따라서 DLP는 O(n)의 선형 복잡도 알고리즘이 존재함을 본 논문에서 검증하였다.

Ⅴ. 결론 및 향후 과제

본 논문에서는 보드 판에 n개의 점들 쌍이 존재하는 퍼즐에서 각 점 쌍 간에 선을 연결할 경우 교차가 발생하지 않도록 n개 선 모두를 긋는 점 연결 퍼즐을 O(n)의 선형 복잡도로 풀 수 있는 알고리즘을 제안하였다.

제안된 방법은 매우 단순한 법칙을 적용하였다. 내부 점들에 대해서 각 점 쌍 간에 선이 교차하지 않도록 연결하고, 맨 마지막에 변에 인접한 점 쌍 간 선은 기존에 작도된 선들과 교차하지 않은 공간으로 연결하는 방법이다. 제안된 알고리즘을 적용한 결과 DLP는 내부 점 들 간에 직선을 연결한 경우 교차점이 발생하면 교차점 수 만큼의 다른 해가 존재함을 알 수 있었다. 따라서 DLP의 해는 유일하게 존재하는 것이 아니라 다수가 존재한다는 사실을 밝혔다. 또한, 제안된 IDPCA를 적용하면 DLP의 해를 항상 얻을 수 있다는 사실도 실험을 통해 증명하였다.

본 연구 결과에 기반하여 추후 전자회로 기판이나 반도체 내부 회로 설계 분야에 IDPCA를 적용할 수 있는지를 연구할 계획이다.

References

• Google Play, "Connect Dots: Dots Link Puzzle", https://play.google.com/store/apps/details?id=com.guidestar.connectthedots&hl=en-US, . [accessed: Aug. 05, 2025]
• Happy Games Co., "Color Link - Connect the Dots", https://play.google.com/store/apps/details?id=com.color.link&hl=en-US, . [accessed: Aug. 05, 2025]
• K. Kouichi and T. Yasuhiko, "NP-Completeness and Enumeration of Number Link Puzzle", IEICE Technical Reports in Theoretical Foundations of Computing, Vol. 109, No. 465, pp. 1-7, Mar. 2010.
• S. U. Lee, "Algorithm for Cross-avoidance Bypass Routing in Numberlink Puzzle", Journal of IIBC, Vol. 24, No. 3, pp. 95-101, Jun. 2024. [https://doi.org/10.7236/JIIBC.2024.24.3.95]
• S. U. Lee, "Binary Backtracking Algorithm for Sudoku", Journal of IIBC, Vol. 17, No. 4, pp. 155-161, Aug. 2017. [https://doi.org/10.7236/.2017.17.4.155]
• Wikipedia, "List of NP-Complete Problems", https://en.wikipedia.org/wiki/List_of_NP-complete_problems, . [accessed: Aug. 05, 2025]
• G. Viglietta, "Gaming Is a Hard Job, but Someone Has to Do It!", Theory of Computer Systems, Vol. 54, No. 4, pp. 595-621, Jan. 2012. [https://doi.org/10.1007/978-3-642-30347-0_35]
• G. Kendall, A. J. Parkes, and K. Spoerer, "A Survey of NP-Complete Puzzles", ICGA Journal: The Journal of the Computer Games Community, Vol. 31, No. 1, pp. 13-34, Mar. 2008. [https://doi.org/10.3233/ICG-2008-31103]
• R. Master, "Raviraj Master", https://www.youtube.com/@ravirajmaster/shorts, . [accessed: Aug. 05, 2025]
• M. R. Garey and D. S. Johnson, "Crossing Number is NP-complete", SIAM Journal of Algorithmic Discrete Meth., Vol. 4, No. 3, pp. 312-316, Sep. 1983. [https://doi.org/10.1137/0604033]
• J. Díaz, J. Petit, and M. Serna, "A Survey on Graph Layout Problems", ACM Computing Surveys, Vol. 34, No. 3, pp. 313-356, Sep. 2002. [https://doi.org/10.1145/568522.568523]
• Puzzle Games.com, "Connect the dots of same color without crossing the lines!" https://www.puzzlegame.com/Color-Connect, . [accessed: Aug. 05, 2025]
• r/puzzles, "Connecting same colors with a line, lines cannot touch", https://www.reddit.com/r/puzzles/comments/1alpq78/connecting_same_colors_with_a_line_lines_cannot/, . [accessed: Aug. 05, 2025]