숫자 연결 퍼즐은 n × n 크기의 정사각형 격자 보드에서 진행되는 퍼즐입니다. 보드를 이루는 칸 중 일부는 비어 있고, 일부는 고정 칸(solid square)이며, 고정되지 않은 일부 칸에는 정수 1, 2, 3, … 이 배치되어 있습니다. 각 정수는 보드 위에서 정확히 서로 다른 두 개의 칸을 차지합니다.
플레이어의 목표는 각 정수가 놓인 두 칸을, 수평·수직 이동만으로 구성된 단순 경로를 통해 연결하는 것입니다. 이때 다음 세 가지 제약 조건이 적용됩니다.
- 서로 다른 두 경로는 절대 교차해서는 안 됩니다.
- 어떤 경로도 고정 칸을 지나갈 수 없습니다.
- 모든 비고정(non-solid) 칸은 반드시 어느 하나의 경로로 채워져야 합니다.
퍼즐 생성 알고리즘
주어진 보드 크기 n × n에 대해 유효한 랜덤 퍼즐을 만들려면, 먼저 보드 위에 서로 교차하지 않는 무작위 단순 경로들을 생성합니다. 생성된 모든 경로 바깥에 고립된 채 남겨진 칸이 있다면, 해당 칸들은 고정(금지) 칸으로 표시합니다. 마지막으로 각 경로의 양 끝점에 정수를 배치하고, 고정 칸 목록과 함께 이를 퍼즐로 제공합니다.
요약하면 먼저 해답(solution)을 만들고, 그 해답으로부터 역으로 퍼즐을 도출하는 방식입니다. 생성된 경로들과 고정 칸들은 n × n 보드 전체를 분할(partition)하며, 이 분할을 효율적으로 관리하기 위해 유니온-파인드(Union-Find) 자료구조를 활용합니다. 이 자료구조는 보드 위 n²개 칸으로 이루어진 집합의 부분집합들을 다루는 데 사용됩니다.
의사코드(Pseudo Code)
- 보드 위에서 두 칸 (a, b)와 (c, d)를 무작위로 찾습니다. 조건은 다음과 같습니다.
- (a, b)와 (c, d)는 서로 인접한 칸이어야 하며,
- 두 칸 모두 지금까지 생성된 어떤 경로에도 속하지 않아야 합니다.
- (a, b)가 속한 유니온-파인드 트리와 (c, d)가 속한 트리를 하나로 합칩니다(union).
- 현재 경로를 더 확장할 수 있는 동안 다음을 반복합니다.
- (a, b) ← (c, d)로 이름을 바꿉니다.
- (a, b)의 인접 칸 중 (c, d)를 무작위로 선택합니다. 조건은 다음과 같습니다.
- (c, d)는 현재 경로를 포함해 지금까지 생성된 어떤 경로에도 속하지 않아야 하며,
- 부분적으로 완성된 현재 경로에서 (c, d)가 가지는 유일한 이웃은 (a, b)여야 합니다.
- 적합한 이웃 (c, d)를 찾지 못하면 더 이상 경로를 확장할 수 없으므로 반복을 종료합니다.
- 그렇지 않으면 (a, b)와 (c, d)가 속한 두 유니온-파인드 트리를 합칩니다.
- 새 경로의 시작점과 끝점에 해당하는 두 칸에 끝점(endpoint) 플래그를 설정합니다.
- SUCCESS를 반환합니다.